University:
Massachusetts Institute of Technology
Course:
18.218 | Topics in Combinatorics: Analysis of Boolean Functions
Academic year:

2021
Views:

358

Pages:

4
Author:

Marvin Harrington

18.218 Topics in Combinatorics Spring 2021 – Lecture 6 In this lecture, we will present more advanced applications of the hypercontractive inequality. 1 The FKN theorem Recall that in the homework assignment, you have seen that degree 1 Boolean functions must be a dictatorship or an anti-dictatorship. The following theorem is a stability-version of that statement, showing that Boolean functions that are close to being degree 1 are close to dictatorships or anti-dictatorships. Theorem 1.1. Suppose a function f : {−1, 1}n → {−1, 1} is ε-close to a degree 1 function in `22 , i.e. kf − f =1 k22 6 ε. Then, there exists bi ∈ {−1, 1} and i ∈ [n] such that kf − bi xi k2 = O(ε). Proof. Let `(x) = f =1 (x) = n P ai xi . Expanding, we see that i=1 2 `(x) = n X a2i + 2 X i=1 Therefore, var(`2 ) =4 P i 1 − ε. P Letting h(x) = `2 (x) − E `2 = ai aj xi xj , we have var(`2 ) = khk22 , and our goal i6=j is to bound the 2-norm of h. By the 1-norm trick, as h is a degree 2 function khk2 6 9khk1 , and computing √ √ khk1 6 k`2 − f 2 k1 + E `2 − 1 6 k` − f k2 k` + f k2 + ε 6 ε2 + ε 6 3 ε. √ Thus, khk2 6 27 ε. Finishing the proof. Staring now at var(`2 ) = n P i=1 √ 2 a2i 2 − n P i=1 2 (27 ε) > (1 − ε) − n X i=1 a4i , we get that a4i , so n P i=1 a4i > 1 − O(ε). Thus, max a2i i and as n P i=1 n X a2i > 1 − O(ε), i=1 a2i 6 1, we get maxi a2i > 1 − O(ε). This shows that there is i? such that |ai? | > 1 − O(ε). Assume without loss of generality that ai? > 1 − O(ε); we thus get 1 − O(ε) 6 ai? = fb({i? }) = 2Pr [f (x) = xi? ] − 1, x and so Prx [f (x) = xi? ] > 1 − O(ε). Remark 1.2. An interesting question which is not fully understood asks for extensions of this theorem to degree d functions. Namely, what can one say about a degree d function that is close to Boolean? The question however is more delicate, as the precise notion of closeness depends on d, and we will not elaborate on this further for now. 2 The Fourier spectrum of small-sets Suppose S ⊆ {−1, 1}n is a small set, i.e. |S| = δ2n for a small δ. What can we say about the Fourier spectrum of 1S ? Claim 2.1. deg(1S ) > Ω(log(1/δ)). Proof. Let d be the degree of 1S . Then √ d √ d δ = k1S k22 = h1S , 1S i 6 k1S k4/3 k1S k4 6 k1S k4/3 3 k1S k2 = 3 δ 5/4 , so √ d 3 > δ −1/4 , hence d > 1√ 4 log 3 log(1/δ). While this proof is very simple, there is an even simpler argument to prove this statement based on the Schwarz-Zippel argument (which says that a degree d function on the Boolean cube must be non-zero on at least 2−d fraction of the points). However, one can adapt the above argument to say something much stronger: not only is the degree of 1S must be Ω(log(1/δ)), but in fact most of its Fourier mass lies on such levels. For technical reasons, we will prove the following slightly more general statement. Lemma 2.2. Let f : {−1, 1}n → {−1, 0, 1} be a function such that 0 < Prx [f (x) 6= 0] 6 δ. Then X fb(S)2 6 δ 24/20 . 1 |S|6 20 log(1/δ) Proof. Let d = to bound is 1 20 kf 6d k22 log(1/δ). Introducing the notation f 6d (x) = P b f (S)χS (x), our quantity of interest |S|6d P b 2 = f (S) . We do that as follows: |S|6d kf 6d k22 = hf 6d , f 6d i = hf 6d , f i 6 kf 6d k4 kf k4/3 6 √ d 3 kf 6d k2 kf k4/3 6 √ d 3 kf k2 kf k4/3 . By the premise kf k2 6 δ 1/2 and kf k4/3 6 δ 3/4 . We thus get kf 6d k22 6 ed δ 5/4 6 δ −1/20 δ 5/4 6 δ 24/20 . Note that as the overall Fourier mass of f is δ, and δ 24/20 δ for small δ, the lemma says that a (signed) indicator of a small set has almost all of its mass on the high-degrees. Remark 2.3. With a bit more effort, one may even show a bound of the form δ 2 logd (1/δ), and for some applications this quantitative difference is important; see homework assignment. 3 The KKL theorem What can we say about Boolean functions that have small average degree, i.e. I[f ] 6 Kvar(f )? Theorem 3.1. Let f : {−1, 1}n → {−1, 1} be such that I[f ] 6 Kvar(f ). Then there exists i ∈ [n] such that Ii [f ] > e−O(K) . Proof overview. Before giving the proof, we will give the rough intuition. First, as I[f ] 6 Kvar(f ) and I[f ] is the average degree, a Markov-inequality type bound shows that all but little bit of the Fourier mass of f lies on degrees O(K), and hence it makes sense to consider the low-degree part of f . We will decompose this low-degree part according to the contribution of different coordinates to it (via the derivatives), and then upper bound each one of these contributions separately using the tools we have developed so far. Since the total Fourier mass we have is roughly var(f ), the contribution of at least one of these coordinates is meaningful, and that will be the influential coordinate we are looking for. Proof. Suppose towards contradiction that Ii [f ] 6 e−C·K =: δ for all i ∈ [n], where C is an absolute constant to be determined later. Fix i, and consider the function g = ∂i f (x); note that g is −1, 0, 1 valued, and the probability it is non-zero is Ii [f ] 6 δ, so by Lemma 2.2 we have X gb(S)2 6 Ii [f ]24/20 . 1 S:|S|6 20 log(1/δ) Let us translate this now into information about the Fourier spectrum of f . If i ∈ S, gb(S) = fb(S) and otherwise it is 0, so we get that X fb(S)2 6 Ii [f ]24/20 . 1 S:|S|6 20 log(1/δ) i∈S Summing this over i, we get that X 1 S:0<|S|6 20 log(1/δ) |S| fb(S)2 6 n X Ii [f ]24/20 6 δ 1/5 I[f ] 6 δ 1/5 Kvar(f ) 6 e−CK Kvar(f ). i=1 Therefore, X C S :|S|6 20 K fb(S)2 6 δ 1/5 Kvar(f ), and on the other hand |S| fb(S)2 P X fb(S)2 6 C S :|S|> 20 K C S :|S|> 20 K 6 C 20 K I[f ] 20 6 var(f ). C C 20 K Combining the two inequalities, we get that X 20 fb(S)2 6 var(f ) + e−CK Kvar(f ) < var(f ), C S :0<|S| where the last inequality holds for appropriate C (C = 40 will do), and contradiction. As an immediate corollary, we get a more standard formulation of the KKL theorem. Corollary 3.2. For any f : {−1, 1}n → {−1, 1}, there is i ∈ [n] such that Ii [f ] > Ω logn n var(f ) . Proof. Let C > 0 be the implicit constant from Theorem 3.1, i.e. absolute C such that maxi Ii [f ] > I[f ] −C var(f ) e . If I[f ] 6 1 2C var(f ) log n, we get from Theorem 3.1 that 1 log n max Ii [f ] > e− log n/2 = √ > var(f ). i n n Otherwise, I[f ] > 1 2C var(f ) log n, and so max Ii [f ] > i 4 I[f ] 1 log n > var(f ). n 2C n Tightness of the KKL theorem The following example, called the “Tribes” function, shows that the KKL theorem as well as Friedgut’s theorem are tight. Claim 4.1. There exists f : {0, 1}n → {0, 1} with var(f ) > Ω(1) and Ii [f ] = O(log n/n) for all i ∈ [n]. Proof. Take W k,V` ∈ N such that `k 6 n, and take I1 , . . . , Ik ⊆ [n] disjoint each of size `. Define the function f (x) = kj=1 i∈Ij xi . Note that   k Y ^ E[f ] = Pr [f (x) = 1] = 1 − Pr [f (x) = 0] = 1 − Pr  xi = 0 = 1 − (1 − 2−` )k , x x j =1 i∈Ij so if we take k = 2` we will have that E[f ] is bounded away from 0 and 1, and hence var(f ) > Ω(1). Indeed, we choose k = 2` , and then the constraint on `, k turns into `2` 6 n, and it is enough to choose ` = blog n − log log nc. We finish the proof by computing the influences loss of generality V of f . Fix i, and assume without V i ∈ I1 . Note that i is influential on x if and only if q∈Ij xq = 0 for all j > 1, and q∈I1 \{i} xq = 1, so     k Y ^ ^ Pr [f (x) 6= f (x ⊕ ei )] = Pr  xq = 1 Pr  xq = 0 = 2`−1 (1 − 2−` )k−1 = Θ(log n/n). x x q∈I1 \{i} j =2 x q∈Ij

18.218 S2021 Lecture 6: The FKN Theorem and the KKL Theorem

Related Documents

Description

Related Documents

Free up your schedule!

Take 5 seconds to unlock