ECCC-Report TR20-002https://eccc.weizmann.ac.il/report/2020/002Comments and Revisions published for TR20-002en-usSun, 12 Jan 2020 07:01:29 +0200
Paper TR20-002
| Sensitivity lower bounds from linear dependencies |
Sophie Laplante,
Reza Naserasr,
Anupa Sunny
https://eccc.weizmann.ac.il/report/2020/002Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least the square root of n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we show how to derive a proof of Huangâ€™s result using only linear dependency and independence of vectors associated with the vertices of the hypercube. Our approach leads to several improvements of the result. In particular we prove that in any induced subgraph of the hypercube with more than half the number of vertices, there are two vertices, one of odd parity and the other of even parity, each with at least n vertices at distance at most 2. As an application we show that for any Boolean function f, the polynomial degree of f is bounded above by the product of the 0- and 1-sensitivities, a strictly stronger statement which implies the sensitivity conjecture.Sun, 12 Jan 2020 07:01:29 +0200https://eccc.weizmann.ac.il/report/2020/002