REVIEW 4 cited by
Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
In this paper, we show that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $\sqrt{n}$. This result is best possible, and improves a logarithmic lower bound shown by Chung, F\"uredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.
Forward citations
Cited by 4 Pith papers
-
Block Sensitivity can exceed Spectral Sensitivity Squared
A total Boolean function on 2,017,584 variables has block sensitivity at least λ^{2.127}, with λ the spectral sensitivity, so bs is not O(λ²).
-
Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
For every total Boolean function, the logs of exact and approximate De Morgan sparsity (and of exact and approximate l1 norm) are polynomially related up to a log n factor, resolving a 2021 conjecture.
-
A New Definition of the Dimension of Graphs
The paper introduces a new graph invariant called dimension and claims a relationship between that dimension and the chromatic number.
-
Majorana fermions and the Sensitivity Conjecture
Huang's pseudo-adjacency matrix in the Sensitivity Conjecture proof is the zero-momentum Majorana operator from the Jordan-Wigner transformation.
Discussion (0). Continue with ORCID to comment.