Evasiveness conjecture for monotone transitive Boolean functions

About 6 years old · traced to

A Boolean function is a function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}. Its decision-tree complexity D(f)D(f) is the minimum number of input bits an adaptive algorithm must query to determine ff, and ff is evasive when D(f)=nD(f)=n. The function is monotone if f(x1,…,xn)≤f(y1,…,yn)f(x_1,\ldots,x_n)\leq f(y_1,\ldots,y_n) whenever xi≤yix_i\leq y_i for every ii, and transitive if its symmetry group acts transitively on the coordinates. Evasiveness conjecture. Every non-constant monotone, transitive Boolean function is evasive.

References

Primary source

Klas Markström and Trevor Pinto, “Random Uniform and Pure Random Simplicial Complexes”, arXiv:2001.01933 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.