BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1658
DTSTAMP:20251219T042011Z
SUMMARY:Depth-2 threshold circuits and related models of computation
DESCRIPTION:Speaker: Vladimir Podolskii (Tufts University)\n\nAbstract: \nL
 ow-depth Boolean threshold circuits play an important role in theoretical 
 computer science. On one hand\, they are central for some of the main curr
 ent frontiers in Boolean circuit complexity\, and on the other hand they f
 orm a Boolean version of feed-forward neural networks. It turns out that p
 roving lower bounds for these Boolean circuits is notoriously hard: lower 
 bounds for explicit functions are unknown even for depth-2 circuits. In ot
 her words\, we do not understand well the expressibility of feed-forward n
 eural networks with just one hidden layer.In this talk we will discuss kno
 wn approaches to this problem\, subproblems that also remain open\, and so
 me recent progress on them. In particular\, we will discuss other computat
 ional models that turn out to be related to this setting\, including model
 s based on decision lists and models based on nearest neighbour representa
 tion of Boolean functions.The talk is based on joint work with Mason DiCic
 co\, Daniel Reichman and Morgan Prior. I will also mention some older resu
 lts of joint work with Kristoffer Arnsfelt Hansen.\nShort Bio:\nVladimir P
 odolskii is a theoretical computer scientist working in computational comp
 lexity. He is currently an associate professor at Tufts University. Prior 
 to that he has worked at Steklov Mathematical Institute in Moscow since 20
 09 as research scientist. From 2014 till 2022 he also worked at HSE Univer
 sity in Moscow as an associate professor (part-time). From 2022 till 2023 
 we worked as visiting associate professor at Courant Institute\, NYU. He r
 eceived his PhD from Moscow State University in 2009.\n \n
URL:https://www.tcs.tifr.res.in/web/events/1658
DTSTART;TZID=Asia/Kolkata:20251224T110000
DTEND;TZID=Asia/Kolkata:20251224T120000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR