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