Tata Institute of Fundamental Research
Boolean Monotonicity Testing via an Isoperimetry Result on the Directed Hypercube
Seminar
Speaker:
Deeparnab Chakrabarty (Microsoft Research, India
#9, Lavelle Road
Bangalore, Karnataka 560025
)
Organiser:
Prahladh Harsha
Date:
Thursday, 2 May 2013, 15:30 to 16:30
Venue:
AG-80
(Scan to add to calendar)
Abstract:
A Boolean 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 of $y$. $f$ is $\epsilon$-far from monotone if the function needs to be changed in at least $\epsilon$ fraction of the domain points to make it monotone. We are interested in the problem of distinguishing monotone functions from those that are $\epsilon$-far, given only query access to the function, making as few queries to the function as possible. There is a relatively easy tester making $O(n/\epsilon)$-queries from 2000. In this talk, I'll show a slightly more sophisticated tester which makes $o(n)$ queries (to be precise, it makes $O(n^{5/6}/\epsilon^{10/3})$ queries).
One 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 large directed edge expansion, or a large directed vertex expansion (joint work with C. Seshadhri).
| Speaker: | Deeparnab Chakrabarty (Microsoft Research, India #9, Lavelle Road Bangalore, Karnataka 560025 ) |
| Organiser: | Prahladh Harsha |
| Date: | Thursday, 2 May 2013, 15:30 to 16:30 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
A Boolean 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 of $y$. $f$ is $\epsilon$-far from monotone if the function needs to be changed in at least $\epsilon$ fraction of the domain points to make it monotone. We are interested in the problem of distinguishing monotone functions from those that are $\epsilon$-far, given only query access to the function, making as few queries to the function as possible. There is a relatively easy tester making $O(n/\epsilon)$-queries from 2000. In this talk, I'll show a slightly more sophisticated tester which makes $o(n)$ queries (to be precise, it makes $O(n^{5/6}/\epsilon^{10/3})$ queries).
One 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 large directed edge expansion, or a large directed vertex expansion (joint work with C. Seshadhri).
One 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 large directed edge expansion, or a large directed vertex expansion (joint work with C. Seshadhri).