BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/830
DTSTAMP:20230914T125940Z
SUMMARY:Simple Boolean Functions on the p-biased Hypercube
DESCRIPTION:Speaker: Irit Dinur (Weizmann Institute of Science\nDepartment 
 of Applied Math and\nComputer Science\nRehovot\n76100 Israel)\n\nAbstract:
  \nNisan and Szegedy showed that low degree Boolean functions are juntas\,
  namely\, they depend only on a constant number of their variables. Kindle
 r and Safra showed a robust version of the above: low degree functions whi
 ch are almost Boolean are close to juntas.\nWe study the same question on 
 the p-biased hypercube\, for very small $p$.  The $p$-biased hypercube is
  a product probability space in which each coordinate is 1 with probabilit
 y p and 0 otherwise. In this space most of the measure is on $n$-bit strin
 gs whose Hamming weight about $pn \\ll n$.\nIt turns out that here new phe
 nomena emerge. For example\, the function $x_1 + ... + x_n=p (where x_i \\
 in {0\,1})$ is close to Boolean but not close to a junta.\nWe characterize
  low degree functions that are almost Boolean and show that they are close
  to a new class of functions which we call sparse juntas.\nAn interesting 
 aspect of our proof is that it relies on a local to global agreement theor
 em. We cover the $p$-biased hypercube by many smaller dimensional copies o
 f the uniform hypercube\, and approximate our function locally via the Kin
 dler-Safra theorem for constant p. We then stitch the local approximations
  together into one global function that is a sparse junta (based on joint 
 work with Yuval Filmus and Prahladh Harsha).\n
URL:https://www.tcs.tifr.res.in/web/events/830
DTSTART;TZID=Asia/Kolkata:20171205T113000
DTEND;TZID=Asia/Kolkata:20171205T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR