Nisan–Szegedy's sensitivity conjecture for Boolean functions
Nisan–Szegedy's sensitivity conjecture for Boolean functions
Let be a Boolean function. Write for its sensitivity and for its block sensitivity, the maximum number of pairwise disjoint blocks of input variables whose simultaneous flips change the value of .
Nisan–Szegedy's sensitivity conjecture. There exists an absolute constant such that, for every Boolean function ,
The conjecture asks whether sensitivity is polynomially related to the other standard complexity measures of Boolean functions. The supplied context says that Hao's result directly resolves it, so the conjecture is solved.
Sources & referencesView supporting material
Primary source
Rohan Karthikeyan, Siddharth Sinha and Vallabh Patil, “On the resolution of the sensitivity conjecture”, arXiv:1912.05406 (2020).
Additional references
2 papers in this index state this conjecture (2019). The statement above is taken from the most recent of them; the others are arXiv:1907.00847.
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.