Evasiveness conjecture for monotone transitive Boolean functions
Evasiveness conjecture for monotone transitive Boolean functions
A Boolean function is a function . Its decision-tree complexity is the minimum number of input bits an adaptive algorithm must query to determine , and is evasive when . The function is monotone if whenever for every , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.