Tata Institute of Fundamental Research
Average Case Lower Bounds for Bounded Depth Threshold Circuits
STCS Colloquium
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)
Abstract:
Abstract: A threshold gate is a Boolean function that accepts its input based on whether some weighted linear combination of its inputs exceeds some fixed threshold value or not. A threshold circuit is a circuit made up of threshold gates. Proving superpolynomial lower bounds for depth-2 threshold circuits is one of the outstanding open problems in circuit complexity today.
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)).
| 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)
Abstract:
Abstract: A threshold gate is a Boolean function that accepts its input based on whether some weighted linear combination of its inputs exceeds some fixed threshold value or not. A threshold circuit is a circuit made up of threshold gates. Proving superpolynomial lower bounds for depth-2 threshold circuits is one of the outstanding open problems in circuit complexity today.
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)).
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)).