Event calendar file
School of Technology and Computer Science Seminars
On Circuit Depth of Symmetric Boolean Functions
by Tulasi mohan Molli (School of Technology and Computer Science, TIFR)
Friday, September 15, 2017
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
| Description |
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. |
