All reports by Author Erik Waingarten:

__
TR19-165
| 18th November 2019
__

Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten#### Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning

__
TR19-163
| 16th November 2019
__

Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Erik Waingarten#### Approximating the Distance to Monotonicity of Boolean Functions

__
TR19-134
| 4th October 2019
__

Omri Ben-Eliezer, Clement Canonne, Shoham Letzter, Erik Waingarten#### Finding monotone patterns in sublinear time

__
TR18-094
| 2nd May 2018
__

Amit Levi, Erik Waingarten#### Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs

__
TR17-068
| 20th April 2017
__

Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie#### Settling the query complexity of non-adaptive junta testing

Clement Canonne, Xi Chen, Gautam Kamath, Amit Levi, Erik Waingarten

We give a nearly-optimal algorithm for testing uniformity of distributions supported on $\{-1,1\}^n$, which makes $\tilde O (\sqrt{n}/\varepsilon^2)$ queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restriction for distributions on $\{-1,1\}^n$, and a quantitative analysis of how ... 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 >>>

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 >>>

Amit Levi, Erik Waingarten

We introduce a new model for testing graph properties which we call the \emph{rejection sampling model}. We show that testing bipartiteness of $n$-nodes graphs using rejection sampling queries requires complexity $\widetilde{\Omega}(n^2)$. Via reductions from the rejection sampling model, we give three new lower bounds for tolerant testing of Boolean functions ... more >>>

Xi Chen, Rocco Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie

We prove that any non-adaptive algorithm that tests whether an unknown

Boolean function $f\colon \{0, 1\}^n\to\{0, 1\} $ is a $k$-junta or $\epsilon$-far from every $k$-junta must make $\widetilde{\Omega}(k^{3/2} / \epsilon)$ many queries for a wide range of parameters $k$ and $\epsilon$. Our result dramatically improves previous lower ...
more >>>