BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/238
DTSTAMP:20230914T125916Z
SUMMARY:Fighting Boolean Circuits: New Correlation Bounds and Pseudorandom 
 Generators
DESCRIPTION:Speaker: Srikanth Srinivasan\nRutgers University\nDIMACS\nNew B
 runswick\nNew Jersey\nUnited States of America\n\nAbstract: \nThe general 
 problem of proving limitations on what efficient algorithms can accomplish
  has been the subject of much research over the past four decades. In this
  talk\, we consider the specific question of bounding the power of Boolean
  circuits. We discuss three generic questions: those of proving lower boun
 ds\, correlation bounds\, and constructing Pseudorandom generators (PRGs) 
 for different classes of Boolean circuits. We look at the major results in
  these directions and the important questions that need to be tackled next
 .\n\nIn the process\, we motivate the question of proving correlation boun
 ds and constructing PRGs for bounded-depth circuits. We then describe our 
 own results: correlation bounds for AC^0 with a few symmetric gates\, and 
 explicit PRGs against read-once ACC^0 (this is joint work with Shachar Lov
 ett (IAS\, Princeton) and Dmitry Gavinsky (NEC Research Labs\, Princeton))
 .\n
URL:https://www.tcs.tifr.res.in/web/events/238
DTSTART;TZID=Asia/Kolkata:20120104T113000
DTEND;TZID=Asia/Kolkata:20120104T123000
LOCATION:A-212 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR