A boolean circuit is a natural model of computation for Boolean functions. Size and Depth of a circuit are two measures of complexity of the circuit.
A long standing open problem is to show a super logarithmic lower-bound for the depth of the circuit computing an explicit function.
Symmetric functions are a class of functions where permuting the input bits does not change the value output or in other words, the function depends only on the number 1's in the input.
In this talk, we will see Valiant's construction of a logarithmic depth circuit for the majority function which in turn gives a logarithmic depth circuit for any symmetric function.
