BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/360
DTSTAMP:20230914T125921Z
SUMMARY:Boolean Monotonicity Testing via an Isoperimetry Result on the Dire
cted Hypercube
DESCRIPTION:Speaker: Deeparnab Chakrabarty (Microsoft Research\, India\n#9\
, Lavelle Road\nBangalore\, Karnataka 560025\n\n\n )\n\nAbstract: \nA Boo
lean function $f:\\{0\,1\\}^n \\to \\{0\,1\\}$ is monotone if $f(x) \\geq
f(y)$ whenever $x > y$\, that is\, all coordinates of $x$ dominate those o
f $y$. $f$ is $\\epsilon$-far from monotone if the function needs to be ch
anged in at least $\\epsilon$ fraction of the domain points to make it mon
otone. We are interested in the problem of distinguishing monotone functio
ns from those that are $\\epsilon$-far\, given only query access to the fu
nction\, making as few queries to the function as possible. There is a rel
atively easy tester making $O(n/\\epsilon)$-queries from 2000. In this tal
k\, I'll show a slightly more sophisticated tester which makes $o(n)$ quer
ies (to be precise\, it makes $O(n^{5/6}/\\epsilon^{10/3})$ queries).\nOne
of the main ingredients will be an isoperimetry result on the *directed*
hypercube\, where the edges of the hypercube are directed from $y$ to $x$
if $x > y$. In particular\, we show that the support set (the $x$'s s.t.
$f(x)=1$) of a $\\epsilon$-far from monotone function\, either have a la
rge directed edge expansion\, or a large directed vertex expansion (joint
work with C. Seshadhri).\n
URL:https://www.tcs.tifr.res.in/web/events/360
DTSTART;TZID=Asia/Kolkata:20130502T153000
DTEND;TZID=Asia/Kolkata:20130502T163000
LOCATION:AG-80
END:VEVENT
END:VCALENDAR