BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/668
DTSTAMP:20230914T125933Z
SUMMARY:Some Lower Bounds for Depth 2 Circuits with Threshold and Mod Gates
DESCRIPTION:Speaker: Tulasi mohan Molli\n\nAbstract: \nAbstract: In this ta
 lk\, we will see some lower bound techniques for depth 2 circuits with thr
 eshold and mod gates. We focus mainly on two techniques to prove lower bou
 nds for threshold circuits: communication complexity and random restrictio
 ns.\n\nThe communication complexity approach for proving lower bounds is b
 ased on the observation that depth 2 circuits with a threshold gate at the
  top and a small number of low communication gates at the bottom  have ef
 ficient randomized protocols. So\, one approach for proving lower bounds f
 or the above mentioned classes of circuits is to produce a function which 
 has small discrepancy. The lower bound follows from the well known result 
 that functions with small discrepancy have large randomized communication 
 complexity.\n\nThe function with small discrepancy is obtained by lifting 
 a base function with large sign degree by a process called masking. This m
 ethod of lifting to obtain hard functions was used by Krause and Pudlak to
  obtain functions with large sign monomial complexity from a base function
  with large sign degree. This shows an exponential lower bound for depth 2
  threshold circuits with AND gates at the bottom. We will see a degree-dis
 crepency which says that if the sign degree of the base function is large\
 , then the discrepancy of it's lift is small.\n\nIn our work\, we observed
  that masking the Universal Threshold function which is a linear threshold
  function also gives rise to a function which has small discrepancy. There
 by\, we show that for a lifted function to be hard\, the base function nee
 d not have high sign degree.\n
URL:https://www.tcs.tifr.res.in/web/events/668
DTSTART;TZID=Asia/Kolkata:20160331T140000
DTEND;TZID=Asia/Kolkata:20160331T150000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR