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