Nisan–Szegedy's sensitivity conjecture for Boolean functions

Let ff be a Boolean function. Write s(f)s(f) for its sensitivity and bs(f)bs(f) for its block sensitivity, the maximum number of pairwise disjoint blocks of input variables whose simultaneous flips change the value of ff.

Nisan–Szegedy's sensitivity conjecture. There exists an absolute constant C>0C>0 such that, for every Boolean function ff,

bs(f)s(f)C.bs(f)\leq s(f)^C.

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

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.