BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1136
DTSTAMP:20230914T125952Z
SUMMARY:Approximate Polymorphisms
DESCRIPTION:Speaker: Nitin Saurabh (Technion-IIT\, Haifa\, Israel)\n\nAbstr
 act: \nA Boolean function f on n variables is called a polymorphism of ano
 ther Boolean function g on m variables if their operations commute. That i
 s\, for all {0\,1}-matrix Z of dimension (n x m)\, f(g(row1(Z))\, g(row2(Z
 ))\, ...\, g(rown(Z))) = g(f(col1(Z))\, f(col2(Z))\, ...\,f(colm(Z))). The
  function f is called an approximate polymorphism if this equality holds w
 ith probability close to 1 when Z is sampled uniformly.\nThe problem of ch
 aracterizing the structure of exact or approximate polymorphisms appears i
 n several different contexts\, namely in understanding the complexity of C
 SPs\, property testing\, and social choice theory.\nIn this talk\, we will
  give a characterization of exact polymorphisms\, and also show that appro
 ximate polymorphisms must be close to exact polymorphisms. Our results gen
 eralize the classical linearity testing result of Blum et al. as well as t
 he recent AND testing result of Filmus et al.\nThis is based on a joint wo
 rk with Gilad Chase\, Yuval Filmus and Dor Minzer.\nZoom link: https://zoo
 m.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09\n
URL:https://www.tcs.tifr.res.in/web/events/1136
DTSTART;TZID=Asia/Kolkata:20210618T171500
DTEND;TZID=Asia/Kolkata:20210618T181500
END:VEVENT
END:VCALENDAR