Speaker: |
Srikanth Srinivasan (Indian Institute of Technology Department of Mathematics Powai Mumbai 400076) |

Organiser: |
Prahladh Harsha |

Date: |
Tuesday, 26 Apr 2016, 16:00 to 17:00 |

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

(Scan to add to calendar)

Weak lower bounds for threshold circuits have been known for two decades. Impagliazzo, Paturi, and Saks (building on work of Paturi and Sas) showed that any threshold circuit of depth-d computing the Parity function must have at least $n^{1/(d-1)}$ gates and $n^{1+1/exp(d)}$ wires. Surprisingly these bounds are known to be nearly tight.

We show stronger *average* case lower bounds in the same regime. We show that for each integer $d > 1$, there is an \epsilon_$d > 0$ such that Parity has correlation at most $1/n^{\Omega(1)}$ with depth-$d$ threshold circuits which have at most $n^{1/2(d-1)}$ gates or $n^{1+\epsilon_d}$ wires. We also show that the Generalized Andreev Function has correlation at most $1/2^{n^{\Omega(1)}}$ with depth-$d$ threshold circuits which have at most $n^{1+ \epsilon_d}$ wires.

I will talk about some of the techniques in this and other works on threshold circuits (joint work with Ruiwen Chen (Oxford) and Rahul Santhanam (Oxford)).