BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/447
DTSTAMP:20230914T125925Z
SUMMARY:Switching in Boolean Circuits and Modelling Cognition Through Neuro
ids
DESCRIPTION:Speaker: Pritam Bhattacharya\n\nAbstract: \nAbstract: In comput
ational complexity theory\, Håstad's switching lemma is a vital analytica
l tool for proving lower bounds on the size of constant-depth Boolean circ
uits. Using the switching lemma\, Håstad showed in 1986 that Boolean circ
uits of depth $k$\, in which only AND\, OR\, and NOT gates are allowed\, r
equire size $\\exp\\left(\\Omega\\left(n^{\\frac{1}{k-1}}\\right)\\right)$
for computing the PARITY function on $n$ variables. In essence\, the swit
ching lemma says that\, given an arbitrary formula in disjunctive normal f
orm\, if we set some fraction of the variables randomly\, then with high p
robability\, the restricted function can be computed by a decision tree of
small depth. In 2012\, Impagliazzo\, Matthews and Paturi formulated an ex
tended switching lemma which says that\, given a sequence of formulas in c
onjunctive and/or disjunctive normal form on the same set of variables\, i
f all of them are hit by the same random restriction\, then it is exponent
ially unlikely that there is a large subset of formulas where each formula
contributes a large number of variables to their joint decision tree. In
the first part of my talk\, we will discuss the extended switching lemma a
nd its proof with the help of an illustrative example.\n\nIn the second pa
rt of the talk\, we will critique the neuroidal model for cognition propos
ed by Valiant. We will start off by discussing the motivation behind Valia
nt's work. We will then explore the physiology of the brain and some insig
hts from cognitive psychology that aided Valiant's formulation of the neur
oidal model. Next\, we will describe the actual model in extensive detail
and present the algorithm put forward by Valiant for implementing unsuperv
ised memorization within his model as a case study. Finally\, we will conc
lude by discussing the relevance of the neuroidal model to the current att
empts by researchers to build cognitive computing systems.\n \n
URL:https://www.tcs.tifr.res.in/web/events/447
DTSTART;TZID=Asia/Kolkata:20140121T140000
DTEND;TZID=Asia/Kolkata:20140121T153000
LOCATION:AG-66 (Lecture Theatre)
END:VEVENT
END:VCALENDAR