Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity,
Unateness, and Juntas
by Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
Oded's comments
Not clear why I missed this wonderful result.
I guess it is a consequence of not following arXiv,
which I find quite unfriendly,
and not following the friendly
Property Tesing Review
well enough.
As far as I know this is the first significant
separation between tolerant and standard testing
obtained via a natural property,
alas it refers only to non-adaptove testers.
In contrast, prior seprataions, which follow
Fischer
and Fortnow (2006), embed a PCP system in the property.
The original abstract
(slightly revised to avoid setting complex math expressions)
We give the first super-polynomial (in fact, mildly exponential) lower bounds for tolerant testing (equivalently, distance estimation) of monotonicity, unateness, and juntas with a constant separation between the "yes" and "no" cases.
Specifically, we give
- A exp(Omega(n sup 1/4)))-query lower bound for non-adaptive,
two-sided tolerant monotonicity testers and unateness testers
when the "gap" parameter is larger than 1/sqrt(n);
- A exp(Omega(n sup 1/2)))-query lower bound for non-adaptive,
two-sided tolerant junta testers when the gap parameter
is an absolute constant.
In the constant-gap regime no non-trivial prior lower bound
was known for monotonicity, the best prior lower bound known
for unateness was Omega(n sup 3/2) queries,
and the best prior lower bound known for juntas was poly(k) queries.
See arXiv 2309.12513
Back to
list of Oded's choices.