One of the Best Paper Award winners at STOC 2026 is a paper by Mark Chen, Xi Chen, Hao Cui, William Pires, and Jonah Stockwell (Chen et al. 2026), which almost determines the query complexity of testing monotonicity of Boolean functions. The authors prove that even a fully adaptive randomized algorithm needs almost queries. This improves the previous exponent to essentially the optimal exponent .
Let us first formulate the problem. A Boolean function on variables is a function There are possible inputs, so the complete truth table of contains values.
For write if We say that is monotone if In other words, changing some coordinates of the input from to can never change the output from to .
For example, for any fixed integer , the function is monotone.
Suppose now that is unknown, and that an algorithm may choose an input and ask for the value . Such a request is called a query. The algorithm is not given the full truth table; it only sees the values at the points it queries.
If the goal were to determine exactly whether an arbitrary unknown function is monotone, one could not expect to do this after examining only a tiny part of its exponentially large truth table. Property testing asks a more flexible question: can we distinguish monotone functions from functions which are very far from every monotone function?
For two Boolean functions define their distance by Thus is the proportion of inputs on which the two functions have different values.
For a constant , we say that is -far from monotone if for every monotone Boolean function . Equivalently, one has to change the values of at at least inputs in order to make it monotone.
A randomized algorithm is called an -tester for monotonicity if it satisfies the following two requirements:
if is monotone, the algorithm outputs “monotone” with probability at least ;
if is -far from monotone, the algorithm outputs “not monotone” with probability at least .
The probability is over the random choices made by the algorithm. There is no requirement when is non-monotone but is less than away from some monotone function.
The number of values of requested by the algorithm is its query complexity. A tester is called non-adaptive if all points at which it queries are selected before any answers are known. A tester is called adaptive if later queries are allowed to depend on the answers to earlier ones.
Adaptivity can potentially be very useful. After seeing a suspicious value of , an adaptive algorithm may choose its next query nearby and try to locate a violation of monotonicity. A lower bound for adaptive testers is therefore substantially stronger than the same lower bound for non-adaptive testers.
The main theorem of Chen, Chen, Cui, Pires, and Stockwell (Chen et al. 2026) is the following.
Theorem. For every constant , there exist constants , , and such that, for every , every randomized adaptive -tester for monotonicity of Boolean functions makes at least queries.
Since can be arbitrarily small, this says that the exponent in the lower bound can be made arbitrarily close to . For example, by taking , one obtains a lower bound proportional to , for some fixed value of . The constant is allowed to depend on .
The history of the problem makes this theorem particularly striking. In 2015, Chen, De, Servedio, and Tan (Chen et al. 2015) had already proved an almost- lower bound for non-adaptive testers: for every , some constant forces at least a constant multiple of queries. Thus the non-adaptive problem was already understood quite well. What remained unclear was whether adaptivity could provide a substantial advantage.
In 2017, Chen, Waingarten, and Xie (Chen et al. 2017) proved that an adaptive tester needs roughly queries, up to logarithmic factors. This was the best adaptive lower bound for several years.
On the other hand, Khot, Minzer, and Safra (Khot et al. 2018) constructed a non-adaptive tester using, for fixed , queries multiplied only by a polylogarithmic factor in . More precisely, their dependence on is proportional to . In particular, for every fixed and every , their number of queries is at most for all sufficiently large , where is a constant.
Before the new result, therefore, there was a genuine polynomial gap: the best adaptive lower bound had exponent , whereas an upper bound with exponent arbitrarily close to was known. The new theorem closes this polynomial gap. The exponent of in the query complexity is now known to be .
There is an interesting contrast between and here. An -variable Boolean function has values, but testing monotonicity does not require anything remotely close to reading the full truth table. Roughly queries suffice, apart from logarithmic factors, and the new theorem says that no randomized algorithm can reduce the exponent below , even if it is allowed to choose every new query after seeing all previous answers.