Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas

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 2 Ω(n 1/4 / √ ε) -query lower bound for non-adaptive, two-sided tolerant monotonicity testers and unateness testers when the "gap" parameter ε 2 -ε 1 is equal to ε, for any ε ≥ 1/ √ n;