Sensitivity conjecture

Conjectureopen

In computational complexity, the sensitivity theorem, proved by Hao Huang in 2019, states that the sensitivity of a Boolean function f ⁣:{0,1}n{0,1}f\colon \{0,1\}^{n}\to \{0,1\} is at least the square root of its degree, thus settling a conjecture posed by Nisan and Szegedy in 1992. The proof is notably succinct, given that prior progress had been limited.

posted by Wikipedia source: Wikipedia

0 Replies


Sign in to reply.