BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1443
DTSTAMP:20240709T062350Z
SUMMARY:Limitations of Massively Parallel Constant-time Algorithms
DESCRIPTION:Speaker: Vaibhav Krishan (Indian Institute of Technology\, Bomb
 ay)\n\nAbstract: \nHow many processors are needed to compute a function in
  constant-time by a massively parallel algorithm? We consider this questio
 n with the lens of Boolean circuits. Here\, we compose logic gates\, acti
 ng as processors\, with the number of layers corresponding to the running
  time\, to compute a Boolean function.Hence\, the question we would like 
 to answer is: how many gates do we need in such a circuit to compute a ce
 rtain function if the circuit only has a constant number of layers? In p
 articular\, we are searching for explicit functions that require a very l
 arge number of gates\, with a given set of choices for the logic gates.An
 swers to such questions have implications in learning theory\, cryptograp
 hy\, and the study of randomness. In this talk\, I will discuss past and 
 recent progress on such questions. Then\, I will talk about a recent high
 er-order Fourier-analysis based approach\, proposed by Bhrushundi\, Hosse
 ini\, Lovett and Rao (ITCS 2019)\, towards resolving a thirty-five years 
 old conjecture. Afterwards\, I will describe our contribution in developi
 ng this approach\, where we propose studying the projection of an explici
 t set of vectors towards resolving this conjecture. The talk will conclu
 de with some implications towards other frontiers in the study of Boolean
  circuits.The work I will discuss in this talk was in collaboration with P
 rof. Sundar Vishwanathan at IIT Bombay.\nShort Bio:\nVaibhav Krishan is a
  recent PhD graduate from IIT Bombay\, where he worked under the supervis
 ion of Prof. Sundar Vishwanathan and Prof. Nutan Limaye. He has worked in
  the industry as a quantitative trader\, and as a data scientist\, after 
 completing his undergrad. \n
URL:https://www.tcs.tifr.res.in/web/events/1443
DTSTART;TZID=Asia/Kolkata:20240709T160000
DTEND;TZID=Asia/Kolkata:20240709T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR