Difference between revisions
sensitivity-conjecture
Status and infobox
- status:
—→ solved - tier:
—→ V3 - kind:
—→ problem - year:
—→ 1992 - statement:
—→ The sensitivity of a Boolean function is polynomially related to its other complexity measures, such as block sensitivity.
Source +21 −0
+---
+title: Sensitivity conjecture
+kind: problem
+status: solved
+tier: V3
+year: 1992
+authors: Noam Nisan and Mario Szegedy
+statement: The sensitivity of a Boolean function is polynomially related to its other complexity measures, such as block sensitivity.
+space: complexity
+---
+Thirty years of partial results ended with a two-page proof using an ingenious signed adjacency matrix of the hypercube. Scott Aaronson called it one of the most beautiful proofs he had seen. Huang's argument is short enough to formalize quickly.
+
+*Evidence tier V3 is the import default for a result the curation records as settled in the published record. No formal proof or certificate is attached to this page yet.*
+
+Posed 1992, Noam Nisan and Mario Szegedy. Closed 2019, Hao Huang.
+
+## Sources
+
+- [Wikipedia: Sensitivity theorem](https://en.wikipedia.org/wiki/Sensitivity_theorem)
+
+[[Space:complexity|Complexity classes]] · [[Continent:computation|Computation]]
Revision 61 as rendered
Thirty years of partial results ended with a two-page proof using an ingenious signed adjacency matrix of the hypercube. Scott Aaronson called it one of the most beautiful proofs he had seen. Huang's argument is short enough to formalize quickly.
Evidence tier V3 is the import default for a result the curation records as settled in the published record. No formal proof or certificate is attached to this page yet.
Posed 1992, Noam Nisan and Mario Szegedy. Closed 2019, Hao Huang.