Speaker: |
Tulasi mohan Molli |

Organiser: |
Sayantan Chakraborty |

Date: |
Friday, 15 Sep 2017, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

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.