I have prepared this talk which is a little unusual and is in part historical and speculative. You can view the slides here. I am scheduled to give it in about three hours at Boston University. And because it’s just another day in the greater Boston area, while I’ll be talking my ex officemate Vitaly Feldman will be speaking at Harvard University. His talk looks quite interesting and attempts to explain why overfitting is actually necessary for good learning. As for mine, well you’ll have to come and see or take a peek at the slides.
lecture
Nonabelian combinatorics and communication complexity
Below and here in pdf is a survey I am writing for SIGACT, due next week. Comments would be very helpful.
Finite groups provide an amazing wealth of problems of interest to complexity theory. And complexity theory also provides a useful viewpoint of grouptheoretic notions, such as what it means for a group to be “far from abelian.” The general problem that we consider in this survey is that of computing a group product over a finite group . Several variants of this problem are considered in this survey and in the literature, including in [KMR66, Bar89, BC92, IL95, BGKL03, PRS97, Amb96, AL00, Raz00, MV13, Mil14, GVa].
Some specific, natural computational problems related to are, from hardest to easiest:
(1) Computing ,
(2) Deciding if , where is the identity element of , and
(3) Deciding if under the promise that either or for a fixed .
Problem (3) is from [MV13]. The focus of this survey is on (2) and (3).
We work in the model of communication complexity [Yao79], with which we assume familiarity. For background see [KN97, RY19]. Briefly, the terms in a product will be partitioned among collaborating parties – in several ways – and we shall bound the number of bits that the parties need to exchange to solve the problem.
Organization.
We begin in Section 2 with twoparty communication complexity. In Section 3 we give a streamlined proof, except for a step that is only sketched, of a result of Gowers and the author [GV15, GVb] about interleaved group products. In particular we present an alternative proof, communicated to us by Will Sawin, of a lemma from [GVa]. We then consider two models of threeparty communication. In Section 4 we consider numberinhand protocols, and we relate the communication complexity to socalled quasirandom groups [Gow08, BNP08]. In Section 6 we consider numberinhand protocols, and specifically the problem of separating deterministic and randomized communication. In Section 7 we give an exposition of a result by Austin [Aus16], and show that it implies a separation that matches the stateoftheart [BDPW10] but applies to a different problem.
Some of the sections follow closely a set of lectures by the author [Vio17]; related material can also be found in the blog posts [Vioa, Viob]. One of the goals of this survey is to present this material in a more organized matter, in addition to including new material.
2 Two parties
Let be a group and let us start by considering the following basic communication task. Alice gets an element and Bob gets an element and their goal is to check if . How much communication do they need? Well, is equivalent to . Because Bob can compute without communication, this problem is just a rephrasing of the equality problem, which has a randomized protocol with constant communication. This holds for any group.
The same is true if Alice gets two elements and and they need to check if . Indeed, it is just checking equality of and , and again Alice can compute the latter without communication.
Things get more interesting if both Alice and Bob get two elements and they need to check if the interleaved product of the elements of Alice and Bob equals , that is, if
Now the previous transformations don’t help anymore. In fact, the complexity depends on the group. If it is abelian then the elements can be reordered and the problem is equivalent to checking if . Again, Alice can compute without communication, and Bob can compute without communication. So this is the same problem as before and it has a constant communication protocol.
For nonabelian groups this reordering cannot be done, and the problem seems hard. This can be formalized for a class of groups that are “far from abelian” – or we can take this result as a definition of being far from abelian. One of the groups that works best in this sense is the following, first constructed by Galois in the 1830’s.
Definition 1. The special linear group is the group of invertible matrices over the field with determinant .
The following result was asked in [MV13] and was proved in [GVa].
Theorem 1. Let and let . Suppose Alice receives and Bob receives . They are promised that either equals or . Deciding which case it is requires randomized communication .
This bound is tight as Alice can send her input, taking bits. We present the proof of this theorem in the next section.
Similar results are known for other groups as well, see [GVa] and [Sha16]. For example, one group that is “between” abelian groups and is the following.
If we work over instead of in Theorem 1 then the communication complexity is [Sha16]. The latter bound is tight [MV13]: with knowledge of , the parties can agree on an element such that . Hence they only need to keep track of the image . This takes communication because In more detail, the protocol is as follows. First Bob sends . Then Alice sends . Then Bob sends and finally Alice can check if .
Interestingly, to decide if without the promise a stronger lower bound can be proved for many groups, including , see Corollary 3 below.
In general, it seems an interesting open problem to try to understand for which groups Theorem 1 applies. For example, is the communication large for every quasirandom group [Gow08]?
Theorem 1 and the corresponding results for other groups also scale with the length of the product: for example deciding if over requires communication which is tight.
A strength of the above results is that they hold for any choice of in the promise. This makes them equivalent to certain results, discussed below in Section 5.0.1. Next we prove two other lower bounds that do not have this property and can be obtained by reduction from disjointness. First we show that for any nonabelian group there exists an element such that deciding if or requires communication linear in the length of the product. Interestingly, the proof works for any nonabelian group. The choice of is critical, as for some and the problem is easy. For example: take any group and consider where is the group of integers with addition modulo . Distinguishing between and amounts to computing the parity of (the components of) the input, which takes constant communication.
Theorem 2. Let be a nonabelian group. There exists such that the following holds. Suppose Alice receives and receives . They are promised that either equals or . Deciding which case it is requires randomized communication .
Proof. We reduce from unique setdisjointness, defined below. For the reduction we encode the And of two bits as a group product. This encoding is similar to the famous puzzle that asks to hang a picture on a wall with two nails in such a way that the picture falls if either one of the nails is removed. Since is nonabelian, there exist such that , and in particular with . We can use this fact to encode the And of and as
In the disjointness problem Alice and Bob get inputs respectively, and they wish to check if there exists an such that . If you think of as characteristic vectors of sets, this problem is asking if the sets have a common element or not. The communication of this problem is [KS92, Raz92]. Moreover, in the “unique” variant of this problem where the number of such ’s is 0 or 1, the same lower bound still applies. This follows from [KS92, Raz92] – see also Proposition 3.3 in [AMS99]. For more on disjointness see the surveys [She14, CP10].
We will reduce unique disjointness to group products. For we produce inputs for the group problem as follows:
The group product becomes
If there isn’t an such that , then for each the term is , and thus the whole product is 1.
Otherwise, there exists a unique such that and thus the product will be , with being in the th position. If Alice and Bob can check if the above product is equal to 1, they can also solve the unique set disjointness problem, and thus the lower bound applies for the former.
We required the uniqueness property, because otherwise we might get a product that could be equal to 1 in some groups.
Next we prove a result for products of length just ; it applies to nonabelian groups of the form and not with the promise.
Theorem 3. Let be a nonabelian group and consider . Suppose Alice receives and Bob receives . Deciding if requires randomized communication .
Proof. The proof is similar to the proof of Theorem 2. We use coordinate of to encode bit of the disjointness instance. If there is no intersection in the latter, the product will be . Otherwise, at least some coordinate will be .
As a corollary we can prove a lower bound for .
Corollary 3. Theorem 3 holds for .
Proof. Note that contains and that is not abelian. Apply Theorem 3.
Theorem 3 is tight for constantsize . We do not know if Corollary 3 is tight. The trivial upper bound is .
3 Proof of Theorem 1
Several related proofs of this theorem exist, see [GV15, GVa, Sha16]. As in [GVa], the proof that we present can be broken down in three steps. First we reduce the problem to a statement about conjugacy classes. Second we reduce this to a statement about trace maps. Third we prove the latter. We present the first step in a way that is similar but slightly different from the presentation in [GVa]. The second step is only sketched, but relies on classical results about and can be found in [GVa]. For the third we present a proof that was communicated to us by Will Sawin. We thank him for his permission to include it here.
3.1 Step 1
We would like to rule out randomized protocols, but it is hard to reason about them directly. Instead, we are going to rule out deterministic protocols on random inputs. First, for any group element we define the distribution on quadruples , where are uniformly random elements. Note the product of the elements in is always .
Towards a contradiction, suppose we have a randomized protocol such that
This implies a deterministic protocol with the same gap, by fixing the randomness.
We reach a contradiction by showing that for every deterministic protocol using little communication, we have
We start with the following standard lemma, which describes a protocol using product sets.
Lemma 4. (The set of accepted inputs of) A deterministic bit protocol for a function can be written as a disjoint union of rectangles, where a rectangle is a set of the form with and and where is constant.
Proof. (sketch) For every communication transcript , let be the set of inputs giving transcript . The sets are disjoint since an input gives only one transcript, and their number is : one for each communication transcript of the protocol. The rectangle property can be proven by induction on the protocol tree.
Next, we show that any rectangle cannot distinguish . The way we achieve this is by showing that for every the probability that is roughly the same for every , and is roughly the density of the rectangle. (Here we write for the characteristic function of the set .) Without loss of generality we set . Let have density and have density . We aim to bound above
where note the distribution of is the same as .
Because the distribution of is uniform in , the above can be rewritten as
The inequality is CauchySchwarz, and the step after that is obtained by expanding the square and noting that is uniform in , so that the expectation of the term is .
Now we do several transformations to rewrite the distribution in the last expectation in a convenient form. First, rightmultiplying by we can rewrite the distribution as the uniform distribution on tuples such that
The last equation is equivalent to .
We can now do a transformation setting to be to rewrite the distribution of the fourtuple as
where we use to denote a uniform element from the conjugacy class of , that is for a uniform .
Hence it is sufficient to bound
where all the variables are uniform and independent.
With a similar derivation as above, this can be rewritten as
Here each occurrence of denotes a uniform and independent conjugate. Hence it is sufficient to bound
We can now replace with Because has the same distribution of , it is sufficient to bound
For this, it is enough to show that with high probability over and , the distribution of , over the choice of the two independent conjugates, has statistical distance from uniform.
3.2 Step 2
In this step we use information on the conjugacy classes of the group to reduce the latter task to one about the equidistribution of the trace map. Let be the Trace map:
We state the lemma that we want to show.
Lemma 5. Let and . For all but values of and , the distribution of
is close to uniform over in statistical distance.
To give some context, in the conjugacy class of an element is essentially determined by the trace. Moreover, we can think of and as generic elements in . So the lemma can be interpreted as saying that for typical , taking a uniform element from the conjugacy class of and multiplying it by yields an element whose conjugacy class is uniform among the classes of . Using that essentially all conjugacy classes are equal, and some of the properties of the trace map, one can show that the above lemma implies that for typical the distribution of is close to uniform. For more on how this fits we refer the reader to [GVa].
3.3 Step 3
We now present a proof of Lemma 5. The highlevel argument of the proof is the same as in [GVa] (Lemma 5.5), but the details may be more accessible and in particular the use of the LangWeil theorem [LW54] from algebraic geometry is replaced by a more elementary argument. For simplicity we shall only cover the case where is prime. We will show that for all but values of , the probability over that is within of , and for the others it is at most . Summing over gives the result.
We shall consider elements whose trace is unique to the conjugacy class of . (This holds for all but conjugacy classes – see for example [GVa] for details.) This means that the distribution of is that of a uniform element in conditioned on having trace . Hence, we can write the probability that as the number of solutions in to the following three equations (divided by the size of the group, which is ):
We use the second one to remove and the first one to remove from the last equation. This gives
This is an equation in two variables. Write and and use distributivity to rewrite the equation as
At least since Lagrange it has been known how to reduce this to a Pell equation . This is done by applying an invertible affine transformation, which does not change the number of solutions. First set . Then the equation becomes
Equivalently, the crossterm has disappeared and we have
Now one can add constants to and to remove the linear terms, changing the constant term. Specifically, let and set and . The equation becomes
The linear terms disappear, the coefficients of and do not change and the equation can be rewritten as
So this is now a Pell equation
where and
For all but values of we have that is nonzero. Moreover, for all but values of the term is a nonzero polynomial in . (Specifically, for any and any such that .) So we only consider the values of that make it nonzero. Those where give solutions, which is fine. We conclude with the following lemma.
Lemma 6. For and nonzero, and prime , the number of solutions over to the Pell equation
is within of .
This is a basic result from algebraic geometry that can be proved from first principles.
Proof. If for some , then we can replace with and we can count instead the solutions to the equation
Because we can set and , which preserves the number of solutions, and rewrite the equation as
Because , this has solutions: for every nonzero we have .
So now we can assume that for any . Because the number of squares is , the range of has size . Similarly, the range of also has size . Hence these two ranges intersect, and there is a solution .
We take a line passing through : for parameters we consider pairs . There is a bijection between such pairs with and the points with . Because the number of solutions with is , using that , it suffices to count the solutions with .
The intuition is that this line has two intersections with the curve . Because one of them, , lies in , the other has to lie as well there. Algebraically, we can plug the pair in the expression to obtain the equivalent equation
Using that is a solution this becomes
We can divide by . Obtaining
We can now divide by which is nonzero by the assumption . This yields
Hence for every value of there is a unique giving a solution. This gives solutions.
4 Three parties, numberinhand
In this section we consider the following threeparty numberinhand problem: Alice gets , Bob gets , Charlie gets , and they want to know if . The communication depends on the group . We present next two efficient protocols for abelian groups, and then a communication lower bound for other groups.
4.1 A randomized protocol for the hypercube
We begin with the simplest setting. Let , that is bit strings with bitwise addition modulo 2. The parties want to check if . They can do so as follows. First, they pick a hash function that is linear: . Specifically, for a uniformly random define . Then, the protocol is as follows.
 Alice sends ,
 Bob send ,
 Charlie accepts if and only if .
