BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/279
DTSTAMP:20230914T125917Z
SUMMARY:Hard-core Set Theorem: Magic of Average Case Complexity
DESCRIPTION:Speaker: Sagnik  Mukhopadhyay\n\nAbstract: \nSuppose you are tr
 ying to build a circuit using limited number of AND\, OR\, NOT gates to co
 mpute some boolean function $f$ over inputs in $\\{0\,1\\}^n$. But the fun
 ction is such that every circuit with the above limit on its resources fai
 ls to compute $f$ correctly on a small fraction of the inputs\, i.e. the f
 unction is 'hard' for circuits of this given size.\nIn the above case\, tw
 o things might be happening:\na) All the circuits that you are trying out 
 are failing for different sets of inputs\, and intuitively\, there should 
 be functions for which no particular input is harder than any particular o
 ther input\, per se.\nb) There can be one small set $H$ hidden in the inpu
 t set which is extremely hard to compute by any circuit\, and on that set 
 $H$\, no circuit can do any better than guessing $f$ randomly.\nImpagliazz
 o's hardcore set lemma is 'one bit of magic in complexity theory' which sa
 ys that it is always the second case\, as if the hardness of the function 
 is concentrated on a small 'hardcore' set $H$ inside the input space. I wi
 ll state and prove this result in the talk.\n
URL:https://www.tcs.tifr.res.in/web/events/279
DTSTART;TZID=Asia/Kolkata:20120525T150000
DTEND;TZID=Asia/Kolkata:20120525T163000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR