.png){kind=icon}
.png){kind=icon}
Return
Sensitivity Conjecture and Signed Hypercubes
.png){kind=icon}
PRE
AI
DOI：10.1145/3777401.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Using spectral techniques, H. Huang proved that every subgraph of Hn, the hypercube of dimension n, induced on more than half the vertices has maximum degree at least root n. Combined with earlier work, this completed a proof of the sensitivity conjecture. In this work we show how to derive Huang's result using linear dependency and independence of vectors associated with the vertices of the hypercube. Our approach leads to several improvements of Huang's result. In particular, we prove that in any induced subgraph of Hn 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 off is bounded above by s0(f) s1(f), a statement which implies the sensitivity conjecture (but not immediately implied by the sensitivity conjecture). Using these linear dependencies, we show structural relations about the neighborhoods on the induced subgraphs at distance at most three. A key implement in Huang's proof is to assign signs (+, -) to the edges of Hn such that the product of the signs on each 4-cycle is-. With the set of negative edges being called a signature, one may observe that there are a total of 22n-1 such signatures on Hn satisfying this condition and that the symmetric difference of any two such signatures is an edge cut. A question of high interest then is to find the smallest size among all these signatures. This is known as the frustration index in the study of signed graphs. Here we provide lower and upper bounds for this parameter, observing that the two bounds match when n is a power of 4. We then establish a strong connection with other studies: On one hand with a question of Erd & odblac;s on the number of edges of a largest 4-cycle free subgraph of the hypercube. On the other hand with Ambainis functions which are used to show a separation between degree and adversary lower bounds on query complexity.
Keywords:
Boolean function
sensitivity
signed graphs
frustration index
Journal
A
IF:
0.8
Papers:
9
Citations:
0