The hash function outputs 1 bit, so the communication is constant. By linearity, the protocol accepts iff . If this is always the case, otherwise it happens with probability .
4.2 A randomized protocol for
This protocol is from [Vio14]. For simplicity we only consider the case here – the protocol for general is in [Vio14]. Again, the parties want to check if . For this group, there is no 100% linear hash function but there are almost linear hash functions that satisfy the following properties. Note that the inputs to are interpreted modulo and the outputs modulo .
 for all there is such that ,
 for all we have ,
 .
Assuming some random hash function that satisfies the above properties the protocol works similarly to the previous one:
 Alice sends ,
 Bob sends ,
 Charlie accepts if and only if .
We can set to achieve constant communication and constant error.
To prove correctness of the protocol, first note that for some . Then consider the following two cases:
 if then and the protocol is always correct.
 if then the probability that for some is at most the probability that which is ; so the protocol is correct with high probability.
The hash function..
For the hash function we can use a function analyzed in [DHKP97]. Let be a random odd number modulo . Define
where the product is integer multiplication, and is bitshift. In other words we output the bits of the integer product .
We now verify that the above hash function family satisfies the three properties we required above.
Property (3) is trivially satisfied.
For property (1) we have the following. Let and and . To recap, by definition we have:
 ,
 .
Notice that if in the addition the carry into the bit is , then
otherwise
which concludes the proof for property (1).
Finally, we prove property (2). We start by writing where is odd. So the binary representation of looks like
The binary representation of the product for a uniformly random looks like
We consider the two following cases for the product :
 If , or equivalently , the output never lands in the bad set ;
 Otherwise, the hash function output has uniform bits. For any set , the probability that the output lands in is at most .
4.3 Quasirandom groups
What happens in other groups? The hash function used in the previous result was fairly nontrivial. Do we have an almost linear hash function for matrices? The answer is negative. For and the problem is hard, even under the promise. For a group the complexity can be expressed in terms of a parameter which comes from representation theory. We will not formally define this parameter here, but several qualitatively equivalent formulations can be found in [Gow08]. Instead the following table shows the ’s for the groups we’ve introduced.





:  abelian  





:  





.
Theorem 1. Let be a group, and let . Let be the minimum dimension of any irreducible representation of . Suppose Alice, Bob, and Charlie receive , y, and respectively. They are promised that either equals or . Deciding which case it is requires randomized communication complexity .
This result is tight for the groups we have discussed so far. The arguments are the same as before. Specifically, for the communication is . This is tight up to constants, because Alice and Bob can send their elements. For the communication is . This is tight as well, as the parties can again just communicate the images of an element such that , as discussed in Section 1. This also gives a computational proof that cannot be too large for , i.e., it is at most . For abelian groups we get nothing, matching the efficient protocols given above.
5 Proof of Theorem 1
First we discuss several “mixing” lemmas for groups, then we come back to protocols and see how to apply one of them there.
5.0.1 mixing
We want to consider “high entropy” distributions over , and state a fact showing that the multiplication of two such distributions “mixes” or in other words increases the entropy. To define entropy we use the norms . Our notion of (non)entropy will be . Note that is exactly the collision probability where is independent and identically distributed to . The smaller this quantity, the higher the entropy of . For the uniform distribution we have and so we can think of as maximum entropy. If is uniform over elements, we have and we think of as having “high” entropy.
Because the entropy of is small, we can think of the distance between and in the 2norm as being essentially the entropy of :
Lemma 7. [Gow08, BNP08] If are independent over , then
where is the minimum dimension of an irreducible representation of .
By this lemma, for high entropy distributions and , we get . The factor allows us to pass to statistical distance using CauchySchwarz:
This is the way in which we will use the lemma.
Another useful consequence of this lemma, which however we will not use directly, is this. Suppose now you have independent, highentropy variables . Then for every we have
To show this, set without loss of generality and rewrite the lefthandside as
By CauchySchwarz this is at most
and we can conclude by Lemma 7. Hence the product of three highentropy distributions is close to uniform in a pointwise sense: each group element is obtained with roughly probability .
At least over , there exists an alternative proof of this fact that does not mention representation theory (see [GVa] and [Vioa, Viob]).
With this notation in hand, we conclude by stating a “mixing” version of Theorem 2. For more on this perspective we refer the reader to [GVa].
Theorem 1. Let . Let and be two distributions over . Suppose is independent from . Let . We have
For example, when and have high entropy over (that is, are uniform over pairs), we have , and so . In particular, is close to uniform over in statistical distance.
5.0.2 Back to protocols
As in the beginning of Section 3, for any group element we define the distribution on triples , where are uniform and independent. Note the product of the elements in is always . Again as in Section 3, it suffices to show that for every deterministic protocols using little communication we have
Analogously to Lemma 4, the following lemma describes a protocol using rectangles. The proof is nearly identical and is omitted.
Lemma 8. (The set of accepted inputs of) A deterministic bit numberinhand protocol with three parties can be written as a disjoint union of “rectangles,” that is sets of the form .
Next we show that these product sets cannot distinguish these two distributions , via a straightforward application of lemma 7.
Proof. Pick any and let be the inputs of Alice, Bob, and Charlie respectively. Then
where is uniform in . If either or is small, that is or , then also and hence (??) is at most as well. This holds for every , so we also have We will choose later.
Otherwise, and are large: and . Let be the distribution of conditioned on . We have that and are independent and each is uniform over at least elements. By Lemma 7 this implies , where is the uniform distribution. As mentioned after the lemma, by Cauchy–Schwarz we obtain
where the last inequality follows from the fact that .
This implies that and , because taking inverses and multiplying by does not change the distance to uniform. These two last inequalities imply that
and thus we get that
Picking completes the proof.
Returning to arbitrary deterministic protocols (as opposed to rectangles), write as a union of disjoint rectangles by Lemma 8. Applying Lemma 9 and summing over all rectangles we get that the distinguishing advantage of is at most . For the advantage is at most , concluding the proof.
6 Three parties, numberonforehead
In numberonforehead (NOH) communication complexity [CFL83] with parties, the input is a tuple and each party sees all of it except . For background, it is not known how to prove negative results for parties.
We mention that Theorem 1 can be extended to the multiparty setting, see [GVa]. Several questions arise here, such as whether this problem remains hard for , and what is the minimum length of an interleaved product that is hard for parties (the proof in 1 gives a large constant).
However in this survey we shall instead focus on the problem of separating deterministic and randomized communication. For , we know the optimal separation: The equality function requires communication for deterministic protocols, but can be solved using communication if we allow the protocols to use public coins. For , the best known separation between deterministic and randomized protocol is vs [BDPW10]. In the following we give a new proof of this result, for a different function: if and only if for . As is true for some functions in [BDPW10], a stronger separation could hold for . For context, let us state and prove the upper bound for randomized communication.
Proof. In the numberonforehead model, computing reduces to twoparty equality with no additional communication: Alice computes privately, then Alice and Bob check if .
To prove the lower bound for deterministic protocols we reduce the communication problem to a combinatorial problem.
For intuition, if is the abelian group of real numbers with addition, a corner becomes for , which are the coordinates of an isosceles triangle. We now state the theorem that connects corners and lower bounds.
Lemma 12. Let be a group and a real number. Suppose that every subset with contains a corner. Then the deterministic communication complexity of (defined as ) is .
It is known that implies a corner for certain abelian groups , see [LM07] for the best bound and pointers to the history of the problem. For a stronger result is known: implies a corner [Aus16]. This in turn implies communication .
Proof. We saw already twice that a numberinhand bit protocol can be written as a disjoint union of rectangles (Lemmas 4, 8). Likewise, a numberonforehead bit protocol can be written as a disjoint union of cylinder intersections for some :
The proof idea of the above fact is to consider the transcripts of , then one can see that the inputs giving a fixed transcript are a cylinder intersection.
Let be a bit protocol. Consider the inputs on which accepts. Note that at least fraction of them are accepted by some cylinder intersection . Let . Since the first two elements in the tuple determine the last, we have .
Now suppose contains a corner . Then
This implies , which is a contradiction because and so .
7 The corners theorem for quasirandom groups
In this section we prove the corners theorem for quasirandom groups, following Austin [Aus16]. Our exposition has several minor differences with that in [Aus16], which may make it more computerscience friendly. Possibly a proof can also be obtained via certain local modifications and simplifications of Green’s exposition [Gre05b, Gre05a] of an earlier proof for the abelian case. We focus on the case for simplicity, but the proof immediately extends to other quasirandom groups (with corresponding parameters).
Theorem 1. Let . Every subset of density contains a corner .
7.1 Proof idea
For intuition, suppose is a product set, i.e., for . Let’s look at the quantity
where iff . Note that the random variable in the expectation is equal to exactly when form a corner in . We’ll show that this quantity is greater than , which implies that contains a corner (where ). Since we are taking , we can rewrite the above quantity as
where the last line follows by replacing with in the uniform distribution. If , then both B/G and . Condition on , , . Then the distribution is a product of three independent distributions, each uniform on a set of density . (In fact, two distributions would suffice for this.) By Lemma 7, is close to uniform in statistical distance. This implies that the above expectation equals
for for a small enough constant . Hence, product sets of density polynomial in contain corners.
Given the above, it is natural to try to decompose an arbitrary set into product sets. We will make use of a more general result.
7.2 Weak Regularity Lemma
Let be some universe (we will take ) and let be a function (for us, ). Let be some set of functions, which can be thought of as “easy functions” or “distinguishers” (these will be rectangles or closely related to them). The next theorem shows how to decompose into a linear combination of the up to an error which is polynomial in the length of the combination. More specifically, will be indistinguishable from by the .
Lemma 13. Let be a function and a set of functions. For all , there exists a function where , and such that for all
A different way to state the conclusion, which we will use, is to say that we can write so that is small.
The lemma is due to Frieze and Kannan [FK96]. It is called “weak” because it came after Szemerédi’s regularity lemma, which has a stronger distinguishing conclusion. However, the lemma is also “strong” in the sense that Szemerédi’s regularity lemma has as a tower of whereas here we have polynomial in . The weak regularity lemma is also simpler. There also exists a proof [Tao17] of Szemerédi’s theorem (on arithmetic progressions), which uses weak regularity as opposed to the full regularity lemma used initially.
Proof. We will construct the approximation through an iterative process producing functions . We will show that decreases by each iteration.
Start: Define (which can be realized setting ).
Iterate: If not done, there exists such that . Assume without loss of generality .
Update: where shall be picked later.
Let us analyze the progress made by the algorithm.
where the last line follows by taking . Therefore, there can only be iterations because .
7.3 Getting more for rectangles
Returning to the main proof, we will use the weak regularity lemma to approximate the indicator function for arbitrary by rectangles. That is, we take to be the collection of indicator functions for all sets of the form for . The weak regularity lemma shows how to decompose into a linear combination of rectangles. These rectangles may overlap. However, we ideally want to be a linear combination of nonoverlapping rectangles. In other words, we want a partition of rectangles. It is possible to achieve this at the price of exponentiating the number of rectangles. Note that an exponential loss is necessary even if in every rectangle; or in other words in the unidimensional setting. This is one step where the terminology “rectangle” may be misleading – the set is not necessarily an interval. If it was, a polynomial rather than exponential blowup would have sufficed to remove overlaps.
Claim 14. Given a decomposition of into rectangles from the weak regularity lemma with functions, there exists a decomposition with rectangles which don’t overlap.
Proof. Exercise.
In the above decomposition, note that it is natural to take the coefficients of rectangles to be the density of points in that are in the rectangle. This gives rise to the following claim.
Claim 15. The weights of the rectangles in the above claim can be the average of in the rectangle, at the cost of doubling the error.
Consequently, we have that , where is the sum of nonoverlapping rectangles with coefficients .
Proof. Let be a partition decomposition with arbitrary weights. Let be a partition decomposition with weights being the average of . It is enough to show that for all rectangle distinguishers
By the triangle inequality, we have that
To bound , note that the error is maximized for a that respects the decomposition in nonoverlapping rectangles, i.e., is the union of some nonoverlapping rectangles from the decomposition. This can be argued using that, unlike , the value of and on a rectangle from the decomposition is fixed. But, from the point of “view” of such , ! More formally, . This gives
and concludes the proof.
We need to get still a little more from this decomposition. In our application of the weak regularity lemma above, we took the set of distinguishers to be characteristic functions of rectangles. That is, distinguishers that can be written as where and map . We will use that the same guarantee holds for and with range , up to a constant factor loss in the error. Indeed, let and have range . Write where and have range , and the same for . The error for distinguisher is at most the sum of the errors for distinguishers , , , and . So we can restrict our attention to distinguishers where and have range . In turn, a function with range can be written as an expectation for functions with range , and the same for . We conclude by observing that
7.4 Proof
Let us now finish the proof by showing a corner exists for sufficiently dense sets . We’ll use three types of decompositions for , with respect to the following three types of distinguishers, where and have range :
 ,
 ,
 .
The first type is just rectangles, what we have been discussing until now. The distinguishers in the last two classes can be visualized over as parallelograms with a 45degree angle. The same extra properties we discussed for rectangles can be verified hold for them too.
Recall that we want to show
We’ll decompose the th occurrence of via the th decomposition listed above. We’ll write this decomposition as . We apply this in a certain order to produce sums of products of three functions. The inputs to the functions don’t change, so to avoid clutter we do not write them, and it is understood that in each product of three functions the inputs are, in order . The decomposition is:
We first show that the expectation of the first term is big. This takes the next two claims. Then we show that the expectations of the other terms are small.
Proof. We just need to get error for any product of three functions for the three decomposition types. We have:
This is similar to what we discussed in the overview, and is where we use mixing. Specifically, if or are at most for a small enough constant than we are done. Otherwise, conditioned on , the distribution on is uniform over a set of density , and the same holds for , and the result follows by Lemma 7.
Recall that we start with a set of density .
Proof. We will relate the expectation over to using the Hölder inequality: For random variables ,
To apply this inequality in our setting, write
By the Hölder inequality the expectation of the righthand side is
The last three terms equal to because
where is the set in the partition that contains . Putting the above together we obtain
Finally, because the functions are positive, we have that . This concludes the proof.
It remains to show the other terms are small. Let be the error in the weak regularity lemma with respect to distinguishers with range . Recall that this implies error with respect to distinguishers with range . We give the proof for one of the terms and then we say little about the other two.
The proof involves changing names of variables and doing CauchySchwarz to remove the terms with and bound the expectation above by , which is small by the regularity lemma.
Proof. Replace with in the uniform distribution to get
where the first inequality is by CauchySchwarz.
Now replace and reason in the same way:
Replace to rewrite the expectation as
We want to view the last three terms as a distinguisher . First, note that has range . This is because and has range , where recall that is the set in the partition that contains . Fix . The last term in the expectation becomes a constant . The second term only depends on , and the third only on . Hence for appropriate functions and with range this expectation can be rewritten as
which concludes the proof.
There are similar proofs to show the remaining terms are small. For , we can perform simple manipulations and then reduce to the above case. For , we have a slightly easier proof than above.
7.4.1 Parameters
Suppose our set has density , and the error in the regularity lemma is . By the above results we can bound
where the terms in the righthand size come, lefttoright from Claim 17, 16, and 18. Picking the proof is completed for sufficiently small .
References
[AL00] Andris Ambainis and Satyanarayana V. Lokam. Imroved upper bounds on the simultaneous messages complexity of the generalized addressing function. In Latin American Symposium on Theoretical Informatics (LATIN), pages 207–216, 2000.
[Amb96] Andris Ambainis. Upper bounds on multiparty communication complexity of shifts. In Symp. on Theoretical Aspects of Computer Science (STACS), pages 631–642, 1996.
[AMS99] Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. J. of Computer and System Sciences, 58(1, part 2):137–147, 1999.
[Aus16] Tim Austin. AjtaiSzemerédi theorems over quasirandom groups. In Recent trends in combinatorics, volume 159 of IMA Vol. Math. Appl., pages 453–484. Springer, [Cham], 2016.
[Bar89] David A. Mix Barrington. Boundedwidth polynomialsize branching programs recognize exactly those languages in NC. J. of Computer and System Sciences, 38(1):150–164, 1989.
[BC92] Michael BenOr and Richard Cleve. Computing algebraic formulas using a constant number of registers. SIAM J. on Computing, 21(1):54–58, 1992.
[BDPW10] Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel. Separating deterministic from randomized multiparty communication complexity. Theory of Computing, 6(1):201–225, 2010.
[BGKL03] László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam. Communication complexity of simultaneous messages. SIAM J. on Computing, 33(1):137–166, 2003.
[BNP08] László Babai, Nikolay Nikolov, and László Pyber. Product growth and mixing in finite groups. In ACMSIAM Symp. on Discrete Algorithms (SODA), pages 248–257, 2008.
[CFL83] Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multiparty protocols. In 15th ACM Symp. on the Theory of Computing (STOC), pages 94–99, 1983.
[CP10] Arkadev Chattopadhyay and Toniann Pitassi. The story of set disjointness. SIGACT News, 41(3):59–85, 2010.
[DHKP97] Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable randomized algorithm for the closestpair problem. J. Algorithms, 25(1):19–51, 1997.
[FK96] Alan M. Frieze and Ravi Kannan. The regularity lemma and approximation schemes for dense problems. In IEEE Symp. on Foundations of Computer Science (FOCS), pages 12–20, 1996.
[Gow08] W. T. Gowers. Quasirandom groups. Combinatorics, Probability & Computing, 17(3):363–387, 2008.
[Gre05a] Ben Green. An argument of Shkredov in the finite field setting, 2005. Available at people.maths.ox.ac.uk/greenbj/papers/corners.pdf.
[Gre05b] Ben Green. Finite field models in additive combinatorics. Surveys in Combinatorics, London Math. Soc. Lecture Notes 327, 127, 2005.
[GVa] W. T. Gowers and Emanuele Viola. Interleaved group products. SIAM J. on Computing.
[GVb] W. T. Gowers and Emanuele Viola. The multiparty communication complexity of interleaved group products. SIAM J. on Computing.
[GV15] W. T. Gowers and Emanuele Viola. The communication complexity of interleaved group products. In ACM Symp. on the Theory of Computing (STOC), 2015.
[IL95] Neil Immerman and Susan Landau. The complexity of iterated multiplication. Inf. Comput., 116(1):103–116, 1995.
[KMR66] Kenneth Krohn, W. D. Maurer, and John Rhodes. Realizing complex Boolean functions with simple groups. Information and Control, 9:190–195, 1966.
[KN97] Eyal Kushilevitz and Noam Nisan. Communication complexity. Cambridge University Press, 1997.
[KS92] Bala Kalyanasundaram and Georg Schnitger. The probabilistic communication complexity of set intersection. SIAM J. Discrete Math., 5(4):545–557, 1992.
[LM07] Michael T. Lacey and William McClain. On an argument of Shkredov on twodimensional corners. Online J. Anal. Comb., (2):Art. 2, 21, 2007.
[LW54] Serge Lang and André Weil. Number of points of varieties in finite fields. American Journal of Mathematics, 76:819–827, 1954.
[Mil14] Eric Miles. Iterated group products and leakage resilience against . In ACM Innovations in Theoretical Computer Science conf. (ITCS), 2014.
[MV13] Eric Miles and Emanuele Viola. Shielding circuits with groups. In ACM Symp. on the Theory of Computing (STOC), 2013.
[PRS97] Pavel Pudlák, Vojtěch Rödl, and Jiří Sgall. Boolean circuits, tensor ranks, and communication complexity. SIAM J. on Computing, 26(3):605–633, 1997.
[Raz92] Alexander A. Razborov. On the distributional complexity of disjointness. Theor. Comput. Sci., 106(2):385–390, 1992.
[Raz00] Ran Raz. The BNSChung criterion for multiparty communication complexity. Computational Complexity, 9(2):113–122, 2000.
[RY19] Anup Rao and Amir Yehudayoff. Communication complexity. 2019. https://homes.cs.washington.edu/ anuprao/pubs/book.pdf.
[Sha16] Aner Shalev. Mixing, communication complexity and conjectures of Gowers and Viola. Combinatorics, Probability and Computing, pages 1–13, 6 2016. arXiv:1601.00795.
[She14] Alexander A. Sherstov. Communication complexity theory: Thirtyfive years of set disjointness. In Symp. on Math. Foundations of Computer Science (MFCS), pages 24–43, 2014.
[Tao17] Terence Tao. Szemerédiâs proof of Szemerédiâs theorem, 2017. https://terrytao.files.wordpress.com/2017/09/szemerediproof1.pdf.
[Vioa] Emanuele Viola. Thoughts: Mixing in groups. https://emanueleviola.wordpress.com/2016/10/21/mixingingroups/.
[Viob] Emanuele Viola. Thoughts: Mixing in groups ii. https://emanueleviola.wordpress.com/2016/11/15/mixingingroupsii/.
[Vio14] Emanuele Viola. The communication complexity of addition. Combinatorica, pages 1–45, 2014.
[Vio17] Emanuele Viola. Special topics in complexity theory. Lecture notes of the class taught at Northeastern University. Available at http://www.ccs.neu.edu/home/viola/classes/spepf17.html, 2017.
[Yao79] Andrew ChiChih Yao. Some complexity questions related to distributive computing. In 11th ACM Symp. on the Theory of Computing (STOC), pages 209–213, 1979.
Special Topics in Complexity Theory: class is over :(
I put together in a single file all the lectures given by me. On the class webpage you can also find the scribes of the two guest lectures, and the students’ presentations. Many thanks to Matthew Dippel, Xuangui Huang, Chin Ho Lee, Biswaroop Maiti, Tanay Mehta, Willy Quach, and Giorgos Zirdelis for doing an excellent job scribing these lectures. (And for giving me perfect teaching evaluations. Though I am not sure if I biased the sample. It went like this. One day I said: “Please fill the student evaluations, we need 100%.” A student said: “100% what? Participation or score?” I meant participation but couldn’t resist replying jokingly “both.”) Finally, thanks also to all the other students, postdocs, and faculty who attended the class and created a great atmosphere.
Special Topics in Complexity Theory, Lecture 19
Special Topics in Complexity Theory, Fall 2017. Instructor: Emanuele Viola
1 Lecture 19, Guest lecture by Huacheng Yu, Scribe: Matthew Dippel
Guest lecture by Huacheng Yu on dynamic data structure lower bounds, for the 2D range query and 2D range parity problems. Thanks to Huacheng for giving this lecture and for feedback on the writeup.
What is covered.
 Overview of Larsen’s lower bound for 2D range counting.
 Extending these techniques for for 2D range parity.
2 Problem definitions
Definition 1. 2D range counting
Give a data structure that maintains a weighted set of 2 dimensional points with integer coordinates, that supports the following operations:
 UPDATE: Add a (point, weight) tuple to the set.
 QUERY: Given a query point , return the sum of weights of points in the set satisfying and .
Definition 2. 2D range parity
Give a data structure that maintains an unweighted set of 2 dimensional points with integer coefficients, that supports the following operations:
 UPDATE: Add a point to the set.
 QUERY: Given a query point , return the parity of the number of points in the set satisfying and .
Both of these definitions extend easily to the dimensional case, but we state the 2D versions as we will mainly work with those.
2.1 Known bounds
All upper bounds assume the RAM model with word size .
Upper bounds: Using range trees, we can create a data structure for 2D range counting, with all update and query operations taking time time. With extra tricks, we can make this work for 2D range parity with operations running in time .
Lower bounds. There are a series of works on lower bounds:
 Fredman, Saks ’89 – 1D range parity requires .
 Patrascu, Demaine ’04 – 1D range counting requires .
 Larsen ’12 – 2D range counting requires .
 Larsen, Weinstein, Yu ’17 – 2D range parity requires .
This lecture presents the recent result of [Larsen ’12] and [Larsen, Weinstein, Yu ’17]. They both use the same general approach:
 Show that, for an efficient approach to exist, the problem must demonstrate some property.
 Show that the problem doesn’t have that property.
3 Larsen’s technique
All lower bounds are in the cell probe model with word size .
We consider a general data structure problem, where we require a structure that supports updates and queries of an unspecified nature. We further assume that there exists an efficient solution with update and query times . We will restrict our attention to operation sequences of the form . That is, a sequence of updates followed by a single query . We fix a distribution over such sequences, and show that the problem is still hard.
3.1 Chronogram method [FS89]
We divide the updates into epochs, so that our sequence becomes:
where and . The epochs are multiplicatively shrinking. With this requirement, we have that .
Let be the set of all memory cells used by the data structure when run on the sequence of updates. Further, let be the set of memory cells which are accessed by the structure at least once in , and never again in a further epoch.
Claim 2. There exists an epoch such that probes cells from when answering the query at the end. Note that this is simply our query time divided by the number of epochs. In other words, can’t afford to read cells from each set without breaking its promise on the query run time.
Claim 2 implies that there is an epoch which has the smallest effect on the final answer. We will call this the ”easy” epoch.
Idea. : The set contains ”most” information about among all memory cells in . Also, are not updated past epoch , and hence should contain no information relative to the updates in . Epochs are progressively shrinking, and so the total touched cells in during the query operation should be small.
3.2 Communication game
Having set up the framework for how to analyze the data structure, we now introduce a communication game where two parties attempt to solve an identical problem. We will show that, an efficient data structure implies an efficient solution to this communication game. If the message is smaller than the entropy of the updates of epoch (conditioned on preceding epochs), this gives an information theoretic contradiction. The trick is to find a way for the encoder to exploit the small number of probed cells to send a short message.
The game. The game consists of two players, Alice and Bob, who must jointly compute a single query after a series of updates. The model is as follows:
 Alice has all of the update epochs . She also has an index , which still corresponds to the ”easy” epoch as defined above.
 Bob has all update epochs EXCEPT for . He also has a random query . He is aware of the index .
 Communication can only occur in a single direction, from Alice to Bob.
 We assume some fixed input distribution .
 They win this game if Bob successfully computes the correct answer for the query .
Then we will show the following generic theorem, relating this communication game to data structures for the corresponding problem:
Theorem 3. If there is a data structure with update time and probes cells from in expectation when answering the final query , then the communication game has an efficient solution, with communication cost, and success probability at least . This holds for any choice of .
Before we prove the theorem, we consider specific parameters for our problem. If we pick
then, after plugging in the parameters, the communication cost is . Note that, we could always trivially achieve by having Alice send Bob all of , so that he can compute the solution of the problem with no uncertainty. The success probability is , which simplifies to . This is significantly better than , which could be achieved trivially by having Bob output a random answer to the query, independent of the updates.
Proof.
We assume we have a data structure for the update / query problem. Then Alice and Bob will proceed as follows:
Alice’s steps.
 Simulate on . While doing so, keep track of memory cell accesses and compute .
 Sample a random subset , such that .
 Send .
We note that in Alice’s Step 3, to send a cell, she sends a tuple holding the cell ID and the cell state before the query was executed. Also note that, she doesn’t distinguish to Bob which cells are in which sets of the union.
Bob’s steps.
 Receive from Alice.
 Simulate on epochs . Snapshot the current memory state of the data structure as .
 Simulate the query algorithm. Every time attempts to probe cell , Bob checks if . If it is, he lets probe from . Otherwise, he lets probe from .
 Bob returns the result from the query algorithm as his answer.
If the query algorithm does not query any cell in , then Bob succeeds, as he can exactly simulate the data structure query. Since the query will check cells in , and Bob has a random subset of them of size , then the probability that he got a subset the data structure will not probe is at least . The communication cost is the cost of Alice sending the cells to Bob, which is
4 Extension to 2D Range Parity
The extension to 2D range parity proceeds in nearly identical fashion, with a similar theorem relating data structures to communication games.
Theorem 1. Consider an arbitrary data structure problem where queries have 1bit outputs. If there exists a data structure having:
 update time
 query time
 Probes cells from when answering the last query
Then there exists a protocol for the communication game with bits of communication and success probability at least , for any choice of . Again, we plug in the parameters from 2D range parity. If we set
then the cost is , and the probability simplifies to .
We note that, if we had different queries, then randomly guessing on all of them, with constant probability we could be correct on as many as . In this case, the probability of being correct on a single one, amortized, is .
Proof. The communication protocol will be slightly adjusted. We assume an a priori distribution on the updates and queries. Bob will then compute the posterior distribution, based on what he knows and what Alice sends him. He then computes the maximum likelihood answer to the query . We thus need to figure out what Alice can send, so that the answer to is often biased towards either or .
We assume the existence of some public randomness available to both Alice and Bob. Then we adjust the communication protocol as follows:
Alice’s modified steps.
 Alice samples, using the public randomness, a subset of ALL memory cells , such that each cell is sampled with probability . Alice sends to Bob. Since Bob can mimic the sampling, he gains additional information about which cells are and aren’t in .
Bob’s modified steps.
 Denote by the set of memory cells probed by the data structure when Bob simulates the query algorithm. That is, is what Bob ”thinks” D will probe during the query, as the actual set of cells may be different if Bob had full knowledge of the updates, and the data structure may use that information to determine what to probe. Bob will use to compute the posterior distribution.
Define the function to be the ”bias” when takes on the value . In particular, this function is conditioned on that Bob receives from Alice. We can then clarify the definition of as
In particular, has the following two properties:
In these statements, the expectation is over everything that Bob knows, and the probabilities are also conditioned on everything that Bob knows. The randomness comes from what he doesn’t know. We also note that when the query probes no cells in , then the bias is always , since the a posterior distribution will put all its weight on the correct answer of the query.
Finishing the proof requires the following lemma:
Lemma 2. For any with the above two properties, there exists a such that and
Note that the sum inside the absolute values is the bias when .
References
Special Topics in Complexity Theory, Lecture 18
Special Topics in Complexity Theory, Fall 2017. Instructor: Emanuele Viola
1 Lecture 18, Scribe: Giorgos Zirdelis
In this lecture we study lower bounds on data structures. First, we define the setting. We have bits of data, stored in bits of memory (the data structure) and want to answer queries about the data. Each query is answered with probes. There are two types of probes:
 bitprobe which return one bit from the memory, and
 cellprobe in which the memory is divided into cells of bits, and each probe returns one cell.
The queries can be adaptive or nonadaptive. In the adaptive case, the data structure probes locations which may depend on the answer to previous probes. For bitprobes it means that we answer a query with depth decision trees.
Finally, there are two types of data structure problems:
 The static case, in which we map the data to the memory arbitrarily and afterwards the memory remains unchanged.
 The dynamic case, in which we have update queries that change the memory and also run in bounded time.
In this lecture we focus on the nonadaptive, bitprobe, and static setting. Some trivial extremes for this setting are the following. Any problem (i.e., collection of queries) admits data structures with the following parameters:
 and , i.e. you write down all the answers, and
 and , i.e. you can always answer a query about the data if you read the entire data.
Next, we review the best current lower bound, a bound proved in the 80’s by Siegel [Sie04] and rediscovered later. We state and prove the lower bound in a different way. The lower bound is for the problem of wise independence.
Problem 1. The data is a seed of size for a wise independent distribution over . A query is defined to be the th bit of the sample.
The question is: if we allow a little more space than seed length, can we compute such distributions fast?
Theorem 2. For the above problem with it holds that
It follows, that if then is . But if then nothing is known.
Proof. Let . We have the memory of bits and we are going to subsample it. Specifically, we will select a bit of with probability , independently.
The intuition is that we will shrink the memory but still answer a lot of queries, and derive a contradiction because of the seed length required to sample wise independence.
For the “shrinking” part we have the following. We expect to keep memory bits. By a Chernoff bound, it follows that we keep bits except with probability .
For the “answer a lot of queries” part, recall that each query probes bits from the memory. We keep one of the queries if it so happens that we keep all the bits that it probed in the memory. For a fixed query, the probability that we keep all its probes is .
We claim that with probability at least , we keep queries. This follows by Markov’s inequality. We expect to not keep queries on average. We now apply Markov’s inequality to get that the probability that we don’t keep at least queries is at most .
Thus, if , then there exists a fixed choice of memory bits that we keep, to achieve both the “shrinking” part and the “answer a lot of queries” part as above. This inequality is true because and so . But now we have bits of memory while still answering as many as queries.
The minimum seed length to answer that many queries while maintaining wise independence is . Therefore the memory has to be at least as big as the seed. This yields
from which the result follows.
This lower bound holds even if the memory bits are filled arbitrarily (rather than having entropy at most ). It can also be extended to adaptive cell probes.
We will now show a conceptually simple data structure which nearly matches the lower bound. Pick a random bipartite graph with nodes on the left and nodes on the right. Every node on the right side has degree . We answer each probe with an XOR of its neighbor bits. By the Vazirani XOR lemma, it suffices to show that any subset of at most memory bits has an XOR which is unbiased. Hence it suffices that every subset with has a unique neighbor. For that, in turn, it suffices that has a neighborhood of size greater than (because if every element in the neighborhood of has two neighbors in then has a neighborhood of size ). We pick the graph at random and show by standard calculations that it has this property with nonzero probability.
It suffices to have , so that the probability is strictly less than 1, because . We can match the lower bound in two settings:
 if for some constant , then suffices,
 and suffices.
Remark 3. It is enough if the memory is wise independent as opposed to completely uniform, so one can have . An open question is if you can improve the seed length to optimal.
As remarked earlier the lower bound does not give anything when is much larger than . In particular it is not clear if it rules out . Next we show a lower bound which applies to this case.
Problem 4. Take bits to be a seed for biased distribution over . The queries, like before, are the bits of that distribution. Recall that .
Theorem 5. You need .
Proof. Every query is answered by looking at bits. But queries are answered by the same 2bit function of probes (because there is a constant number of functions on 2bits). There are two cases for :
 is linear (or affine). Suppose for the sake of contradiction that . Then you have a linear dependence, because the space of linear functions on bits is . This implies that if you XOR those bits, you always get 0. This in turn contradicts the assumption that the distributions has small bias.
 is AND (up to negating the input variables or the output). In this case, we keep collecting queries as long as they probe at least one new memory bit. If when we stop we have a query left such that both their probes query bits that have already been queried. This means that there exist two queries and whose probes cover the probes of a third query . This in turn implies that the queries are not close to uniform. That is because there exist answers to and that fix bits probed by them, and so also fix the bits probed by . But this contradicts the small bias of the distribution.
References
Special Topics in Complexity Theory, Lectures 1617
Special Topics in Complexity Theory, Fall 2017. Instructor: Emanuele Viola
1 Lectures 1617, Scribe: Tanay Mehta
In these lectures we prove the corners theorem for pseudorandom groups, following Austin [Aus16]. Our exposition has several nonmajor differences with that in [Aus16], which may make it more computerscience friendly. The instructor suspects a proof can also be obtained via certain local modifications and simplifications of Green’s exposition [Gre05b, Gre05a] of an earlier proof for the abelian case. We focus on the case for simplicity, but the proof immediately extends to other pseudorandom groups.
Theorem 1. Let . Every subset of density contains a corner, i.e., a set of the form .
1.1 Proof Overview
For intuition, suppose is a product set, i.e., for . Let’s look at the quantity
where iff . Note that the random variable in the expectation is equal to exactly when form a corner in . We’ll show that this quantity is greater than , which implies that contains a corner (where ). Since we are taking , we can rewrite the above quantity as
where the last line follows by replacing with in the uniform distribution. If , then and . Condition on , , . Then the distribution is a product of three independent distributions, each uniform on a set of measure greater than . By pseudorandomness is close to uniform in statistical distance. This implies that the above quantity equals
Given this, it is natural to try to write an arbitrary as a combination of product sets (with some error). We will make use of a more general result.
1.2 Weak Regularity Lemma
Let be some universe (we will take ). Let be a function (for us, ). Let be some set of functions, which can be thought of as “easy functions” or “distinguishers.”
Theorem 2.[Weak Regularity Lemma] For all , there exists a function where , and such that for all
The lemma is called ‘weak’ because it came after Szemerédi’s regularity lemma, which has a stronger distinguishing conclusion. However, the lemma is also ‘strong’ in the sense that Szemerédi’s regularity lemma has as a tower of whereas here we have polynomial in . The weak regularity lemma is also simpler. There also exists a proof of Szemerédi’s theorem (on arithmetic progressions), which uses weak regularity as opposed to the full regularity lemma used initially.
Proof. We will construct the approximation through an iterative process producing functions . We will show that decreases by each iteration.
 Start: Define (which can be realized setting ).
 Iterate: If not done, there exists such that . Assume without loss of generality .
 Update: where shall be picked later.
Let us analyze the progress made by the algorithm.
where the last line follows by taking . Therefore, there can only be iterations because .
1.3 Getting more for rectangles
Returning to the lower bound proof, we will use the weak regularity lemma to approximate the indicator function for arbitrary by rectangles. That is, we take to be the collection of indicator functions for all sets of the form for . The weak regularity lemma gives us as a linear combination of rectangles. These rectangles may overlap. However, we ideally want to be a linear combination of nonoverlapping rectangles.
Claim 3. Given a decomposition of into rectangles from the weak regularity lemma with functions, there exists a decomposition with rectangles which don’t overlap.
Proof. Exercise.
In the above decomposition, note that it is natural to take the coefficients of rectangles to be the density of points in that are in the rectangle. This gives rise to the following claim.
Claim 4. The weights of the rectangles in the above claim can be the average of in the rectangle, at the cost of doubling the distinguisher error.
Consequently, we have that , where is the sum of nonoverlapping rectangles with coefficients .
Proof. Let be a partition decomposition with arbitrary weights. Let be a partition decomposition with weights being the average of . It is enough to show that for all rectangle distinguishers
By the triangle inequality, we have that
To bound , note that the error is maximized for a that respects the decomposition in nonoverlapping rectangles, i.e., is the union of some nonoverlapping rectangles from the decomposition. This can be argues using that, unlike , the value of and on a rectangle from the decomposition is fixed. But, for such , ! More formally, .
We need to get a little more from this decomposition. The conclusion of the regularity lemma holds with respect to distinguishers that can be written as where and map . We need the same guarantee for and with range . This can be accomplished paying only a constant factor in the error, as follows. Let and have range . Write where and have range , and the same for . The error for distinguisher is at most the sum of the errors for distinguishers , , , and . So we can restrict our attention to distinguishers where and have range . In turn, a function with range can be written as an expectation for functions with range , and the same for . We conclude by observing that
1.4 Proof
Let us now finish the proof by showing a corner exists for sufficiently dense sets . We’ll use three types of decompositions for , with respect to the following three types of distinguishers, where and have range :
 ,
 ,
 .
The last two distinguishers can be visualized as parallelograms with a 45degree angle between two segments. The same extra properties we discussed for rectangles hold for them too.
Recall that we want to show
We’ll decompose the th occurrence of via the th decomposition listed above. We’ll write this decomposition as . We do this in the following order:
We first show that is big (i.e., inverse polylogarithmic in expectation) in the next two claims. Then we show that the expectations of the other terms are small.
Claim 5. For all , the values are the same (over ) up to an error of .
Proof. We just need to get error for any product of three functions for the three decomposition types. By the standard pseudorandomness argument we saw in previous lectures,
Recall that we start with a set of density .
Claim 6. .
Proof. By the previous claim, we can fix . We will relate the expectation over to by a trick using the Hölder inequality: For random variables ,
To apply this inequality in our setting, write
By the Hölder inequality, we get that
Note that
where is the set in the partition that contains . Finally, by nonnegativity of , we have that . This concludes the proof.
We’ve shown that the term is big. It remains to show the other terms are small. Let be the error in the weak regularity lemma with respect to distinguishers with range .
Claim 7. .
Proof. Replace with in the uniform distribution to get
where the first inequality is by CauchySchwarz.
Now replace and reason in the same way:
Replace to rewrite the expectation as
We want to view the last three terms as a distinguisher . First, note that has range . This is because and has range .
Fix . The last term in the expectation becomes a constant . The second term only depends on , and the third only on . Hence for appropriate functions and with range this expectation can be rewritten as
which concludes the proof.
There are similar proofs to show the remaining terms are small. For , we can perform simple manipulations and then reduce to the above case. For , we have a slightly easier proof than above.
1.4.1 Parameters
Suppose our set has density . We apply the weak regularity lemma for error . This yields the number of functions . For say , we can bound from below by the same expectation with fixed to , up to an error . Then, . The expectation of terms with is less than . So the proof can be completed for all sufficiently small .
References
[Aus16] Tim Austin. AjtaiSzemerédi theorems over quasirandom groups. In Recent trends in combinatorics, volume 159 of IMA Vol. Math. Appl., pages 453–484. Springer, [Cham], 2016.
[Gre05a] Ben Green. An argument of shkredov in the finite field setting, 2005. Available at people.maths.ox.ac.uk/greenbj/papers/corners.pdf.
[Gre05b] Ben Green. Finite field models in additive combinatorics. Surveys in Combinatorics, London Math. Soc. Lecture Notes 327, 127, 2005.
Special Topics in Complexity Theory, Lecture 15
Special Topics in Complexity Theory, Fall 2017. Instructor: Emanuele Viola
1 Lecture 15, Scribe: Chin Ho Lee
In this lecture fragment we discuss multiparty communication complexity, especially the problem of separating deterministic and randomized communication, which we connect to a problem in combinatorics.
2 Numberonforehead communication complexity
In numberonforehead (NOH) communication complexity each party sees all of the input except its own input . For background, it is not known how to prove negative results for parties. We shall focus on the problem of separating deterministic and randomizes communication. For , we know the optimal separation: The equality function requires communication for deterministic protocols, but can be solved using communication if we allow the protocols to use public coins. For , the best known separation between deterministic and randomized protocol is vs [BDPW10]. In the following we give a new proof of this result, for a simpler function: if and only if for .
For context, let us state and prove the upper bound for randomized communication.
Claim 1. has randomized communication complexity .
Proof. In the NOH model, computing reduces to party equality with no additional communication: Alice computes privately, then Alice and Bob check if .
To prove a lower bound for deterministic protocols, where , we reduce the communication problem to a combinatorial problem.
Definition 2. A corner in a group is , where are arbitrary group elements and .
For intuition, consider the case when is Abelian, where one can replace multiplication by addition and a corner becomes for .
We now state the theorem that gives the lower bound.
Theorem 3. Suppose that every subset with contains a corner. Then the deterministic communication complexity of is .
It is known that when is Abelian, then implies a corner. We shall prove that when , then implies a corner. This in turn implies communication .
Proof. We saw that a numberinhand (NIH) bit protocol can be written as a disjoint union of rectangles. Likewise, a numberonforehead bit protocol can be written as a disjoint union of cylinder intersections for some :
The proof idea of the above fact is to consider the transcripts of , then one can see that the inputs giving a fixed transcript are a cylinder intersection.
Let be a bit protocol. Consider the inputs on which accepts. Note that at least fraction of them are accepted by some cylinder intersection . Let . Since the first two elements in the tuple determine the last, we have .
Now suppose contains a corner . Then
This implies , which is a contradiction because and so .
References
Special Topics in Complexity Theory, Lecture 10
Added Dec 27 2017: An updated version of these notes exists on the class page.
Special Topics in Complexity Theory, Fall 2017. Instructor: Emanuele Viola
1 Lecture 10, Guest lecture by Justin Thaler, Scribe: Biswaroop Maiti
This is a guest lecture by Justin Thaler regarding lower bounds on approximate degree [BKT17, BT15, BT17]. Thanks to Justin for giving this lecture and for his help with the writeup. We will sketch some details of the lower bound on the approximate degree of , and some intuition about the techniques used. Recall the definition of from the previous lecture as below:
Definition 1. The surjectivity function , takes input where each is interpreted as an element of . has value if and only if .
Recall from the last lecture that is the blockwise composition of the function on bits and the function on bits. In general, we will denote the blockwise composition of two functions , and , where is defined on bits and is defined on bits, by . Here, the outputs of copies of are fed into (with the inputs to each copy of being pairwise disjoint). The total number of inputs to is .
1.1 Lower Bound of via lower bound of ANDOR
Claim 2. .
We will look at only the lower bound in the claim. We interpret the input as a list of numbers from . As presented in [BKT17], the proof for the lower bound proceeds in the following steps.
 Show that to approximate , it is necessary to approximate the blockcomposition on inputs of Hamming weight at most . i.e., show that .
Step 1 was covered in the previous lecture, but we briefly recall a bit of intuition for why the claim in this step is reasonable. The intuition comes from the fact that the converse of the claim is easy to establish, i.e., it is easy to show that in order to approximate , it is sufficient to approximate on inputs of Hamming weight exactly .
This is because can be expressed as an (over all range items ) of the (over all inputs ) of “Is input equal to ”? Each predicate of the form in quotes is computed exactly by a polynomial of degree , since it depends on only of the input bits, and exactly of the predicates (one for each ) evaluates to TRUE.
Step 1 of the lower bound proof for in [BKT17] shows a converse, namely that the only way to approximate is to approximate on inputs of Hamming weight at most .
 Show that , i.e., the degree required to approximate on inputs of Hamming weight at most is at least .
In the previous lecture we also sketched this Step 2. In this lecture we give additional details of this step. As in the papers, we use the concept of a “dual witness.” The latter can be shown to be equivalent to bounded indistinguishability.
Step 2 itself proceeds via two substeps:
 Give a dual witness for that has places little mass (namely, total mass less then ) on inputs of hamming weight .
 By modifying , give a dual witness for that places zero mass on inputs of Hamming weight .
In [BKT17], both Substeps 2a and 2b proceed entirely in the dual world (i.e., they explicitly manipulate dual witnesses and ). The main goal of this section of the lecture notes is to explain how to replace Step 2b of the argument of [BKT17] with a wholly “primal” argument.
The intuition of the primal version of Step 2b that we’ll cover is as follows. First, we will show that a polynomial of degree that is bounded on the low Hamming Weight inputs, cannot be too big on the high Hamming weight inputs. In particular, we will prove the following claim.
Claim 3. If is a degree polynomial that satisfies on all inputs of of Hamming weight at most , then for all inputs .
Second, we will explain that the dual witness constructed in Step 2a has the following “primal” implication:
Claim 4. For , any polynomial of degree satisfying for all inputs of Hamming weight at most must satisfy for some input .
Combining Claims 3 and 4, we conclude that no polynomial of degree can satisfy
which is exactly the desired conclusion of Step 2. This is because any polynomial satisfying Equation (1) also satisfies for all of Hamming weight of most , and hence Claim 3 implies that
But Claim 4 states that any polynomial satisfying both Equations (1) and (2) requires degree strictly larger than .
In the remainder of this section, we prove Claims 3 and 4.
1.2 Proof of Claim 3
Proof of Claim 3. For notational simplicity, let us prove this claim for polynomials on domain , rather than .
Proof in the case that is symmetric. Let us assume first that is symmetric, i.e., is only a function of the Hamming weight of its input . Then for some degree univariate polynomial (this is a direct consequence of MinskyPapert symmetrization, which we have seen in the lectures before). We can express as below in the same spirit of Lagrange interpolation.
Here, the first term, ,is bounded in magnitude by , and . Therefore, we get the final bound:
Proof for general . Let us now consider the case of general (not necessarily symmetric) polynomials . Fix any input . The goal is to show that .
Let us consider a polynomial of degree obtained from by restricting each input such that to have the value 0. For example, if and , then . We will exploit three properties of :
 .
 Since for all inputs with , satisfies the analogous property: for all inputs with .
 If denotes the all1s vector of length , then .
Property 3 means that our goal is to show that .
Let denote the symmetrized version of , i.e., , where the expectation is over a random permutation of , and . Since for all permutations , . But is symmetric, so Properties 1 and 2 together mean that the analysis from the first part of the proof implies that for all inputs . In particular, letting , we conclude that as desired.
Discussion. One may try to simplify the analysis of the general case in the proof Claim 3 by considering the polynomial defined via ], where the expectation is over permutations of . is a symmetric polynomial, so the analysis for symmetric polynomials immediately implies that . Unfortunately, this does not mean that .
This is because the symmetrized polynomial is averaging the values of over all those inputs of a given Hamming weight. So, a bound on this averaging polynomial does not preclude the case where is massively positive on some inputs of a given Hamming weight, and massively negative on other inputs of the same Hamming weight, and these values cancel out to obtain a small average value. That is, it is not enough to conclude that on the average over inputs of any given Hamming weight, the magnitude of is not too big.
Thus, we needed to make sure that when we symmetrize to , such large cancellations don’t happen, and a bound of the average value of on a given Hamming weight really gives us a bound on on the input itself. We defined so that . Since there is only one input in of Hamming weight , does not average ’s values on many inputs, meaning we don’t need to worry about massive cancellations.
A note on the history of Claim 3. Claim 3 was implicit in [RS10]. They explicitly showed a similar bound for symmetric polynomials using primal view and (implicitly) gave a different (dual) proof of the case for general polynomials.
1.3 Proof of Claim 4
1.3.1 Interlude Part 1: Method of Dual Polynomials [BT17]
A dual polynomial is a dual solution to a certain linear program that captures the approximate degree of any given function . These polynomials act as certificates of the high approximate degree of . The notion of strong LP duality implies that the technique is lossless, in comparison to symmetrization techniques which we saw before. For any function and any , there is always some dual polynomial that witnesses a tight approximate degree lower bound for . A dual polynomial that witnesses the fact that is a function satisfying three properties:
 Correlation analysis:
If satisfies this condition, it is said to be wellcorrelated with .
 Pure high degree: For all polynomials of degree less than , we have
If satisfies this condition, it is said to have pure high degree at least .
 norm:
1.3.2 Interlude Part 2: Applying The Method of Dual Polynomials To BlockComposed Functions
For any function , we can write an LP capturing the approximate degree of . We can prove lower bounds on the approximate degree of by proving lower bounds on the value of feasible solution of this LP. One way to do this is by writing down the Dual of the LP, and exhibiting a feasible solution to the dual, thereby giving an upper bound on the value of the Dual. By the principle of LP duality, an upper bound on the Dual LP will be a lower bound of the Primal LP. Therefore, exhibiting such a feasible solution, which we call a dual witness, suffices to prove an approximate degree lower bound for .
However, for any given dual witness, some work will be required to verify that the witness indeed meets the criteria imposed by the Dual constraints.
When the function is a blockwise composition of two functions, say and , then we can try to construct a good dual witness for by looking at dual witnesses for each of and , and combining them carefully, to get the dual witness for .
The dual witness constructed in Step 2a for is expressed below in terms of the dual witness of the inner function viz. and the dual witness of the outer , viz. .
This method of combining dual witnesses for the “outer” function and for the “inner function” is referred to in [BKT17, BT17] as dual block composition.
1.3.3 Interlude Part 3: Hamming Weight Decay Conditions
Step 2a of the proof of the lower bound from [BKT17] gave a dual witness for (with ) that had pure high degree , and also satisfies Equations (4) and (5) below.
Equation (4) is a very strong “Hamming weight decay” condition: it shows that the total mass that places on inputs of high Hamming weight is very small. Hamming weight decay conditions play an essential role in the lower bound analysis for from [BKT17]. In addition to Equations (4) and (5) themselves being Hamming weight decay conditions, [BKT17]’s proof that satisfies Equations (4) and (5) exploits the fact that the dual witness for can be chosen to simultaneously have pure high degree , and to satisfy the following weaker Hamming weight decay condition:
Claim 5. There exist constants such that for all ,
(We will not prove Claim 5 in these notes, we simply state it to highlight the importance of dual decay to the analysis of ).
Dual witnesses satisfying various notions of Hamming weight decay have a natural primal interpretation: they witness approximate degree lower bounds for the target function ( in the case of Equation (4), and in the case of Equation (6)) even when the approximation is allowed to be exponentially large on inputs of high Hamming weight. This primal interpretation of dual decay is formalized in the following claim.
Claim 6. Let be any function mapping to . Suppose is a dual witness for satisfying the following properties:
 (Correlation): .
 (Pure high degree): has pure high degree .
 (Dual decay): for all .
Then there is no degree polynomial such that
Proof. Let be any degree polynomial. Since has pure high degree , .
We will now show that if satisfies Equation (7), then the other two properties satisfied by (correlation and dual decay) together imply that , a contradiction.
Here, Line 2 exploited that has correlation at least with , Line 3 exploited the assumption that satisfies Equation (7), and Line 4 exploited the dual decay condition that is assumed to satisfy.
1.3.4 Proof of Claim 4
Proof. Claim 4 follows from Equations (4) and (5), combined with Claim 6. Specifically, apply Claim 6 with , and
2 Generalizing the analysis for to prove a nearly linear approximate degree lower bound for
Now we take a look at how to extend this kind of analysis for to obtain even stronger approximate degree lower bounds for other functions in . Recall that can be expressed as an (over all range items ) of the (over all inputs ) of “Is input equal to ”? That is, simply evaluates on the inputs where indicates whether or not input is equal to range item .
Our analysis for can be viewed as follows: It is a way to turn the function on bits (which has approximate degree ) into a function on close to bits, with polynomially larger approximate degree (i.e. is defined on bits where, say, the value of is , i.e., it is a function on bits). So, this function is on not much more than bits, but has approximate degree , polynomially larger than the approximate degree of .
Hence, the lower bound for can be seen as a hardness amplification result. We turn the function on bits to a function on slightly more bits, but the approximate degree of the new function is significantly larger.
From this perspective, the lower bound proof for showed that in order to approximate , we need to not only approximate the function, but, additionally, instead of feeding the inputs directly to gate itself, we are further driving up the degree by feeding the input through gates. The intuition is that we cannot do much better than merely approximate the function and then approximating the block composed gates. This additional approximation of the gates give us the extra exponent in the approximate degree expression.
We will see two issues that come in the way of naive attempts at generalizing our hardness amplification technique from to more general functions.
2.1 Interlude: Grover’s Algorithm
Grover’s algorithm [Gro96] is a quantum algorithm that finds with high probability the unique input to a black box function that produces a given output, using queries on the function, where is the size of the the domain of the function. It is originally devised as a database search algorithm that searches an unsorted database of size and determines whether or not there is a record in the database that satisfies a given property in queries. This is strictly better compared to deterministic and randomized query algorithms because they will take queries in the worst case and in expectation respectively. Grover’s algorithm is optimal up to a constant factor, for the quantum world.
2.2 Issues: Why a dummy range item is necessary
In general, let us consider the problem of taking any function that does not have maximal approximate degree (say, with approximate degree ), and turning it into a function on roughly the same number of bits, but with polynomially larger approximate degree.
In analogy with how equals evaluated on inputs , where indicates whether or not , we can consider the block composition evaluated on , and hope that this function has polynomially larger approximate degree than itself.
Unfortunately, this does not work. Consider for example the case . The function evaluates to 1 on all possible vectors , since all such vectors of Hamming weight exactly .
One way to try to address this is to introduce a dummy range item, all occurrences of which are simply ignored by the function. That is, we can consider the (hopefully harder) function to interpret its input as a list of numbers from the range , rather than range , and define (note that variables , which indicate whether or not each input equals range item , are simply ignored).
In fact, in the previous lecture we already used this technique of introducing a “dummy” range item, to ease the lower bound analysis for itself. Last lecture we covered Step 1 of the lower bound proof for , and we let denote the frequency of the dummy range item, 0. The introduction of this dummy range item let us replace the condition (i.e., the sum of the frequencies of all the range items is exactly ) by the condition (i.e., the sum of the frequencies of all the range items is at most ).
2.3 A dummy range item is not sufficient on its own
Unfortunately, introducing a dummy range item is not sufficient on its own. That is, even when the range is is rather than , the function may have approximate degree that is not polynomially larger than that of itself. An example of this is (once again) . With a dummy range item, evaluates to TRUE if and only if at least one of the inputs is not equal to the dummy range item . This problem has approximate degree (it can be solved using Grover search).
Therefore, the most naive approach at general hardness amplification, even with a dummy range item, does not work.
2.4 The approach that works
The approach that succeeds is to consider the block composition (i.e., apply the naive approach with a dummy range item not to itself, but to ). As pointed out in Section 2.3, the gates are crucial here for the analysis to go through.
It is instructive to look at where exactly the lower bound proof for breaks down if we try to adapt it to the function (rather than the function which we analyzed to prove the lower bound for ). Then we can see why the introduction of the gates fixes the issue.
When analyzing the more naively defined function (with a dummy range item), Step 1 of the lower bound analysis for does work unmodified to imply that in order to approximate , it is necessary to approximate block composition of on inputs of Hamming weight at most . But Step 2 of the analysis breaks down: one can approximate on inputs of Hamming weight at most using degree just .
Why does the Step 2 analysis break down for ? If one tries to construct a dual witness for by applying dual block composition (cf. Equation (3), but with the dual witness for replaced by a dual witness for ), will not be wellcorrelated with .
Roughly speaking, the correlation analysis thinks of each copy of the inner dual witness as consisting of a sign, , and a magnitude , and the inner dual witness “makes an error” on if it outputs the wrong sign, i.e., if . The correlation analysis winds up performing a union bound over the probability (under the product distribution ) that any of the copies of the inner dual witness makes an error. Unfortunately, each copy of the inner dual witness makes an error with constant probability under the distribution . So at least one of them makes an error under the product distribution with probability very close to 1. This means that the correlation of the dualblockcomposed dual witness with is poor.
But if we look at , the correlation analysis does go through. That is, we can give a dual witness for and a dual witness for such that the the dualblockcomposition of and is wellcorrelated with .
This is because [BT15] showed that for , . This means that has a dual witness that “makes an error” with probability just . This probability of making an error is so low that a union bound over all copies of appearing in the dualblockcomposition of and implies that with probability at least , none of the copies of make an error.
In summary, the key difference between and that allows the lower bound analysis to go through for the latter but not the former is that the latter has approximate degree for , while the former only has approximate degree if is a constant bounded away from 1.
To summarize, the lower bound can be seen as a way to turn the function into a harder function , meaning that has polynomially larger approximate degree than . The right approach to generalize the technique for arbitrary is to (a) introduce a dummy range item, all occurrences of which are effectively ignored by the harder function , and (b) rather than considering the “inner” function , consider the inner function , i.e., let . The gates are essential to make sure that the error in the correlation of the inner dual witness is very small, and hence the correlation analysis for the dualblockcomposed dual witness goes through. Note that can be interpreted as follows: it breaks the range up into blocks, each of length , (the dummy range item is excluded from all of the blocks), and for each block it computes a bit indicating whether or not every range item in the block has frequency at least 1. It then feeds these bits into .
By recursively applying this construction, starting with , we get a function in AC with approximate degree for any desired constant .
2.5 distinctness
The above mentioned very same issue also arises in [BKT17]’s proof of a lower bound on the approximate degree of the distinctness function. Step 1 of the lower bound analysis for reduced analyzing distinctness to analyzing (restricted to inputs of Hamming weight at most ), where is the function that evaluates to TRUE if and only if its input has Hamming weight at least . The lower bound proved in [BKT17] for distinctness is . is the function. So, is “close” to . And we’ve seen that the correlation analysis of the dual witness obtained via dualblockcomposition breaks down for .
To overcome this issue, we have to show that is harder to approximate than itself, but we have to give up some small factor in the process. We will lose some quantity compared to the lower bound for . It may seem that this loss factor is just a technical issue and not intrinsic, but this is not so. In fact, this bound is almost tight. There is an upper bound from a complicated quantum algorithm [BL11, Bel12] for distinctness that makes that we won’t elaborate on here.
References
[Bel12] Aleksandrs Belovs. Learninggraphbased quantum algorithm for kdistinctness. In Foundations of Computer Science (FOCS), 2012 IEEE 53rd Annual Symposium on, pages 207–216. IEEE, 2012.
[BKT17] Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. arXiv preprint arXiv:1710.09079, 2017.
[BL11] Aleksandrs Belovs and Troy Lee. Quantum algorithm for kdistinctness with prior knowledge on the input. arXiv preprint arXiv:1108.3022, 2011.
[BT15] Mark Bun and Justin Thaler. Hardness amplification and the approximate degree of constantdepth circuits. In International Colloquium on Automata, Languages, and Programming, pages 268–280. Springer, 2015.
[BT17] Mark Bun and Justin Thaler. A nearly optimal lower bound on the approximate degree of . arXiv preprint arXiv:1703.05784, 2017.
[Gro96] Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twentyeighth annual ACM symposium on Theory of computing, pages 212–219. ACM, 1996.
[RS10] Alexander A Razborov and Alexander A Sherstov. The signrank of . SIAM Journal on Computing, 39(5):1833–1855, 2010.
Special Topics in Complexity Theory, Lectures 1213
Special Topics in Complexity Theory, Fall 2017. Instructor: Emanuele Viola
1 Lectures 1213, Scribe: Giorgos Zirdelis
In these lectures we study the communication complexity of some problems on groups. We give the definition of a protocol when two parties are involved and generalize later to more parties.
Definition 1. A 2party cbit deterministic communication protocol is a depthc binary tree such that:
 the leaves are the output of the protocol
 each internal node is labeled with a party and a function from that party’s input space to
Computation is done by following a path on edges, corresponding to outputs of functions at the nodes.
A publiccoin randomized protocol is a distribution on deterministic protocols.
2 2party communication protocols
We start with a simple protocol for the following problem.
Let be a group. Alice gets and Bob gets and their goal is to check if , or equivalently if .
There is a simple deterministic protocol in which Alice simply sends her input to Bob who checks if . This requires communication complexity.
We give a randomized protocol that does better in terms on communication complexity. Alice picks a random hash function . We can think that both Alice and Bob share some common randomness and thus they can agree on a common hash function to use in the protocol. Next, Alice sends to Bob, who then checks if .
For we get constant error and constant communication.
3 3party communication protocols
There are two ways to extend 2party communication protocols to more parties. We first focus on the Numberinhand (NIH), where Alice gets , Bob gets , Charlie gets , and they want to check if . In the NIH setting the communication depends on the group .
3.1 A randomized protocol for the hypercube
Let with addition modulo 2. We want to test if . First, we pick a linear hash function , i.e. satisfying . For a uniformly random set . Then,
 Alice sends
 Bob send
 Charlie accepts if and only if
The hash function outputs 1 bit. The error probability is and the communication is . For a better error, we can repeat.
3.2 A randomized protocol for
Let where . Again, we want to test if . For this group, there is no 100% linear hash function but there are almost linear hash function families that satisfy the following properties:
 we have
 we have
Assuming some random hash function (from a family) that satisfies the above properties the protocol works similar to the previous one.
 Alice sends
 Bob sends
 Charlie accepts if and only if
We can set to achieve constant communication and constant error.
Analysis
To prove correctness of the protocol, first note that , then consider the following two cases:
 if then
 if then
It now remains to show that such hash function families exist.
Let be a random odd number modulo . Define
where the product is integer multiplication. In other words we output the bits of the integer product .
We now verify that the above hash function family satisfies the three properties we required above.
Property (3) is trivially satisfied.
For property (1) we have the following. Let and and . The bottom line is how compares with . In more detail we have that,
Notice, that if in the addition the carry into the bit is , then
otherwise
which concludes the proof for property (1).
Finally, we prove property (2). We start by writing where is odd. Bitwise, this looks like .
The product for a uniformly random , bitwise looks like . We consider the two following cases for the product :
 If , or equivalently , the output never lands in the bad set (some thought should be given to the representation of negative numbers – we ignore that for simplicity).
 Otherwise, the hash function output has uniform bits. Again for simplicity, let . Thus,
In other words, the probability of landing in any small set is small.
4 Other groups
What happens in other groups? Do we have an almost linear hash function for matrices? The answer is negative. For and the problem of testing equality with is hard.
We would like to rule out randomized protocols, but it is hard to reason about them directly. Instead, we are going to rule out deterministic protocols on random inputs. For concreteness our main focus will be .
First, for any group element we define the distribution on triples, , where are uniformly random elements. Note the product of the elements in is always .
Towards a contradiction, suppose we have a randomized protocol for the problem. In particular, we have
This implies a deterministic protocol with the same gap, by fixing the randomness.
We reach a contradiction by showing that for every deterministic protocols using little communication (will quantify later), we have
We start with the following lemma, which describes a protocol using product sets.
Lemma 1. (The set of accepted inputs of) A deterministic bit protocol can be written as a disjoint union of “rectangles,” that is sets of the form .
Proof. (sketch) For every communication transcript , let be the set of inputs giving transcript . The sets are disjoint since an input gives only one transcript, and their number is , i.e. one for each communication transcript of the protocol. The rectangle property can be proven by induction on the protocol tree.
Next, we show that these product sets cannot distinguish these two distributions , and for that we will use the pseudorandom properties of the group .
Lemma 2. For all and we have
Recall the parameter from the previous lectures and that when the group is then .
Proof. Pick any and let be the inputs of Alice, Bob, and Charlie respectively. Then
If either or is small, that is or , then also because the term will be small. We will choose later.
Otherwise, and are large, which implies that and are uniform over at least elements. Recall from Lecture 9 that this implies , where is the uniform distribution.
By Cauchy–Schwarz we obtain,
The last inequality follows from the fact that .
This implies that and , because taking inverses and multiplying by does not change anything. These two last inequalities imply that,
and thus we get that,
To conclude, based on all the above we have that for all and independent of the choice of , it is either the case that
or
and we will now choose the to balance these two cases and finish the proof:
The above proves that the distribution behaves like the uniform distribution for product sets, for all .
Returning to arbitrary deterministic protocols , write as a union of disjoint rectangles by the first lemma. Applying the second lemma and summing over all rectangles we get that the distinguishing advantage of is at most . For the advantage is at most and thus we get a contradiction on the existence of such a correct protocol. We have concluded the proof of this theorem.
Theorem 3. Let be a group, and be the minimum dimension of an irreducible representation of . Consider the 3party, numberinhand communication protocol where . Its randomized communication complexity is .
For the communication is . This is tight up to constants, because Alice can send her entire group element.
For the group the known bounds on yield communication . This bound is tight for the problem of distinguishing from for , as we show next. The identity element for the group is the identity permutation. If then is a permutation that maps some element to . The idea is that the parties just need to “follow” , which is logarithmically smaller than . Specifically, let be the permutations that Alice, Bob and Charlie get. Alice sends . Bob gets and sends to Charlie who checks if . The communication is . Because the size of the group is , the communication is .
This is also a proof that cannot be too large for , i.e. is at most .
5 More on 2party protocols
We move to another setting where a clean answer can be given. Here we only have two parties. Alice gets , Bob gets , and they want to know if .
When is abelian, the elements can be reordered as to check whether . This requires constant communication (using randomness) as we saw in Lecture 12, since it is equivalent to the check where and .
We will prove the next theorem for nonabelian groups.
Theorem 1. For every nonabelian group the communication of deciding if is .
Proof. We reduce from unique disjointness, defined below. For the reduction we will need to encode the And of two bits as a group product. (This question is similar to a puzzle that asks how to hang a picture on the wall with two nails, such that if either one of the nails is removed, the picture will fall. This is like computing the And function on two bits, where both bits (nails) have to be 1 in order for the function to be 1.) Since is nonabelian, there exist such that , and in particular with . We can use this fact to encode And as
In the disjointness problem Alice and Bob get inputs respectively, and they wish to check if there exists an such that . If you think of them as characteristic vectors of sets, this problem is asking if the sets have a common element or not. The communication of this problem is . Moreover, in the variant of this problem where the number of such ’s is 0 or 1 (i.e. unique), the same lower bound still applies. This is like giving Alice and Bob two sets that either are disjoint or intersect in exactly one element, and they need to distinguish these two cases.
Next, we will reduce the above variant of the set disjointness to group products. For we product inputs for the group problem as follows:
Now, the product we originally wanted to compute becomes
If there isn’t an such that , then each product term is 1 for all , and thus the whole product is 1.
Otherwise, there exists a unique such that and thus the product will be , with being in the th position. If Alice and Bob can test if the above product is equal to 1, they can also solve the unique set disjointness problem, and thus the lower bound applies for the former.
We required the uniqueness property, because otherwise we might get a product that could be equal to 1 in some groups.
Special Topics in Complexity Theory, Lectures 89
Special Topics in Complexity Theory, Fall 2017. Instructor: Emanuele Viola
1 Lecture 89, Scribe: Xuangui Huang
In these lectures, we finish the proof of the approximate degree lower bound for ANDOR function, then we move to the surjectivity function SURJ. Finally we discuss quasirandom groups.
1.1 Lower Bound of ANDOR
Recall from the last lecture that ANDOR is the composition of the AND function on bits and the OR function on bits. We also proved the following lemma.
Lemma 1. Suppose that distributions over are wise indistinguishable distributions; and distributions over are wise indistinguishable distributions. Define over as follows:
: draw a sample from , and replace each bit by a sample of (independently).
Then and are wise indistinguishable.
To finish the proof of the lower bound on the approximate degree of the ANDOR function, it remains to see that ANDOR can distinguish well the distributions and . For this, we begin with observing that we can assume without loss of generality that the distributions have disjoint supports.
Claim 2. For any function , and for any wise indistinguishable distributions and , if can distinguish and with probability then there are distributions and with the same properties (wise indistinguishability yet distinguishable by ) and also with disjoint supports. (By disjoint support we mean for any either or .)
Proof. Let distribution be the “common part” of and . That is to say, we define such that multiplied by some constant that normalize into a distribution.
Then we can write and as
where , and are two distributions. Clearly and have disjoint supports.
Then we have
Therefore if can distinguish and with probability then it can also distinguish and with such probability.
Similarly, for all such that , we have
Hence, and are wise indistinguishable.
Equipped with the above lemma and claim, we can finally prove the following lower bound on the approximate degree of ANDOR.
Theorem 3. ANDOR.
Proof. Let be wise indistinguishable distributions for AND with advantage , i.e. . Let be wise indistinguishable distributions for OR with advantage . By the above claim, we can assume that have disjoint supports, and the same for . Compose them by the lemma, getting wise indistinguishable distributions . We now show that ANDOR can distinguish :
 : First sample . As there exists a unique such that , . Thus by disjointness of support . Therefore when sampling we always get a string with at least one “”. But then “” is replaced with sample from . We have , and when , ANDOR.
 : First sample , and we know that with probability at least . Each bit “” is replaced by a sample from , and we know that by disjointness of support. Then ANDOR.
Therefore we have ANDOR.
1.2 Lower Bound of SURJ
In this subsection we discuss the approximate degree of the surjectivity function. This function is defined as follows.
Definition 4. The surjectivity function SURJ, which takes input where for all , has value if and only if .
First, some history. Aaronson first proved that the approximate degree of SURJ and other functions on bits including “the collision problem” is . This was motivated by an application in quantum computing. Before this result, even a lower bound of had not been known. Later Shi improved the lower bound to , see [AS04]. The instructor believes that the quantum framework may have blocked some people from studying this problem, though it may have very well attracted others. Recently Bun and Thaler [BT17] reproved the lower bound, but in a quantumfree paper, and introducing some different intuition. Soon after, together with Kothari, they proved [BKT17] that the approximate degree of SURJ is .
We shall now prove the lower bound, though one piece is only sketched. Again we present some things in a different way from the papers.
For the proof, we consider the ANDOR function under the promise that the Hamming weight of the input bits is at most . Call the approximate degree of ANDOR under this promise ANDOR. Then we can prove the following theorems.
Theorem 6. ANDOR for some suitable .
In our settings, we consider . Theorem 5 shows surprisingly that we can somehow “shrink” bits of input into bits while maintaining the approximate degree of the function, under some promise. Without this promise, we just showed in the last subsection that the approximate degree of ANDOR is instead of as in Theorem 6.
Proof of Theorem 5. Define an matrix s.t. the 0/1 variable is the entry in the th row th column, and iff . We can prove this theorem in following steps:
 SURJANDOR under the promise that each row has weight ;
 let be the sum of the th column, then ANDOR under the promise that each row has weight , is at least ANDOR under the promise that ;
 ANDOR under the promise that , is at least ANDOR;
 we can change “” into “”.
Now we prove this theorem step by step.
 Let be a polynomial for SURJ, where . Then we have
Then the polynomial for ANDOR is the polynomial with replaced as above, thus the degree won’t increase. Correctness follows by the promise.
 This is the most extraordinary step, due to Ambainis [Amb05]. In this notation, ANDOR becomes the indicator function of . Define
Clearly it is a good approximation of ANDOR. It remains to show that it’s a polynomial of degree in ’s if is a polynomial of degree in ’s.
Let’s look at one monomial of degree in : . Observe that all ’s are distinct by the promise, and by over . By chain rule we have
By symmetry we have , which is linear in ’s. To get , we know that every other entry in row is , so we give away row , average over ’s such that under the promise and consistent with ’s. Therefore
In general we have
which has degree in ’s. Therefore the degree of is not larger than that of .
 Note that , . Hence by replacing ’s by ’s, the degree won’t increase.
 We can add a “slack” variable , or equivalently ; then the condition actually means .
Proof idea for Theorem 6. First, by the duality argument we can verify that if and only if there exists wise indistinguishable distributions such that:
 can distinguish ;
 and are supported on strings of weight .
Claim 7. OR.
The proof needs a little more information about the weight distribution of the indistinguishable distributions corresponding to this claim. Basically, their expected weight is very small.
Now we combine these distributions with the usual ones for And using the lemma mentioned at the beginning.
What remains to show is that the final distribution is supported on Hamming weight . Because by construction the copies of the distributions for Or are sampled independently, we can use concentration of measure to prove a tail bound. This gives that all but an exponentially small measure of the distribution is supported on strings of weight . The final step of the proof consists of slightly tweaking the distributions to make that measure .
1.3 Groups
Groups have many applications in theoretical computer science. Barrington [Bar89] used the permutation group to prove a very surprising result, which states that the majority function can be computed efficiently using only constant bits of memory (something which was conjectured to be false). More recently, catalytic computation [BCK14] shows that if we have a lot of memory, but it’s full with junk that cannot be erased, we can still compute more than if we had little memory. We will see some interesting properties of groups in the following.
Some famous groups used in computer science are:
 with bitwise addition;
 with addition mod ;
 , which are permutations of elements;
 Wreath product , whose elements are of the form where is a “flip bit”, with the following multiplication rules:
 ;
 in ;
 is the operation;
An example is . Generally we have
 matrices over with determinant in other words, group of matrices such that .
The group was invented by Galois. (If you haven’t, read his biography on wikipedia.)
Quiz. Among these groups, which is the “least abelian”? The latter can be defined in several ways. We focus on this: If we have two highentropy distributions over , does has more entropy? For example, if and are uniform over some elements, is close to uniform over ? By “close to” we mean that the statistical distance is less that a small constant from the uniform distribution. For , if uniform over , then is the same, so there is not entropy increase even though and are uniform on half the elements.
Definition 8.[Measure of Entropy] For , we think of for “high entropy”.
Note that is exactly the “collision probability”, i.e. . We will consider the entropy of the uniform distribution as very small, i.e. . Then we have
Theorem 9.[[Gow08], [BNP08]] If are independent over , then
where is the minimum dimension of irreducible representation of .
By this theorem, for high entropy distributions and , we get , thus we have
If is large, then is very close to uniform. The following table shows the ’s for the groups we’ve introduced.

Here is the alternating group of even permutations. We can see that for the first groups, Equation ((1)) doesn’t give nontrivial bounds.
But for we get a nontrivial bound, and for we get a strong bound: we have .
References
[Amb05] Andris Ambainis. Polynomial degree and lower bounds in quantum complexity: Collision and element distinctness with small range. Theory of Computing, 1(1):37–46, 2005.
[AS04] Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. J. of the ACM, 51(4):595–605, 2004.
[Bar89] David A. Mix Barrington. Boundedwidth polynomialsize branching programs recognize exactly those languages in NC. J. of Computer and System Sciences, 38(1):150–164, 1989.
[BCK14] Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman. Computing with a full memory: catalytic space. In ACM Symp. on the Theory of Computing (STOC), pages 857–866, 2014.
[BKT17] Mark Bun, Robin Kothari, and Justin Thaler. The polynomial method strikes back: Tight quantum query bounds via dual polynomials. CoRR, arXiv:1710.09079, 2017.
[BNP08] László Babai, Nikolay Nikolov, and László Pyber. Product growth and mixing in finite groups. In ACMSIAM Symp. on Discrete Algorithms (SODA), pages 248–257, 2008.
[BT17] Mark Bun and Justin Thaler. A nearly optimal lower bound on the approximate degree of AC0. CoRR, abs/1703.05784, 2017.
[Gow08] W. T. Gowers. Quasirandom groups. Combinatorics, Probability & Computing, 17(3):363–387, 2008.