Misplaced Pages

Sensitivity theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Theorem about complexity measures of Boolean functions

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 } {\displaystyle 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.

Background

Several papers in the late 1980s and early 1990s showed that various decision tree complexity measures of Boolean functions are polynomially related, meaning that if α ( f ) , β ( f ) {\displaystyle \alpha (f),\beta (f)} are two such measures then α ( f ) ≤ C β ( f ) C {\displaystyle \alpha (f)\leq C\beta (f)^{C}} for some constant C > 0 {\displaystyle C>0} . Nisan and Szegedy showed that degree and approximate degree are also polynomially related to all these measures. Their proof went via yet another complexity measure, block sensitivity, which had been introduced by Nisan. Block sensitivity generalizes a more natural measure, (critical) sensitivity, which had appeared before.

Nisan and Szegedy asked whether block sensitivity is polynomially bounded by sensitivity (the other direction is immediate since sensitivity is at most block sensitivity). This is equivalent to asking whether sensitivity is polynomially related to the various decision tree complexity measures, as well as to degree, approximate degree, and other complexity measures which have been shown to be polynomially related to these along the years. This became known as the sensitivity conjecture.

Along the years, several special cases of the sensitivity conjecture were proven. The sensitivity theorem was finally proven in its entirety by Huang, using a reduction of Gotsman and Linial.

Statement

Every Boolean function f : { 0 , 1 } n → { 0 , 1 } {\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}} can be expressed in a unique way as a multilinear polynomial. The degree of f {\displaystyle f} is the degree of this unique polynomial, denoted deg ⁡ ( f ) {\displaystyle \deg(f)} .

The sensitivity of the Boolean function f {\displaystyle f} at the point x ∈ { 0 , 1 } n {\displaystyle x\in \{0,1\}^{n}} is the number of indices i ∈ [ n ] {\displaystyle i\in } such that f ( x ⊕ i ) ≠ f ( x ) {\displaystyle f(x^{\oplus i})\neq f(x)} , where x ⊕ i {\displaystyle x^{\oplus i}} is obtained from x {\displaystyle x} by flipping the i {\displaystyle i} 'th coordinate. The sensitivity of f {\displaystyle f} is the maximum sensitivity of f {\displaystyle f} at any point x ∈ { 0 , 1 } n {\displaystyle x\in \{0,1\}^{n}} , denoted s ( f ) {\displaystyle s(f)} .

The sensitivity theorem states that

s ( f ) ≥ deg ⁡ ( f ) . {\displaystyle s(f)\geq {\sqrt {\deg(f)}}.}

In the other direction, Tal, improving on an earlier bound of Nisan and Szegedy, showed that

s ( f ) ≤ deg ⁡ ( f ) 2 . {\displaystyle s(f)\leq \deg(f)^{2}.}

The sensitivity theorem is tight for the AND-of-ORs function:

⋀ i = 1 m ⋁ j = 1 m x i j {\displaystyle \bigwedge _{i=1}^{m}\bigvee _{j=1}^{m}x_{ij}}

This function has degree m 2 {\displaystyle m^{2}} and sensitivity m {\displaystyle m} .

Proof

Let f : { 0 , 1 } n → { 0 , 1 } {\displaystyle f\colon \{0,1\}^{n}\to \{0,1\}} be a Boolean function of degree d {\displaystyle d} . Consider any maxonomial of f {\displaystyle f} , that is, a monomial of degree d {\displaystyle d} in the unique multilinear polynomial representing f {\displaystyle f} . If we substitute an arbitrary value in the coordinates not mentioned in the monomial then we get a function F {\displaystyle F} on d {\displaystyle d} coordinates which has degree d {\displaystyle d} , and moreover, s ( f ) ≥ s ( F ) {\displaystyle s(f)\geq s(F)} . If we prove the sensitivity theorem for F {\displaystyle F} then it follows for f {\displaystyle f} . So from now on, we assume without loss of generality that f {\displaystyle f} has degree n {\displaystyle n} .

Define a new function g : { 0 , 1 } n → { 0 , 1 } {\displaystyle g\colon \{0,1\}^{n}\to \{0,1\}} by

g ( x 1 , … , x n ) = f ⊕ x 1 ⊕ ⋯ ⊕ x n . {\displaystyle g(x_{1},\dots ,x_{n})=f\oplus x_{1}\oplus \cdots \oplus x_{n}.}

It can be shown that since f {\displaystyle f} has degree n {\displaystyle n} then g {\displaystyle g} is unbalanced (meaning that | g − 1 ( 0 ) | ≠ | g − 1 ( 1 ) | {\displaystyle |g^{-1}(0)|\neq |g^{-1}(1)|} ), say | g − 1 ( 1 ) | > 2 n − 1 {\displaystyle |g^{-1}(1)|>2^{n-1}} . Consider the subgraph G {\displaystyle G} of the hypercube (the graph on { 0 , 1 } n {\displaystyle \{0,1\}^{n}} in which two vertices are connected if they differ by a single coordinate) induced by S = g − 1 ( 1 ) {\displaystyle S=g^{-1}(1)} . In order to prove the sensitivity theorem, it suffices to show that G {\displaystyle G} has a vertex whose degree is at least n {\displaystyle {\sqrt {n}}} . This reduction is due to Gotsman and Linial.

Huang constructs a signing of the hypercube in which the product of the signs along any square is − 1 {\displaystyle -1} . This means that there is a way to assign a sign to every edge of the hypercube so that this property is satisfied. The same signing had been found earlier by Ahmadi et al., which were interested in signings of graphs with few distinct eigenvalues.

Let A {\displaystyle A} be the signed adjacency matrix corresponding to the signing. The property that the product of the signs in every square is − 1 {\displaystyle -1} implies that A 2 = n I {\displaystyle A^{2}=nI} , and so half of the eigenvalues of A {\displaystyle A} are n {\displaystyle {\sqrt {n}}} and half are − n {\displaystyle -{\sqrt {n}}} . In particular, the eigenspace of n {\displaystyle {\sqrt {n}}} (which has dimension 2 n − 1 {\displaystyle 2^{n-1}} ) intersects the space of vectors supported by S {\displaystyle S} (which has dimension > 2 n − 1 {\displaystyle >2^{n-1}} ), implying that there is an eigenvector v {\displaystyle v} of A {\displaystyle A} with eigenvalue n {\displaystyle {\sqrt {n}}} which is supported on S {\displaystyle S} . (This is a simplification of Huang's original argument due to Shalev Ben-David.)

Consider a point x ∈ S {\displaystyle x\in S} maximizing | v x | {\displaystyle |v_{x}|} . On the one hand, A v = n v {\displaystyle Av={\sqrt {n}}v} . On the other hand, A v {\displaystyle Av} is at most the sum of absolute values of all neighbors of x {\displaystyle x} in S {\displaystyle S} , which is at most deg G ⁡ ( x ) ⋅ | v x | {\displaystyle \deg _{G}(x)\cdot |v_{x}|} . Hence deg G ⁡ ( x ) ≥ n {\displaystyle \deg _{G}(x)\geq {\sqrt {n}}} .

Constructing the signing

Huang constructed the signing recursively. When n = 1 {\displaystyle n=1} , we can take an arbitrary signing. Given a signing σ n {\displaystyle \sigma _{n}} of the n {\displaystyle n} -dimensional hypercube Q n {\displaystyle Q_{n}} , we construct a signing of Q n + 1 {\displaystyle Q_{n+1}} as follows. Partition Q n + 1 {\displaystyle Q_{n+1}} into two copies of Q n {\displaystyle Q_{n}} . Use σ n {\displaystyle \sigma _{n}} for one of them and − σ n {\displaystyle -\sigma _{n}} for the other, and assign all edges between the two copies the sign 1 {\displaystyle 1} .

The same signing can also be expressed directly. Let ( x , y ) {\displaystyle (x,y)} be an edge of the hypercube. If i {\displaystyle i} is the first coordinate on which x , y {\displaystyle x,y} differ, we use the sign ( − 1 ) x 1 + ⋯ + x i − 1 {\displaystyle (-1)^{x_{1}+\cdots +x_{i-1}}} .

Extensions

The sensitivity theorem can be equivalently restated as

deg ⁡ ( f ) ≤ s ( f ) 2 . {\displaystyle \deg(f)\leq s(f)^{2}.}

Laplante et al. refined this to

deg ⁡ ( f ) ≤ s 0 ( f ) s 1 ( f ) , {\displaystyle \deg(f)\leq s_{0}(f)s_{1}(f),}

where s b ( f ) {\displaystyle s_{b}(f)} is the maximum sensitivity of f {\displaystyle f} at a point in f − 1 ( b ) {\displaystyle f^{-1}(b)} . They showed furthermore that this bound is attained at two neighboring points of the hypercube.

Aaronson, Ben-David, Kothari and Tal defined a new measure, the spectral sensitivity of f {\displaystyle f} , denoted λ ( f ) {\displaystyle \lambda (f)} . This is the largest eigenvalue of the adjacency matrix of the sensitivity graph of f {\displaystyle f} , which is the subgraph of the hypercube consisting of all sensitive edges (edges connecting two points x , y {\displaystyle x,y} such that f ( x ) ≠ f ( y ) {\displaystyle f(x)\neq f(y)} ). They showed that Huang's proof can be decomposed into two steps:

  • deg ⁡ ( f ) ≤ λ ( f ) 2 {\displaystyle \deg(f)\leq \lambda (f)^{2}} .
  • λ ( f ) ≤ s ( f ) {\displaystyle \lambda (f)\leq s(f)} .

Using this measure, they proved several tight relations between complexity measures of Boolean functions: deg ⁡ ( f ) = O ( Q ( f ) 2 ) {\displaystyle \deg(f)=O(Q(f)^{2})} and D ( f ) = O ( Q ( f ) 4 ) {\displaystyle D(f)=O(Q(f)^{4})} . Here D ( f ) {\displaystyle D(f)} is the deterministic query complexity and Q ( f ) {\displaystyle Q(f)} is the quantum query complexity.

Dafni et al. extended the notions of degree and sensitivity to Boolean functions on the symmetric group and on the perfect matching association scheme, and proved analogs of the sensitivity theorem for such functions. Their proofs use a reduction to Huang's sensitivity theorem.

See also

Notes

  1. ^ Huang 2019.
  2. ^ Nisan & Szegedy 1994.
  3. Klarreich 2019.
  4. Blum & Impagliazzo 1987.
  5. Hartmanis & Hemachandra 1991.
  6. Tardos 1989.
  7. ^ Nisan 1991.
  8. Wegener 1987, pp. 373–410.
  9. Cook, Dwork & Reischuk 1986.
  10. Simon 1983, pp. 439–444.
  11. Nisan & Szegedy 1994, p. 311.
  12. Buhrman & de Wolf 2002.
  13. Hatami, Kulkarni & Pankratov 2011.
  14. Bafna et al. 2016.
  15. C. S. et al. 2016.
  16. ^ Gotsman & Linial 1992.
  17. Tal 2013, pp. 441–454.
  18. Hatami, Kulkarni & Pankratov 2011, Example 5.2.
  19. Ahmadi et al. 2013.
  20. Ben-David 2019.
  21. Laplante et al. 2023.
  22. Aaronson et al. 2021, pp. 1330–1342.
  23. Dafni et al. 2021.

References

Category: