C. Seshadhri, Deeparnab Chakrabarty

For positive integers $n, d$, consider the hypergrid $[n]^d$ with the coordinate-wise product partial ordering denoted by $\prec$.

A function $f: [n]^d \mapsto \mathbb{N}$ is monotone if $\forall x \prec y$, $f(x) \leq f(y)$.

A function $f$ is $\varepsilon$-far from monotone if at least an $\varepsilon$-fraction of values must ...
more >>>

Subhash Khot, Dor Minzer, Muli Safra

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we

give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function

$f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from

being monotone ...
more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

We study monotonicity testing of Boolean functions over the hypergrid $[n]^d$ and design a non-adaptive tester with $1$-sided error whose query complexity is $\tilde{O}(d^{5/6})\cdot \text{poly}(\log n,1/\epsilon)$. Previous to our work, the best known testers had query complexity linear in $d$ but independent of $n$. We improve upon these testers as ... more >>>

C. Seshadhri, Deeparnab Chakrabarty

The problem of testing monotonicity

of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ has received much attention

recently. Denoting the proximity parameter by $\varepsilon$, the best tester is the non-adaptive $\widetilde{O}(\sqrt{n}/\varepsilon^2)$ tester

of Khot-Minzer-Safra (FOCS 2015). Let $I(f)$ denote the total influence

of $f$. We give an adaptive tester whose running ...
more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Testing monotonicity of Boolean functions over the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic problem in property testing. When the range is real-valued, there are $\Theta(d\log n)$-query testers and this is tight. In contrast, the Boolean range qualitatively differs in two ways:

(1) Independence of $n$: There are testers ...
more >>>

Omri Ben-Eliezer

We study testing of local properties in one-dimensional and multi-dimensional arrays. A property of $d$-dimensional arrays $f:[n]^d \to \Sigma$ is $k$-local if it can be defined by a family of $k \times \ldots \times k$ forbidden consecutive patterns. This definition captures numerous interesting properties. For example, monotonicity, Lipschitz continuity and ... more >>>

Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, Erik Waingarten

We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed $k \in \mathbb{N}$ and $\varepsilon > 0$, we show that the non-adaptive query complexity of finding a length-$k$ monotone subsequence of $f \colon [n] \to \mathbb{R}$, assuming that $f$ is $\varepsilon$-far ... more >>>

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten

We design a nonadaptive algorithm that, given a Boolean function $f\colon \{0,1\}^n \to \{0,1\}$ which is $\alpha$-far from monotone, makes poly$(n, 1/\alpha)$ queries and returns an estimate that, with high probability, is an $\widetilde{O}(\sqrt{n})$-approximation to the distance of $f$ to monotonicity. Furthermore, we show that for any constant $\kappa > ... more >>>

Hadley Black, Iden Kalemaj, Sofya Raskhodnikova

We generalize the celebrated isoperimetric inequality of Khot, Minzer, and Safra (SICOMP 2018) for Boolean functions to the case of real-valued functions $f \colon \{0,1\}^d\to\mathbb{R}$. Our main tool in the proof of the generalized inequality is a new Boolean decomposition that represents every real-valued function $f$ over an arbitrary partially ... more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

The problem of testing monotonicity for Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$ is a classic topic in property testing. When $n=2$, the domain is the hypercube. For the hypercube case, a breakthrough result of Khot-Minzer-Safra (FOCS 2015) gave a non-adaptive, one-sided tester making $\widetilde{O}(\varepsilon^{-2}\sqrt{d})$ queries. Up to polylog ... more >>>

Hadley Black, Deeparnab Chakrabarty, C. Seshadhri

Monotonicity testing of Boolean functions on the hypergrid, $f:[n]^d \to \{0,1\}$, is a classic topic in property testing. Determining the non-adaptive complexity of this problem is an important open question. For arbitrary $n$, [Black-Chakrabarty-Seshadhri, SODA 2020] describe a tester with query complexity $\widetilde{O}(\varepsilon^{-4/3}d^{5/6})$. This complexity is independent of $n$, but ... more >>>

Renato Ferreira Pinto Jr.

We study the connection between directed isoperimetric inequalities and monotonicity testing. In recent years, this connection has unlocked breakthroughs for testing monotonicity of functions defined on discrete domains. Inspired the rich history of isoperimetric inequalities in continuous settings, we propose that studying the relationship between directed isoperimetry and monotonicity in ... more >>>