A Distance Amplification Lemma for Monotonicity

Abstract

We show a procedure that, given oracle access to a function $f:\{0,1{\}}^n\to \{0,1\}$, produces oracle access to a function $f^{\prime }:\{0,1{\}}^{n^{\prime }}\to \{0,1\}$ such that if $f$ is monotone, then $f^{\prime }$ is monotone, and if $f$ is $\epsilon$-far from monotone, then $f^{\prime }$ is $\Omega (1)$-far from monotone. Moreover, $n^{\prime }\le n{2}^{O(1/\epsilon )}$ and each oracle query to $f^{\prime }$ can be answered by making $2^{O(1/\epsilon )}$ oracle queries to $f$. Our lemma is motivated by a recent result of [Chen, Chen, Cui, Pires, Stockwell, arXiv:2511.04558], who showed that for all $c>0$ there exists ${\epsilon }_c>0$, such that any (even two-sided, adaptive) algorithm distinguishing between monotone functions and ${\epsilon }_c$-far from monotone functions, requires $\Omega (n^{1/2-c})$ queries. Combining our lemma with their result implies a similar result, except that the distance from monotonicity is an absolute constant $\epsilon >0$, and the lower bound is $\Omega (n^{1/2-o(1)})$ queries.