2025/12/15 by Dor Minzer, Minzer, Dor
Computer Science · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2512.13566
We show a procedure that, given oracle access to a function f\colon \0,1\n→\0,1\, produces oracle access to a function f'\colon \0,1\n'→\0,1\ such that if f is monotone, then f' is monotone, and if f is ε-far from monotone, then f' is Ω(1)-far from monotone. Moreover, n' ≤ n 2O(1/ε) and each oracle query to f' can be answered by making 2O(1/ε) 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 εc>0, such that any (even two-sided, adaptive) algorithm distinguishing between monotone functions and εc-far from monotone functions, requires Ω(n1/2-c) queries. Combining our lemma with their result implies a similar result, except that the distance from monotonicity is an absolute constant ε>0, and the lower bound is Ω(n1/2-o(1)) queries.