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