Evasiveness conjecture for monotone transitive Boolean functions

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 xiyix_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.

Sources & referencesView supporting material

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.