On Circuit Depth of Symmetric Boolean Functions

Tulasi mohan Molli
Sayantan Chakraborty
Friday, 15 Sep 2017, 17:15 to 18:15
A-201 (STCS Seminar Room)
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.