BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/677
DTSTAMP:20230914T125934Z
SUMMARY:Average Case Lower Bounds for Bounded Depth Threshold Circuits
DESCRIPTION:Speaker: Srikanth Srinivasan (Indian Institute of Technology\nD
epartment of Mathematics\nPowai\nMumbai 400076)\n\nAbstract: \nAbstract: A
threshold gate is a Boolean function that accepts its input based on whet
her some weighted linear combination of its inputs exceeds some fixed thre
shold 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.\n\nW
eak lower bounds for threshold circuits have been known for two decades. I
mpagliazzo\, 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.\n\nWe 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 mo
st $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.\n\nI will talk about some of the techniques in this and other wor
ks on threshold circuits (joint work with Ruiwen Chen (Oxford) and Rahul S
anthanam (Oxford)).\n
URL:https://www.tcs.tifr.res.in/web/events/677
DTSTART;TZID=Asia/Kolkata:20160426T160000
DTEND;TZID=Asia/Kolkata:20160426T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR