Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Erik Waingarten:

TR18-094 | 2nd May 2018
Amit Levi, Erik Waingarten

Lower Bounds for Tolerant Junta and Unateness Testing via Rejection Sampling of Graphs

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

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

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

ISSN 1433-8092 | Imprint