Prof. Mark Bun
CAS CS 591 B: Communication Complexity
Lecture Notes 16 & 17: Deterministic Lifting
Fall 2019
Reading.
• Rao-Yehudayo, Chapter 8
• Chattopadhyay-Kouchký-Lo-Mukhopadhyay,SimulationTheoremsviaPseudo-randomProp- erties
We begin a proof of a quite general deterministic lifting theorem. This lifting theorem works for any gadget g satisfying a certain pseudorandom property which we’ll call the h-hitting property. The hitting property guarantees that there are distributions over the monochromatic rectangles of g such that any large enough rectangle will intersect a random rectangle from either of these distributions with high probability.
Denition 1. A gadget g : X × Y has the h-hitting property if there exist distributions σ0 and σ1 over the sets of 0-monochromatic rectangles and 1-monochromatic rectangles of g, respectively, such that for every rectangle A × B with |A|/|X|, |B|/|Y | ≥ 2−h we have
Pr [R∩(A×B)̸=∅]≥0.99 R∼σc
for c ∈ {0, 1}.
Theorem 2 (CKLM17). Let g : X × Y be a gadget with the h-hitting property and let n ≤ 2h/2.
Then for every f : {0, 1}n → {0, 1},
Ccc(f◦gn)≥ 1 ·Cdt(f)·h.
10
Examples of gadgets with the hitting property include
• IPm has the (m/5)-hitting property.
• GHm has the (m/5)-hitting property.
• INDm has the (3 log m/20)-hitting property.
We now begin the proof of Theorem 2. The proof is constructive and uses a communication protocol Π for f ◦ gn to produce a query algorithm (decision tree) computing f(z). This query algorithm attempts to simulate the behavior of Π on inputs that are consistent with the queries to z made so far.
The query algorithm maintains a rectangle A × B ⊆ Xn × Y n. In order for the simulation to be successful, we maintain several invariants of the rectangle:
1
• The rectangle should be consistent with all coordinates of z that have been queries so far. Namely, for every (x, y) ∈ A × B we have that gi(x, y) = zi for every queried coordinate i.
• A × B is suciently rich that it is always possible to maintain the consistency requirement when further coordinates of z are queried. The technical property that captures this is the notion of thickness: The rectangle A × B is thick in coordinate i if for every (x, y) ∈ A × B, the value of g(xi,yi) can be arbitrary even given the rest of the coordinates x−i,y−i.
Formally,asetA∈Xn isτ-thickwithrespecttoSifforeveryi∈S,andalla∈AS−i, dmin(AS,i) := |x ∈ AS : xS−i = a| ≥ τ|X|.
A rectangle A × B is τ-thick if both A and B are τ-thick.
• We also work with a relaxed notion of thickness called average thickness which is enough to guarantee that simulating a step of the protocol is safe. A set A is φ-average-thick with respect to S if for every i ∈ S,
davg(AS,i) := |AS| ≥ φ|X|. |AS−i|
One way to think about thickness and average thickness is in terms of a bipartite graph with left vertices Ai, right vertices AS−i, and edges (ai, aS−i) corresponding to elements in A. Then dmin is the minimum right-degree of this graph and davg is the average right-degree of this graph.
The analysis of Algorithm relies on two main lemmas. The rst lemma says that if the current rectangle is average-thick, then it can be pruned to restore the thickness invariant while losing only a constant factor if its density.
Lemma 3 (Pruning). If A ⊆ Xn is φ-average-thick, then there is a 1 φ-thick subset A′ ⊆ A with
2n
|A′| ≥ |A|/2.
Proof. We repeatedly remove elements x ∈ A which violate the thickness condition. Let τ = 1 φ.
2n Initialize A′ = A. While there exists an i for which dmin(A′,i) < τ|X|, let a ∈ A′−i such that
|E|:=|x∈A′ :x−i =a|<τ|X|. The total number of iterations of this process is at most
Update A′ = A′ \ E.
n n|A|n|A|
|A−i| = ≤ i=1 i=1 davg(A,i)
φ|X|
The algorithm removes at most τ|X| elements in each iteration, so the total number of elements
removed is |A|/2. Hence |A′| ≥ |A|/2.
The second lemma allows us to nd a useful update of the current rectangle when we query a coordinate with low average degree. The update satises two crucial properties. First, it maintains the consistency and τ-thickness invariants of the current rectangle. Second, it increases its density. The second property allows us to argue that the number of query steps over the course of the algorithm is not too large, since Simulate and Prune steps each decrease density by only a factor of 2, and density cannot be larger than 1.
2
Algorithm 1 Decision tree algorithm T(z)
• Setparametersτ=2−h,φ=4·2−h/4
• InitializeA×B=Xn×Yn,S=[n],v=rootoftheprotocoltree
• Until v is a leaf:
If A and B are both φ-average-thick w.r.t. S:
1. Simulate the next step of the protocol moving to a new vertex v with consistent rectangle A×B.
Namely, let u0 and u1 be the children of v in the protocol tree. If it is Alice's turn to speak,choosec∈{0,1}sothat|(Ac)S|≥|AS|/2. SetthenewrectangletoAc×Band v = uc
2. Prune A × B using Lemma 3 to restore τ -thickness.
Else:
1. Query a coordinate i ∈ S for which davg(AS,i) < φ|X| or davg(BS,i) < φ|X|
2. UsetheProjectionLemma5toupdateA×B,setS=S\{i}
• Output the value at v
Denition 4. Let A×B be a rectangle and let S ⊂ [n]. The density of A×B with respect to S
is dened to be
densS(A × B) := |AS| · |BS| . |X||S| · |Y ||S|
Lemma 5 (Projection). Let g : X × Y → {0, 1} have the h-hitting property. Suppose A × B is τ-thick w.r.t. S for τ ≥ 2−h and suppose
davg(AS,i) ≤ φ|X|.
Then for c ∈ {0, 1} there exists a subrectangle A′ × B′ ⊆ A × B such that
1. g(xi,yi)=c for every (x,y)∈A′ ×B′
2. A′×B′ isτ-thickwithrespecttoS−i
3. densS−i(A′ × B′) ≥ 1 · densS(A × B). 2φ
Proof. For convenience, assume S = [n]. Fix (a, b) ∈ A−i × B−i. Let
Ua ={xi ∈X :(xi,a)∈A}, Vb ={yi ∈Y :(yi,b)∈B}.
(τ = 2−h)-thickness implies that |Ua|/|X|, |Vb|/|Y | ≥ 2−h. Then by the hitting property of g, there is a distribution σc over c-monochromatic rectangles of g for which
Pr [R∩(Ua ×Vb)̸=∅]≥0.99. R∼σc
3
Hence there exists a choice of rectangle R such that |{(a,b):R∩(Ua ×Vb)̸=∅}|≥|A−i ×B−i|/2.
LetA′×B′ ={(a,b)∈A×B:(ai,bi)∈R}. Then|A′−i×B−′ i|≥|A−i×B−i|/2. The rectangle A′ × B′ so chosen satises
dens−i(A′ × B′) = |A′−i| · |B−′ i| |X|n−1 · |Y |n−1
= 9 · |A−i| · 9 · |B−i| 10 |X|n−1 10 |Y |n−1
≥ 9 · |A|/(φ|X|) · 9 · |B|/|Y| 10 |X|n−1 10 |Y |n−1
≥ 1 ·dens(A×B). 2φ
Here, the second-to-last inequality follows because davg(A, i) = |A|/|A−i| ≤ φ|X|.
Finally, thickness is inherited from thickness of the original rectangles A × B. (Exercise.)
We are now ready to prove Theorem 2. The proof is broken into two claims: One that the number of queries is small, and one that the protocol is correct.
Claim 6. Let l be the length of the protocol Π computing f ◦ gn. Then Algorithm makes at most 10l/h queries to z.
Proof. By Lemma 5, every Query step increases densS(A × B) by a factor of 1/2φ = 2h/4−2. Meanwhile, every Simulate and Prune step decreases densS (A × B) by a factor of at most 2. Let q be the total number of queries. Since density is always at most 1 and the number of Simulate and Prune steps is at most 2l, we have
(2h/4−2)q · 22l ≤ 1 Claim 7. T(z) = f(z) for every z ∈ {0,1}n.
Proof. Consider the following thought experiment. Augment the original protocol Π to a new protocol Π′ where Alice and Bob send each other their inputs x, y at the very end. Let A × B be the rectangle reached at the end of the simulation of Π, and imagine continuing the simulation of Π′. Then the simulation reaches a rectangle A′ × B′ which is a subrectangle of A × B. Since the simulation always enforces consistency, zj = g(xj,yj) for all j ∈ [n] and (x,y) ∈ A′ × B′. Therefore, there must exist some x, y in the original rectangle A × B which is consistent with z, so Π(x, y) = f(G(x, y)) = f(z).
1 Hitting Distributions
The last ingredient is to exhibit gadgets which satisfy the hitting property. We'll only do this for the inner product gadget, but see [CKLM17] for the analysis of other gadgets.
Theorem 8. The gadget IPm has the h-hitting property for h = m/4. 4
so q ≤ 2l/(h/4 − 2) ≤ 10l/h.
Recall that the goal is to exhibit distributions σ0 and σ1 over the monochromatic rectangles of IPm which are likely to hit any suciently large rectangle. For simplicity, let us only describe the distribution σ0. (The ideas for σ1 are similar.)
To sample σ0, let V be a random subspace of Fm2 of dimension m/2. Let V ⊥ be its orthogonal complement,namelyV⊥ ={u∈Fm2 :⟨u,v⟩=0,∀v∈V}. LetthesampledrectangleRbeV ×V⊥ which by construction is 0-monochoromatic with respect to IPm.
We need to show that R sampled this way is likely to intersect any rectangle A × B with |A|,|B| ≥ 23m/4. Intuitively, a random subspace V of dimension m/2 looks like 2m/2 random points. So the expected size of V ∩ A should be |A| · 2−m/2 ≥ 2m/4 and moreover, concentrate around this with high probability. (And similarly for B.)
Let's do the calculation. Assume 0 ∈/ A; otherwise we are done since 0 ∈ V . Let W = |V ∩ A|. Then we can express W as a sum of indicator random variables W = x∈A Wx where Wx = 1 i
x∈V. Foreachx∈Awehave
Pr[Wx = 1] = 2d/2 − 1. 2d − 1
Moreover, for each x ̸= x′ ∈ A,
Pr[W =1∧W′ =1]= 2
2d/2 − 12 2d −1
2d/2−1 x x 2d−1
2
≤
.
In other words, the random variables Wx are negatively correlated: E[WxWx′ ] ≤ E[Wx]E[Wx′ ].
This implies that
Var[W] = E[W2] − E[W]2 ≤ E Wx2 − E[Wx]2
x∈A
By Chebyshev's inequality (Pr[|X − E[X]| ≥ kVar[X]] ≤ 1/k2),
Pr[A∩V =∅]≤Pr[|W −E[W]≥E[W]]
Similarly, we can argue that Pr[B ∩ V ⊥ = ∅] ≤ 2−m/4. Taking a union bound concludes the proof.
1 E[W ]
≤
≤ 2−m/4.
≤ E[W]
5