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