Non-abelian 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 group-theoretic 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 $g=x_{1}\cdot x_{2}\cdot \cdots \cdot x_{n}$ over a finite group $G$ . 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 $g$ are, from hardest to easiest:

(1) Computing $g$ ,

(2) Deciding if $g=1_{G}$ , where $1_{G}$ is the identity element of $G$ , and

(3) Deciding if $g=1_{G}$ under the promise that either $g=1_{G}$ or $g=h$ for a fixed $h\ne 1_{G}$ .

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 $x_{i}$ in a product $x_{1}\cdot x_{2}\cdot \cdots \cdot x_{n}$ 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 two-party 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 three-party communication. In Section 4 we consider number-in-hand protocols, and we relate the communication complexity to so-called quasirandom groups [Gow08, BNP08]. In Section 6 we consider number-in-hand 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 state-of-the-art [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 $G$ be a group and let us start by considering the following basic communication task. Alice gets an element $x\in G$ and Bob gets an element $y\in G$ and their goal is to check if $x\cdot y=1_{G}$ . How much communication do they need? Well, $x\cdot y=1_{G}$ is equivalent to $x=y^{-1}$ . Because Bob can compute $y^{-1}$ 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 $x_{1}$ and $x_{2}$ and they need to check if $x_{1}\cdot y\cdot x_{2}=1_{G}$ . Indeed, it is just checking equality of $y$ and $x_{1}^{-1}\cdot x_{2}^{-1}$ , 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 $1_{G}$ , that is, if

$\begin{aligned} x_{1}\cdot y_{1}\cdot x_{2}\cdot y_{2}=1_{G}. \end{aligned}$

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 $(x_{1}\cdot x_{2})\cdot (y_{1}\cdot y_{2})=1_{G}$ . Again, Alice can compute $x_{1}\cdot x_{2}$ without communication, and Bob can compute $y_{1}\cdot y_{2}$ without communication. So this is the same problem as before and it has a constant communication protocol.

For non-abelian 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 $SL(2,q)$ is the group of $2\times 2$ invertible matrices over the field $\mathbb{F} _{q}$ with determinant $1$ .

The following result was asked in [MV13] and was proved in [GVa].

Theorem 1. Let $G=SL(2,q)$ and let $h\ne 1_{G}$ . Suppose Alice receives $x_{1},x_{2}\in G$ and Bob receives $y_{1},y_{2}\in G$ . They are promised that $x_{1}\cdot y_{1}\cdot x_{2}\cdot y_{2}$ either equals $1_{G}$ or $h$ . Deciding which case it is requires randomized communication $\Omega (\log |G|)$ .

This bound is tight as Alice can send her input, taking $O(\log |G|)$ 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 $SL(2,q)$ is the following.

Definition 2. The alternating group $A_{n}$ is the group of even permutations of $1,2,\ldots ,n$ .

If we work over $A_{n}$ instead of $SL(2,q)$ in Theorem 1 then the communication complexity is $\Omega (\log \log |G|)$ [Sha16]. The latter bound is tight [MV13]: with knowledge of $h$ , the parties can agree on an element $a\in {1,2,\ldots ,n}$ such that $h(a)\ne a$ . Hence they only need to keep track of the image $a$ . This takes communication $O(\log n)=O(\log \log |A_{n}|)$ because $|A_{n}|=n!/2.$ In more detail, the protocol is as follows. First Bob sends $y_{2}(a)$ . Then Alice sends $x_{2}y_{2}(a)$ . Then Bob sends $y_{1}x_{2}y_{2}(a)$ and finally Alice can check if $x_{1}y_{1}x_{2}y_{2}(a)=a$ .

Interestingly, to decide if $g=1_{G}$ without the promise a stronger lower bound can be proved for many groups, including $A_{n}$ , 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 $x_{1}\cdot y_{1}\cdot x_{2}\cdot y_{2}\cdots x_{n}\cdot y_{n}=1_{G}$ over $G=SL(2,q)$ requires communication $\Omega (n\log |G|)$ which is tight.

A strength of the above results is that they hold for any choice of $h$ in the promise. This makes them equivalent to certain $mixing$ 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 non-abelian group $G$ there exists an element $h$ such that deciding if $g=1_{G}$ or $g=h$ requires communication linear in the length of the product. Interestingly, the proof works for any non-abelian group. The choice of $h$ is critical, as for some $G$ and $h$ the problem is easy. For example: take any group $G$ and consider $H:=G\times \mathbb {Z}_{2}$ where $\mathbb {Z}_{2}$ is the group of integers with addition modulo $2$ . Distinguishing between $1_{H}=(1_{G},0)$ and $h=(1_{G},1)$ amounts to computing the parity of (the $\mathbb {Z}_{2}$ components of) the input, which takes constant communication.

Theorem 2. Let $G$ be a non-abelian group. There exists $h\in G$ such that the following holds. Suppose Alice receives $x_{1},x_{2},\ldots ,x_{n}$ and receives $y_{1},y_{2},\ldots ,y_{n}$ . They are promised that $x_{1}\cdot y_{1}\cdot x_{2}\cdot y_{2}\cdot \cdots \cdot x_{n}\cdot y_{n}$ either equals $1_{G}$ or $h$ . Deciding which case it is requires randomized communication $\Omega (n)$ .

Proof. We reduce from unique set-disjointness, defined below. For the reduction we encode the And of two bits $s,t\in \{0,1\}$ 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 $G$ is non-abelian, there exist $a,b\in G$ such that $a\cdot b\neq b\cdot a$ , and in particular $a\cdot b\cdot a^{-1}\cdot b^{-1}=h$ with $h\neq 1$ . We can use this fact to encode the And of $s$ and $t$ as

$\begin{aligned} a^{s}\cdot b^{t}\cdot a^{-s}\cdot b^{-t}=\begin {cases} 1~~\text {if And\ensuremath {(s,t)=0}}\\ h~~\text {otherwise} \end {cases}. \end{aligned}$

In the disjointness problem Alice and Bob get inputs $x,y\in \{0,1\}^{n}$ respectively, and they wish to check if there exists an $i\in [n]$ such that $x_{i}\land y_{i}=1$ . If you think of $x,y$ as characteristic vectors of sets, this problem is asking if the sets have a common element or not. The communication of this problem is $\Omega (n)$ [KS92, Raz92]. Moreover, in the “unique” variant of this problem where the number of such $i$ ’s is 0 or 1, the same lower bound $\Omega (n)$ 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 $x,y\in \{0,1\}^{n}$ we produce inputs for the group problem as follows:

$\begin{aligned} x & \rightarrow (a^{x_{1}},a^{-x_{1}},\ldots ,a^{x_{n}},a^{-x_{n}})\\ y & \rightarrow (b^{y_{1}},b^{-y_{1}},\ldots ,b^{y_{n}},b^{-y_{n}}). \end{aligned}$

The group product becomes

$\begin{aligned} \underbrace {a^{x_{1}}\cdot b^{y_{1}}\cdot a^{-x_{1}}\cdot b^{-y_{1}}}_{\text {1 bit}}\cdots \cdots a^{x_{n}}\cdot b^{y_{n}}\cdot a^{-x_{n}}\cdot b^{-y_{n}}. \end{aligned}$

If there isn’t an $i\in [n]$ such that $x_{i}\land y_{i}=1$ , then for each $i$ the term $a^{x_{i}}\cdot b^{y_{i}}\cdot a^{-x_{i}}\cdot b^{-y_{i}}$ is $1_{G}$ , and thus the whole product is 1.

Otherwise, there exists a unique $i$ such that $x_{i}\land y_{i}=1$ and thus the product will be $1\cdots 1\cdot h\cdot 1\cdots 1=h$ , with $h$ being in the $i$ -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. $\square$

We required the uniqueness property, because otherwise we might get a product $h^{c}$ that could be equal to 1 in some groups.

Next we prove a result for products of length just $4$ ; it applies to non-abelian groups of the form $G=H^{n}$ and not with the promise.

Theorem 3. Let $H$ be a non-abelian group and consider $G=H^{n}$ . Suppose Alice receives $x_{1},x_{2}$ and Bob receives $y_{1},y_{2}$ . Deciding if $x_{1}\cdot y_{1}\cdot x_{2}\cdot y_{2}=1_{G}$ requires randomized communication $\Omega (n)$ .

Proof. The proof is similar to the proof of Theorem 2. We use coordinate $i$ of $G$ to encode bit $i$ of the disjointness instance. If there is no intersection in the latter, the product will be $1_{G}$ . Otherwise, at least some coordinate will be $\ne 1_{G}$ . $\square$

As a corollary we can prove a lower bound for $A_{n}$ .

Corollary 3. Theorem 3 holds for $G=A_{n}$ .

Proof. Note that $A_{n}$ contains $(A_{4})^{\lfloor n/4\rfloor }$ and that $A_{4}$ is not abelian. Apply Theorem 3. $\square$

Theorem 3 is tight for constant-size $G$ . We do not know if Corollary 3 is tight. The trivial upper bound is $O(\log |A_{n}|)=O(n\log n)$ .

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 $SL(2,q)$ 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 $g\in G$ we define the distribution on quadruples $D_{g}:=(x_{1},y_{1},x_{2},(x_{1}\cdot y_{1}\cdot x_{2})^{-1}g)$ , where $x,y\in G$ are uniformly random elements. Note the product of the elements in $D_{g}$ is always $g$ .

Towards a contradiction, suppose we have a randomized protocol $P$ such that

$\begin{aligned} \mathbb{P} [P(D_{1})=1]\geq \mathbb{P} [P(D_{h})=1]+\frac {1}{10}. \end{aligned}$

This implies a deterministic protocol with the same gap, by fixing the randomness.

We reach a contradiction by showing that for every deterministic protocol $P$ using little communication, we have

$\begin{aligned} |\Pr [P(D_{1})=1]-\Pr [P(D_{h})=1]|\leq \frac {1}{100}. \end{aligned}$

We start with the following standard lemma, which describes a protocol using product sets.

Lemma 4. (The set of accepted inputs of) A deterministic $c$ -bit protocol for a function $f:X\times Y\to Z$ can be written as a disjoint union of $2^{c}$ rectangles, where a rectangle is a set of the form $A\times B$ with $A\subseteq X$ and $B\subseteq Y$ and where $f$ is constant.

Proof. (sketch) For every communication transcript $t$ , let $S_{t}\subseteq G^{2}$ be the set of inputs giving transcript $t$ . The sets $S_{t}$ are disjoint since an input gives only one transcript, and their number is $2^{c}$ : one for each communication transcript of the protocol. The rectangle property can be proven by induction on the protocol tree. $\square$

Next, we show that any rectangle $A\times B$ cannot distinguish $D_{1},D_{h}$ . The way we achieve this is by showing that for every $g$ the probability that $(A\times B)(D_{g})=1$ is roughly the same for every $g$ , and is roughly the density of the rectangle. (Here we write $A\times B$ for the characteristic function of the set $A\times B$ .) Without loss of generality we set $g=1_{G}$ . Let $A$ have density $\alpha$ and $B$ have density $\beta$ . We aim to bound above

$\begin{aligned} \left |\mathbb{E} _{a_{1},b_{1},a_{2},b_{2}:a_{1}b_{1}a_{2}b_{2}=1}A(a_{1},a_{2})B(b_{1},b_{2})-\alpha \beta \right |, \end{aligned}$

where note the distribution of $a_{1},b_{1},a_{2},b_{2}$ is the same as $D_{1}$ .

Because the distribution of $(b_{1},b_{2})$ is uniform in $G^{2}$ , the above can be rewritten as

$\begin{aligned} & \left |\mathbb{E} _{b_{1},b_{2}}B(b_{1},b_{2})\mathbb{E} _{a_{1},a_{2}:a_{1}b_{1}a_{2}b_{2}=1}(A(a_{1},a_{2})-\alpha )\right |\\ & \le \sqrt {\mathbb{E} _{b_{1},b_{2}}B(b_{1},b_{2})^{2}}\sqrt {\mathbb{E} _{b_{1},b_{2}}\mathbb{E} _{a_{1},a_{2}:a_{1}b_{1}a_{2}b_{2}=1}^{2}(A(a_{1},a_{2})-\alpha )}.\\ & =\sqrt {\beta }\sqrt {\mathbb{E} _{b_{1},b_{2},a_{1},a_{2},a_{1}',a_{2}':a_{1}b_{1}a_{2}b_{2}=a_{1}'b_{1}a_{2}'b_{2}=1}A(a_{1},a_{2})A(a_{1}',a_{2}')-\alpha ^{2}}. \end{aligned}$

The inequality is Cauchy-Schwarz, and the step after that is obtained by expanding the square and noting that $(a_{1},a_{2})$ is uniform in $G^{2}$ , so that the expectation of the term $A(a_{1},a_{2})\alpha$ is $\alpha ^{2}$ .

Now we do several transformations to rewrite the distribution in the last expectation in a convenient form. First, right-multiplying by $b_{2}^{-1}$ we can rewrite the distribution as the uniform distribution on tuples such that

$\begin{aligned} a_{1}b_{1}a_{2}=a_{1}'b_{1}a_{2}'. \end{aligned}$

The last equation is equivalent to $b_{1}^{-1}(a_{1}')^{-1}a_{1}b_{1}a_{2}=a_{2}'$ .

We can now do a transformation setting $a_{1}'$ to be $a_{1}x^{-1}$ to rewrite the distribution of the four-tuple as

$\begin{aligned} (a_{1},a_{2},a_{1}x^{-1},C(x)a_{2}) \end{aligned}$

where we use $C(x)$ to denote a uniform element from the conjugacy class of $x$ , that is $b^{-1}xb$ for a uniform $b\in G$ .

Hence it is sufficient to bound

$\begin{aligned} \left |\mathbb{E} A(a_{1},a_{2})A(a_{1}x^{-1},C(x)a_{2})-\alpha ^{2}\right |, \end{aligned}$

where all the variables are uniform and independent.

With a similar derivation as above, this can be rewritten as

$\begin{aligned} & \left |\mathbb{E} A(a_{1},a_{2})\mathbb{E} (A(a_{1}x^{-1},C(x)a_{2})-\alpha )\right |\\ & \le \sqrt {\mathbb{E} A(a_{1},a{}_{2})^{2}}\sqrt {\mathbb{E} _{a_{1},a_{2}}\mathbb{E} _{x}^{2}(A(a_{1}x^{-1},C(x)a_{2})-\alpha )}.\\ & =\sqrt {\alpha }\sqrt {\mathbb{E} A(a_{1}x^{-1},C(x)a_{2})A(a_{1}x'^{-1},C(x')a_{2})-\alpha ^{2}}. \end{aligned}$

Here each occurrence of $C$ denotes a uniform and independent conjugate. Hence it is sufficient to bound

$\begin{aligned} \left |\mathbb{E} A(a_{1}x^{-1},C(x)a_{2})A(a_{1}x'^{-1},C(x')a_{2})-\alpha ^{2}\right |. \end{aligned}$

We can now replace $a_{2}$ with $C(x)^{-1}a_{2}.$ Because $C(x)^{-1}$ has the same distribution of $C(x^{-1})$ , it is sufficient to bound

$\begin{aligned} \left |\mathbb{E} A(a_{1}x^{-1},a_{2})A(a_{1}x'^{-1},C(x')C(x^{-1})a_{2})-\alpha ^{2}\right |. \end{aligned}$

For this, it is enough to show that with high probability $1-1/|G|^{\Omega (1)}$ over $x'$ and $x$ , the distribution of $C(x')C(x^{-1})$ , over the choice of the two independent conjugates, has statistical distance $\le 1/|G|^{\Omega (1)}$ 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 $Tr$ be the Trace map:

$\begin{aligned} Tr\begin {pmatrix}a_{1} & a_{2}\\ a_{3} & a_{4} \end {pmatrix}=a_{1}+a_{4}. \end{aligned}$

We state the lemma that we want to show.

Lemma 5. Let $a:=\begin {pmatrix}0 & 1\\ 1 & w \end {pmatrix}$ and $b:=\begin {pmatrix}v & 1\\ 1 & 0 \end {pmatrix}$ . For all but $O(1)$ values of $w\in \mathbb{F} _{q}$ and $v\in \mathbb{F} _{q}$ , the distribution of

$\begin{aligned} Tr\left (au^{-1}bu\right ) \end{aligned}$

is $O(1/q)$ close to uniform over $\mathbb{F} _{q}$ in statistical distance.

To give some context, in $SL(2,q)$ the conjugacy class of an element is essentially determined by the trace. Moreover, we can think of $a$ and $b$ as generic elements in $G$ . So the lemma can be interpreted as saying that for typical $a,b\in G$ , taking a uniform element from the conjugacy class of $b$ and multiplying it by $a$ yields an element whose conjugacy class is uniform among the classes of $G$ . 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 $x,x'$ the distribution of $C(x')C(x^{-1})$ 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 high-level 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 Lang-Weil theorem [LW54] from algebraic geometry is replaced by a more elementary argument. For simplicity we shall only cover the case where $q$ is prime. We will show that for all but $O(1)$ values of $v,w,c\in \mathbb{F} _{q}$ , the probability over $u$ that $Tr(au^{-1}bu)=c$ is within $O(1/q^{2})$ of $1/q$ , and for the others it is at most $O(1/q)$ . Summing over $c$ gives the result.

We shall consider elements $b$ whose trace is unique to the conjugacy class of $b$ . (This holds for all but $O(1)$ conjugacy classes – see for example [GVa] for details.) This means that the distribution of $u^{-1}bu$ is that of a uniform element in $G$ conditioned on having trace $b$ . Hence, we can write the probability that $Tr(au^{-1}bu)=c$ as the number of solutions in $x$ to the following three equations (divided by the size of the group, which is $q^{3}-q$ ):

$\begin{aligned} x_{3}+x_{2}+wx_{4} & =c & \hspace {1cm}(Tr(ax)=c),\\ x_{1}+x_{4} & =v & \hspace {1cm}(Tr(x)=Tr(b)),\\ x_{1}x_{4}-x_{3}x_{3} & =1 & \hspace {1cm}(Det(x)=1). \end{aligned}$

We use the second one to remove $x_{1}$ and the first one to remove $x_{2}$ from the last equation. This gives

$\begin{aligned} (v-x_{4})x_{4}-(c-x_{3}-wx_{4})x_{3}=1. \end{aligned}$

This is an equation in two variables. Write $x=x_{3}$ and $y=x_{4}$ and use distributivity to rewrite the equation as

$\begin{aligned} -y^{2}+vy-cx+x^{2}+wxy=1. \end{aligned}$

At least since Lagrange it has been known how to reduce this to a Pell equation $x^{2}+dy^{2}=e$ . This is done by applying an invertible affine transformation, which does not change the number of solutions. First set $x=x-wy/2$ . Then the equation becomes

$\begin{aligned} -y^{2}+vy-c(x-wy/2)+(x-wy/2)^{2}+w(x-wy/2)y=1. \end{aligned}$

Equivalently, the cross-term has disappeared and we have

$\begin{aligned} y^{2}(-1-w^{2}/4)+y(v+cw/2)+x^{2}-cx=1. \end{aligned}$

Now one can add constants to $x$ and $y$ to remove the linear terms, changing the constant term. Specifically, let $h:=(v+cw/2)/2$ and set $y=y-h$ and $x=x+c/2$ . The equation becomes

$\begin{aligned} (y-h)^{2}(-1-w^{2}/4)+(y-h)2h+(x+c/2)^{2}-c(x+c/2)=1. \end{aligned}$

The linear terms disappear, the coefficients of $x^{2}$ and $y^{2}$ do not change and the equation can be rewritten as

$\begin{aligned} y^{2}(-1-w^{2}/4)+h^{2}(-1-w^{2}/4)-2h^{2}+x^{2}+(c/2)^{2}-c^{2}/2=1. \end{aligned}$

So this is now a Pell equation

$\begin{aligned} x^{2}+dy^{2}=e \end{aligned}$

where $d:=(-1-w^{2}/4)$ and

$\begin{aligned} e:=1+h^{2}(3+w^{2}/4)+(c/2)^{2}=1+(v^{2}+(cw/2)^{2}+cvw)(1/4)(3+w^{2}/4)+(c/2)^{2}. \end{aligned}$

For all but $O(1)$ values of $w$ we have that $d$ is non-zero. Moreover, for all but $O(1)$ values of $v,w$ the term $e$ is a non-zero polynomial in $c$ . (Specifically, for any $v\ne 0$ and any $w$ such that $3+w^{2}/4\ne 0$ .) So we only consider the values of $c$ that make it non-zero. Those where $e=0$ give $O(q)$ solutions, which is fine. We conclude with the following lemma.

Lemma 6. For $d$ and $e$ non-zero, and prime $q$ , the number of solutions over $\mathbb{F} _{q}$ to the Pell equation

$\begin{aligned} x^{2}+dy^{2}=e \end{aligned}$

is within $O(1)$ of $q$ .

This is a basic result from algebraic geometry that can be proved from first principles.

Proof. If $d=-f^{2}$ for some $f\in \mathbb{F} _{q}$ , then we can replace $y$ with $fy$ and we can count instead the solutions to the equation

$\begin{aligned} x^{2}-y^{2}=e. \end{aligned}$

Because $x^{2}-y^{2}=(x-y)(x+y)$ we can set $x':=x-y$ and $y':=x+y$ , which preserves the number of solutions, and rewrite the equation as

$\begin{aligned} x'y'=e. \end{aligned}$

Because $e\ne 0$ , this has $q-1$ solutions: for every non-zero $y'$ we have $x'=e/y'$ .

So now we can assume that $d\ne -f^{2}$ for any $f\in \mathbb{F} _{q}$ . Because the number of squares is $(q+1)/2$ , the range of $x^{2}$ has size $(q+1)/2$ . Similarly, the range of $e-dy^{2}$ also has size $(q+1)/2$ . Hence these two ranges intersect, and there is a solution $(a,b)$ .

We take a line passing through $(a,b)$ : for parameters $s,t\in \mathbb{F}$ we consider pairs $(a+t,b+st)$ . There is a bijection between such pairs with $t\ne 0$ and the points $(x,y)$ with $x\ne a$ . Because the number of solutions with $x=a$ is $O(1)$ , using that $d\ne 0$ , it suffices to count the solutions with $t\ne 0$ .

The intuition is that this line has two intersections with the curve $x^{2}+dy^{2}=e$ . Because one of them, $(a,b)$ , lies in $\mathbb{F} _{q}$ , the other has to lie as well there. Algebraically, we can plug the pair in the expression to obtain the equivalent equation

$\begin{aligned} a^{2}+t^{2}+2at+d(b^{2}+s^{2}t^{2}+2bst)=e. \end{aligned}$

Using that $(a,b)$ is a solution this becomes

$\begin{aligned} t^{2}+2at+ds^{2}t^{2}+2dbst=0 \end{aligned}$

We can divide by $t\ne 0$ . Obtaining

$\begin{aligned} t(1+ds^{2})+2a+2dbs=0. \end{aligned}$

We can now divide by $1+ds^{2}$ which is non-zero by the assumption $d\ne -f^{2}$ . This yields

$\begin{aligned} t=(-2a-2dbs)/(1+ds^{2}). \end{aligned}$

Hence for every value of $s$ there is a unique $t$ giving a solution. This gives $q$ solutions. $\square$

4 Three parties, number-in-hand

In this section we consider the following three-party number-in-hand problem: Alice gets $x$ , Bob gets $y$ , Charlie gets $z$ , and they want to know if $x\cdot y\cdot z=1_{G}$ . The communication depends on the group $G$ . 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 $G=(\mathbb {Z}_{2})^{n}$ , that is $n$ -bit strings with bit-wise addition modulo 2. The parties want to check if $x+y+z=0^{n}$ . They can do so as follows. First, they pick a hash function $h$ that is linear: $h(x+y)=h(x)+h(y)$ . Specifically, for a uniformly random $a\in \{0,1\}^{n}$ define $h_{a}(x):=\sum a_{i}x_{i}\mod 2$ . Then, the protocol is as follows.

Alice sends $h_{a}(x)$ ,
Bob send $h_{a}(y)$ ,
Charlie accepts if and only if $h_{a}(x)+h_{a}(y)+h_{a}(z)=0s$ .

The hash function outputs 1 bit, so the communication is constant. By linearity, the protocol accepts iff $h_{a}(x+y+z)=0$ . If $x+y+z=0$ this is always the case, otherwise it happens with probability $1/2$ .

4.2 A randomized protocol for $\mathbb {Z}_{N}$

This protocol is from [Vio14]. For simplicity we only consider the case $N=2^{n}$ here – the protocol for general $N$ is in [Vio14]. Again, the parties want to check if $x+y+z=0\mod N$ . For this group, there is no 100% linear hash function but there are almost linear hash functions $h:\mathbb {Z}_{N}\rightarrow \mathbb {Z}_{2^{\ell }}$ that satisfy the following properties. Note that the inputs to $h$ are interpreted modulo $N$ and the outputs modulo $2^{\ell }$ .

for all $a,x,y$ there is $c\in \{0,1\}$ such that $h_{a}(x+y)=h_{a}(x)+h_{a}(y)+c$ ,
for all $x\neq 0$ we have $\mathbb{P} _{a}[h_{a}(x)\in \{-2,-1,0,1,2\}]\leq O(1/2^{\ell })$ ,
$h_{a}(0)=0$ .

Assuming some random hash function $h$ that satisfies the above properties the protocol works similarly to the previous one:

Alice sends $h_{a}(x)$ ,
Bob sends $h_{a}(y)$ ,
Charlie accepts if and only if $h_{a}(x)+h_{a}(y)+h_{a}(z)\in \{-2,-1,0\}$ .

We can set $\ell =O(1)$ to achieve constant communication and constant error.

To prove correctness of the protocol, first note that $h_{a}(x)+h_{a}(y)+h_{a}(z)=h_{a}(x+y+z)-c$ for some $c\in \{0,1,2\}$ . Then consider the following two cases:

if $x+y+z=0$ then $h_{a}(x+y+z)-c=h_{a}(0)-c=-c,$ and the protocol is always correct.
if $x+y+z\neq 0$ then the probability that $h_{a}(x+y+z)-c\in \{-2,-1,0\}$ for some $c\in \{0,1,2\}$ is at most the probability that $h_{a}(x+y+z)\in \{-2,-1,0,1,2\}$ which is $\leq 2^{-\Omega (\ell )}$ ; so the protocol is correct with high probability.

The hash function..

For the hash function we can use a function analyzed in [DHKP97]. Let $a$ be a random odd number modulo $2^{n}$ . Define

$\begin{aligned} h_{a}(x):=(a\cdot x\gg n-\ell )\mod 2^{\ell } \end{aligned}$

where the product $a\cdot x$ is integer multiplication, and $\gg$ is bit-shift. In other words we output the bits $n-\ell +1,n-\ell +2,\ldots ,n$ of the integer product $a\cdot x$ .

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 $s=a\cdot x$ and $t=a\cdot y$ and $u=n-\ell$ . To recap, by definition we have:

$h_{a}(x+y)=((s+t)\gg u)\mod 2^{\ell },$
$h_{a}(x)=(s\gg u)\mod 2^{\ell }$ ,
$h_{a}(x)=(t\gg u)\mod 2^{\ell }$ .

Notice that if in the addition $s+t$ the carry into the $u+1$ bit is $0$ , then

$\begin{aligned} (s\gg u)+(t\gg u)=(s+t)\gg u \end{aligned}$

otherwise

$\begin{aligned} (s\gg u)+(t\gg u)+1=(s+t)\gg u \end{aligned}$

which concludes the proof for property (1).

Finally, we prove property (2). We start by writing $x=s\cdot 2^{c}$ where $s$ is odd. So the binary representation of $x$ looks like

$\begin{aligned} (\cdots \cdots 1\underbrace {0\cdots 0}_{c~\textrm {bits}}). \end{aligned}$

The binary representation of the product $a\cdot x$ for a uniformly random $a$ looks like

$\begin{aligned} (\textit {uniform}~1\underbrace {0\cdots 0}_{c~\textrm {bits}}). \end{aligned}$

We consider the two following cases for the product $a\cdot x$ :

If $a\cdot x=(\underbrace {\textit {uniform}~1\overbrace {00}^{2~bits}}_{\ell ~bits}\cdots 0)$ , or equivalently $c\geq n-\ell +2$ , the output never lands in the bad set $\{-2,-1,0,1,2\}$ ;
Otherwise, the hash function output has $\ell -O(1)$ uniform bits. For any set $B$ , the probability that the output lands in $B$ is at most $|B|\cdot 2^{-\ell +O(1)}$ .

4.3 Quasirandom groups

What happens in other groups? The hash function used in the previous result was fairly non-trivial. Do we have an almost linear hash function for $2\times 2$ matrices? The answer is negative. For $SL_{2}(q)$ and $A_{n}$ the problem is hard, even under the promise. For a group $G$ the complexity can be expressed in terms of a parameter $d$ 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 $d$ ’s for the groups we’ve introduced.


$G$	:	abelian	$A_{n}$	$SL_{2}(q)$

$d$	:	$1$	$\Omega (\frac {\log \|G\|}{\log \log \|G\|})$	$\|G\|^{\Omega (1)}$

Theorem 1. Let $G$ be a group, and let $h\in G$ . Let $d$ be the minimum dimension of any irreducible representation of $G$ . Suppose Alice, Bob, and Charlie receive $x$ , y, and $z$ respectively. They are promised that $x\cdot y\cdot z$ either equals $1_{G}$ or $h$ . Deciding which case it is requires randomized communication complexity $\Omega (\log d)$ .

This result is tight for the groups we have discussed so far. The arguments are the same as before. Specifically, for $SL_{2}(q)$ the communication is $\Omega (\log |G|)$ . This is tight up to constants, because Alice and Bob can send their elements. For $A_{n}$ the communication is $\Omega (\log \log |G|)$ . This is tight as well, as the parties can again just communicate the images of an element $a$ such that $h(a)\ne a$ , as discussed in Section 1. This also gives a computational proof that $d$ cannot be too large for $A_{n}$ , i.e., it is at most $(\log |G|)^{O(1)}$ . 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 $XY$ mixing

We want to consider “high entropy” distributions over $G$ , 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 $\lVert A\rVert _{c}=\left (\sum _{x}A(x)^{c}\right )^{\frac {1}{c}}$ . Our notion of (non-)entropy will be $\lVert A\rVert _{2}$ . Note that $\lVert A\rVert _{2}^{2}$ is exactly the collision probability $\mathbb{P} [A=A']$ where $A'$ is independent and identically distributed to $A$ . The smaller this quantity, the higher the entropy of $A$ . For the uniform distribution $U$ we have $\lVert U\rVert _{2}^{2}=\frac {1}{|G|}$ and so we can think of $1/|G|$ as maximum entropy. If $A$ is uniform over $\Omega (|G|)$ elements, we have $\lVert A\rVert _{2}^{2}=O(1/|G|)$ and we think of $A$ as having “high” entropy.

Because the entropy of $U$ is small, we can think of the distance between $A$ and $U$ in the 2-norm as being essentially the entropy of $A$ :

$\begin{aligned} \lVert A-U\rVert _{2}^{2} & =\sum _{x\in G}\left (A(x)-\frac {1}{|G|}\right )^{2}\\ & =\sum _{x\in G}A(x)^{2}-2A(x)\frac {1}{|G|}+\frac {1}{|G|^{2}}\\ & =\lVert A\rVert _{2}^{2}-\frac {1}{|G|}\\ & =\lVert A\rVert _{2}^{2}-\lVert U\rVert _{2}^{2}\\ & \approx \lVert A\rVert _{2}^{2}. \end{aligned}$

Lemma 7. [Gow08, BNP08] If $X,Y$ are independent over $G$ , then

$\begin{aligned} \lVert X\cdot Y-U\rVert _{2}\leq \lVert X\rVert _{2}\lVert Y\rVert _{2}\sqrt {\frac {|G|}{d}}, \end{aligned}$

where $d$ is the minimum dimension of an irreducible representation of $G$ .

By this lemma, for high entropy distributions $X$ and $Y$ , we get $\lVert X\cdot Y-U\rVert _{2}\leq \frac {O(1)}{\sqrt {|G|d}}$ . The factor $1/\sqrt {|G|}$ allows us to pass to statistical distance $\lVert .\rVert _{1}$ using Cauchy-Schwarz:

$\begin{aligned} \lVert X\cdot Y-U\rVert _{1}\leq \sqrt {|G|}\lVert X\cdot Y-U\rVert _{2}\leq \frac {O(1)}{\sqrt {d}}.~~~~(1) \end{aligned}$

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 $three$ independent, high-entropy variables $X,Y,Z$ . Then for every $g\in G$ we have

$\begin{aligned} |\mathbb{P} [X\cdot Y\cdot Z=g]-1/|G||\le \lVert X\rVert _{2}\lVert Y\rVert _{2}\lVert Z\rVert _{2}\sqrt {\frac {|G|}{d}}.~~~~(2) \end{aligned}$

To show this, set $g=1_{G}$ without loss of generality and rewrite the left-hand-side as

$\begin{aligned} |\sum _{h\in G}\mathbb{P} [X=h](\mathbb{P} [YZ=h^{-1}]-1/|G|)|. \end{aligned}$

By Cauchy-Schwarz this is at most

$\begin{aligned} \sqrt {\sum _{h}\mathbb{P} ^{2}[X=h]}\sqrt {\sum _{h}(\mathbb{P} [YZ=h^{-1}]-1/|G|)^{2}}=\lVert X\lVert _{2}\lVert YZ-U\lVert _{2} \end{aligned}$

and we can conclude by Lemma 7. Hence the product of three high-entropy distributions is close to uniform in a point-wise sense: each group element is obtained with roughly probability $1/|G|$ .

At least over $SL(2,q)$ , 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 $G=SL(2,q)$ . Let $X=(X_{1},X_{2})$ and $Y=(Y_{1},Y_{2})$ be two distributions over $G^{2}$ . Suppose $X$ is independent from $Y$ . Let $g\in G$ . We have

$\begin{aligned} |\mathbb{P} [X_{1}Y_{1}X_{2}Y_{2}=g]-1/|G||\le |G|^{1-\Omega (1)}\lVert X\rVert _{2}\lVert Y\rVert _{2}. \end{aligned}$

For example, when $X$ and $Y$ have high entropy over $G^{2}$ (that is, are uniform over $\Omega (|G|^{2})$ pairs), we have $\lVert X\rVert _{2}\le \sqrt {O(1)/|G|^{2}}$ , and so $|G|^{1-\Omega (1)}\lVert X\rVert _{2}\lVert Y\rVert _{2}\le 1/|G|^{1+\Omega (1)}$ . In particular, $X_{1}Y_{1}X_{2}Y_{2}$ is $1/|G|^{\Omega (1)}$ close to uniform over $G$ in statistical distance.

5.0.2 Back to protocols

As in the beginning of Section 3, for any group element $g\in G$ we define the distribution on triples $D_{g}:=(x,y,(x\cdot y)^{-1}g)$ , where $x,y\in G$ are uniform and independent. Note the product of the elements in $D_{g}$ is always $g$ . Again as in Section 3, it suffices to show that for every deterministic protocols $P$ using little communication we have

$\begin{aligned} |\Pr [P(D_{1})=1]-\Pr [P(D_{h})=1]|\leq \frac {1}{100}. \end{aligned}$

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 $c$ -bit number-in-hand protocol with three parties can be written as a disjoint union of $2^{c}$ “rectangles,” that is sets of the form $A\times B\times C$ .

Next we show that these product sets cannot distinguish these two distributions $D_{1},D_{h}$ , via a straightforward application of lemma 7.

Lemma 9. For all $A,B,C\subseteq G$ we have $|\mathbb{P} (A\times B\times C)(D_{1})=1]-\mathbb{P} [(A\times B\times C)(D_{h})=1]|\leq 1/d^{\Omega (1)}.$

Proof. Pick any $h\in G$ and let $x,y,z$ be the inputs of Alice, Bob, and Charlie respectively. Then

$\begin{aligned} \mathbb{P} [(A\times B\times C)(D_{h})=1]=\mathbb{P} [(x,y)\in A\times B]\cdot \mathbb{P} [(x\cdot y)^{-1}\cdot h\in C|(x,y)\in A\times B],~~~~(3) \end{aligned}$

where $(x,y)$ is uniform in $G^{2}$ . If either $A$ or $B$ is small, that is $\mathbb{P} [x\in A]\leq \epsilon$ or $\mathbb{P} [y\in B]\leq \epsilon$ , then also $\mathbb{P} [(x,y)\in A\times B]\le \epsilon$ and hence (??) is at most $\epsilon$ as well. This holds for every $h$ , so we also have $|\mathbb{P} (A\times B\times C)(D_{1})=1]-\mathbb{P} [(A\times B\times C)(D_{h})=1]|\leq \epsilon .$ We will choose $\epsilon$ later.

Otherwise, $A$ and $B$ are large: $\mathbb{P} [x\in A]>\epsilon$ and $\mathbb{P} [y\in B]>\epsilon$ . Let $(x',y')$ be the distribution of $(x,y)$ conditioned on $(x,y)\in A\times B$ . We have that $x'$ and $y'$ are independent and each is uniform over at least $\epsilon |G|$ elements. By Lemma 7 this implies $\lVert x'\cdot y'-U\rVert _{2}\leq \lVert x'\rVert _{2}\cdot \lVert y'\rVert _{2}\cdot \sqrt {\frac {|G|}{d}}$ , where $U$ is the uniform distribution. As mentioned after the lemma, by Cauchy–Schwarz we obtain

$\begin{aligned} \lVert x'\cdot y'-U\rVert _{1}\leq |G|\cdot \lVert x'\rVert _{2}\cdot \lVert y'\rVert _{2}\cdot \sqrt {\frac {1}{d}}\leq \frac {1}{\epsilon }\cdot \frac {1}{\sqrt {d}}, \end{aligned}$

where the last inequality follows from the fact that $\lVert x\rVert _{2},\lVert y\rVert _{2}\leq \sqrt {\frac {1}{\epsilon |G|}}$ .

This implies that $\lVert (x'\cdot y')^{-1}-U\rVert _{1}\leq \frac {1}{\epsilon }\cdot \frac {1}{\sqrt {d}}$ and $\lVert (x'\cdot y')^{-1}\cdot h-U\rVert _{1}\leq \frac {1}{\epsilon }\cdot \frac {1}{\sqrt {d}}$ , because taking inverses and multiplying by $h$ does not change the distance to uniform. These two last inequalities imply that

$\begin{aligned} |\mathbb{P} [(x'\cdot y')^{-1}\in C]-\mathbb{P} [(x'\cdot y')^{-1}\cdot h\in C]|\le O(\frac {1}{\epsilon \sqrt {d}}); \end{aligned}$

and thus we get that

$\begin{aligned} |\mathbb{P} [(A\times B\times C)(D_{1})=1]-\mathbb{P} [(A\times B\times C)(D_{h})=1]|\le O(\frac {1}{\epsilon \sqrt {d}}). \end{aligned}$

Picking $\epsilon =1/d^{1/4}$ completes the proof. $\square$

Returning to arbitrary deterministic protocols $P$ (as opposed to rectangles), write $P$ as a union of $2^{c}$ disjoint rectangles by Lemma 8. Applying Lemma 9 and summing over all rectangles we get that the distinguishing advantage of $P$ is at most $2^{c}/d^{1/4}$ . For $c\leq (1/100)\log d$ the advantage is at most $1/100$ , concluding the proof.

6 Three parties, number-on-forehead

In number-on-forehead (NOH) communication complexity [CFL83] with $k$ parties, the input is a $k$ -tuple $(x_{1},\dotsc ,x_{k})$ and each party $i$ sees all of it except $x_{i}$ . For background, it is not known how to prove negative results for $k\ge \log n$ 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 $k\ge \log n$ , and what is the minimum length of an interleaved product that is hard for $k=3$ 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 $k=2$ , we know the optimal separation: The equality function requires $\Omega (n)$ communication for deterministic protocols, but can be solved using $O(1)$ communication if we allow the protocols to use public coins. For $k=3$ , the best known separation between deterministic and randomized protocol is $\Omega (\log n)$ vs $O(1)$ [BDPW10]. In the following we give a new proof of this result, for a different function: $f(x,y,z)=1_{G}$ if and only if $x\cdot y\cdot z=1$ for $x,y,z\in SL(2,q)$ . As is true for some functions in [BDPW10], a stronger separation could hold for $f$ . For context, let us state and prove the upper bound for randomized communication.

Claim 10. $f$ has randomized communication complexity $O(1)$ .

Proof. In the number-on-forehead model, computing $f$ reduces to two-party equality with no additional communication: Alice computes $y\cdot z=:w$ privately, then Alice and Bob check if $x=w^{-1}$ . $\square$

To prove the lower bound for deterministic protocols we reduce the communication problem to a combinatorial problem.

Definition 11. A corner in a group $G$ is a set $\{(x,y),(xz,y),(x,zy)\}\subseteq G^{2}$ , where $x,y$ are arbitrary group elements and $z\neq 1_{G}$ .

For intuition, if $G$ is the abelian group of real numbers with addition, a corner becomes $\{(x,y),(x+z,y),(x,y+z)\}$ for $z\neq 0$ , which are the coordinates of an isosceles triangle. We now state the theorem that connects corners and lower bounds.

Lemma 12. Let $G$ be a group and $\delta$ a real number. Suppose that every subset $A\subseteq G^{2}$ with $|A|/|G^{2}|\ge \delta$ contains a corner. Then the deterministic communication complexity of $f$ (defined as $f(x,y,z)=1\iff x\cdot y\cdot z=1_{G}$ ) is $\Omega (\log (1/\delta ))$ .

It is known that $\delta \ge 1/\mathrm {polyloglog}|G|$ implies a corner for certain abelian groups $G$ , see [LM07] for the best bound and pointers to the history of the problem. For $G=SL(2,q)$ a stronger result is known: $\delta \ge 1/\mathrm {polylog}|G|$ implies a corner [Aus16]. This in turn implies communication $\Omega (\log \log |G|)=\Omega (\log n)$ .

Proof. We saw already twice that a number-in-hand $c$ -bit protocol can be written as a disjoint union of $2^{c}$ rectangles (Lemmas 4, 8). Likewise, a number-on-forehead $c$ -bit protocol $P$ can be written as a disjoint union of $2^{c}$ cylinder intersections $C_{i}:=\{(x,y,z):f_{i}(y,z)g_{i}(x,z)h_{i}(x,y)=1\}$ for some $f_{i},g_{i},h_{i}\colon G^{2}\to \{0,1\}$ :

$\begin{aligned} P(x,y,z)=\sum _{i=1}^{2^{c}}f_{i}(y,z)g_{i}(x,z)h_{i}(x,y). \end{aligned}$

The proof idea of the above fact is to consider the $2^{c}$ transcripts of $P$ , then one can see that the inputs giving a fixed transcript are a cylinder intersection.

Let $P$ be a $c$ -bit protocol. Consider the inputs $\{(x,y,(xy)^{-1})\}$ on which $P$ accepts. Note that at least $2^{-c}$ fraction of them are accepted by some cylinder intersection $C=f\cdot g\cdot h$ . Let $A:=\{(x,y):(x,y,(xy)^{-1})\in C\}\subseteq G^{2}$ . Since the first two elements in the tuple determine the last, we have $|A|/|G^{2}|\ge 2^{-c}$ .

Now suppose $A$ contains a corner $\{(x,y),(xz,y),(x,zy)\}$ . Then

$\begin{aligned} (x,y)\in A & \implies (x,y,(xy)^{-1})\in C & & \implies h(x,y)=1,\\ (xz,y)\in A & \implies (xz,y,(xzy)^{-1})\in C & & \implies f(y,(xyz)^{-1})=1,\\ (x,zy)\in A & \implies (x,zy,(xzy)^{-1})\in C & & \implies g(x,(xyz)^{-1})=1. \end{aligned}$

This implies $(x,y,(xzy)^{-1})\in C$ , which is a contradiction because $z\neq 1$ and so $x\cdot y\cdot (xzy)^{-1}\neq 1_{G}$ . $\square$

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 computer-science 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 $G=\textit {SL}(2,q)$ for simplicity, but the proof immediately extends to other quasirandom groups (with corresponding parameters).

Theorem 1. Let $G=\textit {SL}(2,q)$ . Every subset $A\subseteq G^{2}$ of density $|A|/|G|^{2}\geq 1/\log ^{a}|G|$ contains a corner $\{(x,y),(xz,y),(x,zy)~|~z\neq 1\}$ .

7.1 Proof idea

For intuition, suppose $A$ is a product set, i.e., $A=B\times C$ for $B,C\subseteq G$ . Let’s look at the quantity

$\begin{aligned} \mathbb {E}_{x,y,z\leftarrow G}[A(x,y)A(xz,y)A(x,zy)] \end{aligned}$

where $A(x,y)=1$ iff $(x,y)\in A$ . Note that the random variable in the expectation is equal to $1$ exactly when $x,y,z$ form a corner in $A$ . We’ll show that this quantity is greater than $1/|G|$ , which implies that $A$ contains a corner (where $z\neq 1$ ). Since we are taking $A=B\times C$ , we can rewrite the above quantity as

$\begin{aligned} \mathbb {E}_{x,y,z\leftarrow G}[B(x)C(y)B(xz)C(y)B(x)C(zy)] & =\mathbb {E}_{x,y,z\leftarrow G}[B(x)C(y)B(xz)C(zy)]\\ & =\mathbb {E}_{x,y,z\leftarrow G}[B(x)C(y)B(z)C(x^{-1}zy)] \end{aligned}$

where the last line follows by replacing $z$ with $x^{-1}z$ in the uniform distribution. If $|A|/|G|^{2}\ge \delta$ , then both |B|/|G| $\ge \delta$ and $|B|/|G|\ge \delta$ . Condition on $x\in B$ , $y\in C$ , $z\in B$ . Then the distribution $x^{-1}zy$ is a product of three independent distributions, each uniform on a set of density $\ge \delta$ . (In fact, two distributions would suffice for this.) By Lemma 7, $x^{-1}zy$ is $\delta ^{-1}/|G|^{\Omega (1)}$ close to uniform in statistical distance. This implies that the above expectation equals

$\begin{aligned} \frac {|A|}{|G|^{2}}\cdot \frac {|B|}{|G|}\cdot \left (\frac {|C|}{|G|}\pm \frac {\delta ^{-1}}{|G|^{\Omega (1)}}\right ) & \geq \delta ^{2}\left (\delta -\frac {1}{|G|^{\Omega (1)}}\right )\geq \delta ^{3}/2>1/|G|, \end{aligned}$

for $\delta >1/|G|^{c}$ for a small enough constant $c$ . Hence, product sets of density polynomial in $1/|G|$ contain corners.

Given the above, it is natural to try to decompose an arbitrary set $A$ into product sets. We will make use of a more general result.

7.2 Weak Regularity Lemma

Let $U$ be some universe (we will take $U=G^{2}$ ) and let $f:U\rightarrow [-1,1]$ be a function (for us, $f=1_{A}$ ). Let $D\subseteq \{d:U\rightarrow [-1,1]\}$ 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 $f$ into a linear combination $g$ of the $d_{i}$ up to an error which is polynomial in the length of the combination. More specifically, $f$ will be indistinguishable from $g$ by the $d_{i}$ .

Lemma 13. Let $f:U\rightarrow [-1,1]$ be a function and $D\subseteq \{d:U\rightarrow [-1,1]\}$ a set of functions. For all $\epsilon >0$ , there exists a function $g:=\sum _{i\le s}c_{i}\cdot d_{i}$ where $d_{i}\in D$ , $c_{i}\in \mathbb {R}$ and $s=1/\epsilon ^{2}$ such that for all $d\in D$

$\begin{aligned} \left |\mathbb {E}_{x\leftarrow U}[f(x)\cdot d(x)]-\mathbb {E}_{x\leftarrow U}[g(x)\cdot d(x)]\right |\le \epsilon . \end{aligned}$

A different way to state the conclusion, which we will use, is to say that we can write $f=g+h$ so that $\mathbb{E} [h(x)\cdot d(x)]$ 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 $s$ as a tower of $1/\epsilon$ whereas here we have $s$ polynomial in $1/\epsilon$ . 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 $g$ through an iterative process producing functions $g_{0},g_{1},\dots ,g$ . We will show that $||f-g_{i}||_{2}^{2}$ decreases by $\ge \epsilon ^{2}$ each iteration.

Start: Define $g_{0}=0$ (which can be realized setting $c_{0}=0$ ).

Iterate: If not done, there exists $d\in D$ such that $|\mathbb {E}[(f-g)\cdot d]|>\epsilon$ . Assume without loss of generality $\mathbb {E}[(f-g)\cdot d]>\epsilon$ .

Update: $g':=g+\lambda d$ where $\lambda \in \mathbb {R}$ shall be picked later.

Let us analyze the progress made by the algorithm.

$\begin{aligned} ||f-g'||_{2}^{2} & =\mathbb {E}_{x}[(f-g')^{2}(x)]\\ & =\mathbb {E}_{x}[(f-g-\lambda d)^{2}(x)]\\ & =\mathbb {E}_{x}[(f-g)^{2}]+\mathbb {E}_{x}[\lambda ^{2}d^{2}(x)]-2\mathbb {E}_{x}[(f-g)\cdot \lambda d(x)]\\ & \leq ||f-g||_{2}^{2}+\lambda ^{2}-2\lambda \mathbb {E}_{x}[(f-g)d(x)]\\ & \leq ||f-g||_{2}^{2}+\lambda ^{2}-2\lambda \epsilon \\ & \leq ||f-g||_{2}^{2}-\epsilon ^{2} \end{aligned}$

where the last line follows by taking $\lambda =\epsilon$ . Therefore, there can only be $1/\epsilon ^{2}$ iterations because $||f-g_{0}||_{2}^{2}=||f||_{2}^{2}\leq 1$ . $\square$

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 $A$ by rectangles. That is, we take $D$ to be the collection of indicator functions for all sets of the form $S\times T$ for $S,T\subseteq G$ . The weak regularity lemma shows how to decompose $A$ into a linear combination of rectangles. These rectangles may overlap. However, we ideally want $A$ to be a linear combination of non-overlapping 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 $S=G$ in every $S\times T$ rectangle; or in other words in the uni-dimensional setting. This is one step where the terminology “rectangle” may be misleading – the set $T$ is not necessarily an interval. If it was, a polynomial rather than exponential blow-up would have sufficed to remove overlaps.

Claim 14. Given a decomposition of $A$ into rectangles from the weak regularity lemma with $s$ functions, there exists a decomposition with $2^{O(s)}$ rectangles which don’t overlap.

Proof. Exercise. $\square$

In the above decomposition, note that it is natural to take the coefficients of rectangles to be the density of points in $A$ 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 $f$ in the rectangle, at the cost of doubling the error.

Consequently, we have that $f=g+h$ , where $g$ is the sum of $2^{O(s)}$ non-overlapping rectangles $S\times T$ with coefficients $\mathbb{P} _{(x,y)\in S\times T}[f(x,y)=1]$ .

Proof. Let $g$ be a partition decomposition with arbitrary weights. Let $g'$ be a partition decomposition with weights being the average of $f$ . It is enough to show that for all rectangle distinguishers $d\in D$

$\begin{aligned} |\mathbb {E}[(f-g')d]|\leq |\mathbb {E}[(f-g)d]|. \end{aligned}$

By the triangle inequality, we have that

$\begin{aligned} |\mathbb {E}[(f-g')d]|\leq |\mathbb {E}[(f-g)d]|+|\mathbb {E}[(g-g')d]|. \end{aligned}$

To bound $\mathbb {E}[(g-g')d]|$ , note that the error is maximized for a $d$ that respects the decomposition in non-overlapping rectangles, i.e., $d$ is the union of some non-overlapping rectangles from the decomposition. This can be argued using that, unlike $f$ , the value of $g$ and $g'$ on a rectangle $S\times T$ from the decomposition is fixed. But, from the point of “view” of such $d$ , $g'=f$ ! More formally, $\mathbb {E}[(g-g')d]=\mathbb {E}[(g-f)d]$ . This gives

$\begin{aligned} |\mathbb {E}[(f-g')d]|\leq 2|\mathbb {E}[(f-g)d]| \end{aligned}$

and concludes the proof. $\square$

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 $U(x)\cdot V(y)$ where $U$ and $V$ map $G\to \{0,1\}$ . We will use that the same guarantee holds for $U$ and $V$ with range $[-1,1]$ , up to a constant factor loss in the error. Indeed, let $U$ and $V$ have range $[-1,1]$ . Write $U=U_{+}-U_{-}$ where $U_{+}$ and $U_{-}$ have range $[0,1]$ , and the same for $V$ . The error for distinguisher $U\cdot V$ is at most the sum of the errors for distinguishers $U_{+}\cdot V_{+}$ , $U_{+}\cdot V_{-}$ , $U_{-}\cdot V_{+}$ , and $U_{-}\cdot V_{-}$ . So we can restrict our attention to distinguishers $U(x)\cdot V(y)$ where $U$ and $V$ have range $[0,1]$ . In turn, a function $U(x)$ with range $[0,1]$ can be written as an expectation $\mathbb{E} _{a}U_{a}(x)$ for functions $U_{a}$ with range $\{0,1\}$ , and the same for $V$ . We conclude by observing that

$\begin{aligned} \mathbb{E} _{x,y}[(f-g)(x,y)\mathbb{E} _{a}U_{a}(x)\cdot \mathbb{E} _{b}V_{b}(y)]\le \max _{a,b}\mathbb{E} _{x,y}[(f-g)(x,y)U_{a}(x)\cdot V_{b}(y)]. \end{aligned}$

7.4 Proof

Let us now finish the proof by showing a corner exists for sufficiently dense sets $A\subseteq G^{2}$ . We’ll use three types of decompositions for $f:G^{2}\rightarrow \{0,1\}$ , with respect to the following three types of distinguishers, where $U_{i}$ and $V_{i}$ have range $\{0,1\}$ :

$U_{1}(x)\cdot V_{1}(y)$ ,
$U_{2}(xy)\cdot V_{2}(y)$ ,
$U_{3}(x)\cdot V_{3}(xy)$ .

The first type is just rectangles, what we have been discussing until now. The distinguishers in the last two classes can be visualized over $\mathbb {R}^{2}$ as parallelograms with a 45-degree angle. The same extra properties we discussed for rectangles can be verified hold for them too.

Recall that we want to show

$\begin{aligned} \mathbb {E}_{x,y,g}[f(x,y)f(xg,y)f(x,gy)]>\frac {1}{|G|}. \end{aligned}$

We’ll decompose the $i$ -th occurrence of $f$ via the $i$ -th decomposition listed above. We’ll write this decomposition as $f=g_{i}+h_{i}$ . 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 $(x,y),(xg,y),(x,gy)$ . The decomposition is:

$\begin{aligned} & fff\\ = & ffg_{3}+ffh_{3}\\ = & fg_{2}g_{3}+fh_{2}g_{3}+ffh_{3}\\ = & g_{1}g_{2}g_{3}+h_{1}g_{2}g_{3}+fh_{2}g_{3}+ffh_{3}. \end{aligned}$

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.

Claim 16. For all $g\in G$ , the expectations $\mathbb {E}_{x,y}[g_{1}(x,y)g_{2}(xg,y)g_{3}(x,gy)]$ are the same up to an error of $2^{O(s)}/|G|^{\Omega (1)}$ .

Proof. We just need to get error $1/|G|^{\Omega (1)}$ for any product of three functions for the three decomposition types. We have:

$\begin{aligned} & \mathbb {E}_{x,y}[c_{1}U_{1}(x)V_{1}(y)\cdot c_{2}U_{2}(xgy)V_{2}(y)\cdot c_{3}U_{3}(x)V_{3}(xgy)]\\ = & c_{1}c_{2}c_{3}\mathbb {E}_{x,y}[(U_{1}\cdot U_{3})(x)(V_{1}\cdot V_{2})(y)(U_{2}\cdot V_{3})(xgy)]\\ = & c_{1}c_{2}c_{3}\cdot \mathbb {E}_{x}[(U_{1}\cdot U_{3})(x)]\cdot \mathbb {E}_{y}[(V_{1}\cdot V_{2})(y)]\cdot \mathbb {E}_{z}[(U_{2}\cdot V_{3})(z)]\pm \frac {1}{|G|^{\Omega (1)}}. \end{aligned}$

This is similar to what we discussed in the overview, and is where we use mixing. Specifically, if $\mathbb {E}_{x}[(U_{1}\cdot U_{3})(x)]$ or $\mathbb {E}_{y}[(V_{1}\cdot V_{2})(y)]$ are at most $1/|G|^{c}$ for a small enough constant $c$ than we are done. Otherwise, conditioned on $(U_{1}\cdot U_{3})(x)=1$ , the distribution on $x$ is uniform over a set of density $1/|G|^{c}$ , and the same holds for $y$ , and the result follows by Lemma 7. $\square$

Recall that we start with a set of density $\ge 1/\log ^{a}|G|$ .

Claim 17. $\mathbb {E}_{x,y}[g_{1}(x,y)g_{2}(x,y)g_{3}(x,y)]>1/\log ^{4a}|G|$ .

Proof. We will relate the expectation over $x,y$ to $f$ using the Hölder inequality: For random variables $X_{1},X_{2},\ldots ,X_{k}$ ,

$\begin{aligned} \mathbb {E}[X_{1}\dots X_{k}]\leq \prod _{i=1}^{k}\mathbb {E}[X_{i}^{c_{i}}]^{1/c_{i}}\text { such that }\sum 1/c_{i}=1. \end{aligned}$

To apply this inequality in our setting, write

$\begin{aligned} f=(f\cdot g_{1}g_{2}g_{3})^{1/4}\cdot \left (\frac {f}{g_{1}}\right )^{1/4}\cdot \left (\frac {f}{g_{2}}\right )^{1/4}\cdot \left (\frac {f}{g_{3}}\right )^{1/4}. \end{aligned}$

By the Hölder inequality the expectation of the right-hand side is

$\begin{aligned} \leq \mathbb {E}[f\cdot g_{1}g_{2}g_{3}]^{1/4}\mathbb {E}\left [\frac {f}{g_{1}}\right ]^{1/4}\mathbb {E}\left [\frac {f}{g_{2}}\right ]^{1/4}\mathbb {E}\left [\frac {f}{g_{3}}\right ]^{1/4}. \end{aligned}$

The last three terms equal to $1$ because

$\begin{aligned} \mathbb {E}_{x,y}\frac {f(x,y)}{g_{i}(x,y)} & =\mathbb {E}_{x,y}\frac {f(x,y)}{\mathbb {E}_{x',y'\in \textit {Cell}(x,y)}[f(x',y')]}=\mathbb {E}_{x,y}\frac {\mathbb {E}_{x',y'\in \textit {Cell}(x,y)}[f(x',y')]}{\mathbb {E}_{x',y'\in \textit {Cell}(x,y)}[f(x',y')]}=1. \end{aligned}$

where $\textit {Cell}(x,y)$ is the set in the partition that contains $(x,y)$ . Putting the above together we obtain

$\begin{aligned} \mathbb {E}[f]\leq \mathbb {E}[f\cdot g_{1}g_{2}g_{3}]^{1/4}. \end{aligned}$

Finally, because the functions are positive, we have that $\mathbb {E}[f\cdot g_{1}g_{2}g_{3}]^{1/4}\leq \mathbb {E}[g_{1}g_{2}g_{3}]^{1/4}$ . This concludes the proof. $\square$

It remains to show the other terms are small. Let $\epsilon$ be the error in the weak regularity lemma with respect to distinguishers with range $\{0,1\}$ . Recall that this implies error $O(\epsilon )$ with respect to distinguishers with range $[-1,1]$ . We give the proof for one of the terms and then we say little about the other two.

Claim 18. $|\mathbb {E}[f(x,y)f(xg,y)h_{3}(x,gy)]|\leq O(\epsilon )^{1/4}$ .

The proof involves changing names of variables and doing Cauchy-Schwarz to remove the terms with $f$ and bound the expectation above by $\mathbb {E}[h_{3}(x,g)U(x)V(xg)]$ , which is small by the regularity lemma.

Proof. Replace $g$ with $gy^{-1}$ in the uniform distribution to get

$\begin{aligned} & \mathbb {E}_{x,y,g}^{4}[f(x,y)f(xg,y)h_{3}(x,gy)]\\ & =\mathbb {E}_{x,y,g}^{4}[f(x,y)f(xgy^{-1},y)h_{3}(x,g)]\\ & =\mathbb {E}_{x,y}^{4}[f(x,y)\mathbb {E}_{g}[f(xgy^{-1},y)h_{3}(x,g)]]\\ & \leq \mathbb {E}_{x,y}^{2}[f^{2}(x,y)]\mathbb {E}_{x,y}^{2}\mathbb {E}_{g}^{2}[f(xgy^{-1},y)h_{3}(x,g)]\\ & \leq \mathbb {E}_{x,y}^{2}\mathbb {E}_{g}^{2}[f(xgy^{-1},y)h_{3}(x,g)]\\ & =\mathbb {E}_{x,y,g,g'}^{2}[f(xgy^{-1},y)h_{3}(x,g)f(xg'y^{-1},y)h_{3}(x,g')], \end{aligned}$

where the first inequality is by Cauchy-Schwarz.

Now replace $g\rightarrow x^{-1}g,g'\rightarrow x^{-1}g$ and reason in the same way:

$\begin{aligned} & =\mathbb {E}_{x,y,g,g'}^{2}[f(gy^{-1},y)h_{3}(x,x^{-1}g)f(g'y^{-1},y)h_{3}(x,x^{-1}g')]\\ & =\mathbb {E}_{g,g',y}^{2}[f(gy^{-1},y)\cdot f(g'y^{-1},y)\mathbb {E}_{x}[h_{3}(x,x^{-1}g)\cdot h_{3}(x,x^{-1}g')]]\\ & \leq \mathbb {E}_{x,x',g,g'}[h_{3}(x,x^{-1}g)h_{3}(x,x^{-1}g')h_{3}(x',x'^{-1}g)h_{3}(x',x'^{-1}g')]. \end{aligned}$

Replace $g\rightarrow xg$ to rewrite the expectation as

$\begin{aligned} \mathbb {E}[h_{3}(x,g)h_{3}(x,x^{-1}g')h_{3}(x',x'^{-1}xg)h_{3}(x',x'^{-1}g')]. \end{aligned}$

We want to view the last three terms as a distinguisher $U(x)\cdot V(xg)$ . First, note that $h_{3}$ has range $[-1,1]$ . This is because $h_{3}(x,y)=f(x,y)-\mathbb{E} _{x',y'\in \textit {Cell}(x,y)}f(x',y')$ and $f$ has range $\{0,1\}$ , where recall that $Cell(x,y)$ is the set in the partition that contains $(x,y)$ . Fix $x',g'$ . The last term in the expectation becomes a constant $c\in [-1,1]$ . The second term only depends on $x$ , and the third only on $xg$ . Hence for appropriate functions $U$ and $V$ with range $[-1,1]$ this expectation can be rewritten as

$\begin{aligned} \mathbb {E}[h_{3}(x,g)U(x)V(xg)], \end{aligned}$

which concludes the proof. $\square$

There are similar proofs to show the remaining terms are small. For $fh_{2}g_{3}$ , we can perform simple manipulations and then reduce to the above case. For $h_{1}g_{2}g_{3}$ , we have a slightly easier proof than above.

7.4.1 Parameters

Suppose our set has density $\delta \ge 1/\log ^{a}|G|$ , and the error in the regularity lemma is $\epsilon$ . By the above results we can bound

$\begin{aligned} \mathbb {E}_{x,y,g}[f(x,y)f(xg,y)f(x,gy)]\ge 1/\log ^{4a}|G|-2^{O(1/\epsilon ^{2})}/|G|^{\Omega (1)}-\epsilon ^{\Omega (1)}, \end{aligned}$

where the terms in the right-hand size come, left-to-right from Claim 17, 16, and 18. Picking $\epsilon =1/\log ^{1/3}|G|$ the proof is completed for sufficiently small $a$ .

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. Ajtai-Szemeré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. Bounded-width polynomial-size branching programs recognize exactly those languages in NC $^1$ . J. of Computer and System Sciences, 38(1):150–164, 1989.

[BC92] Michael Ben-Or 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 ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 248–257, 2008.

[CFL83] Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multi-party 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 closest-pair 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, 1-27, 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 two-dimensional 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 $NC^1$ . 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 BNS-Chung criterion for multi-party 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: Thirty-five 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/szemeredi-proof1.pdf.

[Vioa] Emanuele Viola. Thoughts: Mixing in groups. https://emanueleviola.wordpress.com/2016/10/21/mixing-in-groups/.

[Viob] Emanuele Viola. Thoughts: Mixing in groups ii. https://emanueleviola.wordpress.com/2016/11/15/mixing-in-groups-ii/.

[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 Chi-Chih Yao. Some complexity questions related to distributive computing. In 11th ACM Symp. on the Theory of Computing (STOC), pages 209–213, 1979.

We knew the best threshold-circuit lower bounds long ago

For more than 20 years we’ve had $n^{1+c^{-d}}$ lower bounds for threshold circuits of depth $d$ [IPS97], for a fixed $c$ . There have been several “explanations” for the lack of progress [AK10]. Recently Chen and Tell have given a better explanation showing that you can’t even improve the result to a better $c$ without proving “the whole thing.”

Say you have a finite group $G$ and you want to compute the iterated product of $n$ elements.

Warm-up [AK10]..

Suppose you can compute this with circuits of size $s(n)=n^{10}$ and depth $10$ . Now we show how you can trade size for depth. Put a complete tree with fan-in $f$ on top of the group product, where each node computes the product of its children (this is correct by associativity, in general this works for a monoid). This tree needs depth $\log _{f}n$ . If you stick your circuit of size $s(n)$ and depth $O(1)$ at each node, the depth of the overall circuit would be obviously $O(\log _{f}n)$ and the overall size would be dominated by the input layer which is $s(f)\cdot n/f<s(f)\cdot n$ . If you are aiming for overall depth $d$ , you need $f=n^{O(1/d)}$ . This gives size $n^{1+O(1/d)}$ .

Hence we have shown that proving bounds $n^{1+\omega (1/d)}$ for some depth $d$ suffices to prove $n^{10}$ lower bounds for depth $10$ .

Chen and Tell..

The above is not the most efficient way to build a tree! I am writing this post following their paper to understand what they do. As they say, the idea is quite simple. While above the size will be dominated by the input layer, we want to balance things so that every layer has roughly the same contribution.

Let’s say we are aiming for size $n^{1+\epsilon }$ and let’s see what depth we can get. Let’s say now the size is $s(n)=n^{k}$ . Let us denote by $n_{i}$ the number of nodes at level $i$ with $i=0$ being the root. The fan-in at level $i$ is $(n^{1+\epsilon }/n_{i})^{1/k}$ so that the cost is $n^{1+\epsilon }$ as desired. We have the recursion $n_{i+1}=n_{i}\cdot (n^{1+\epsilon }/n_{i})^{1/k}$ .

The solution to this recursion is $n_{i}=n^{(1+\epsilon )(1-(1-1/k)^{i})}$ , see below.

So that’s it. We need to get to $n$ nodes. So if you set $i=O(k\log (1/\epsilon ))$ you get say $n_{i}=n^{(1+\epsilon )(1-\epsilon ^{2})}>n$ . Going back to $k=10$ , we have exhibited circuits of size $n^{1+\epsilon }$ and depth just $O(\log 1/\epsilon )$ . So proving stronger bounds than this would rule out circuits of size $n^{10}$ and depth $10$ .

Added later: About the recurrence.

Letting $a_{i}:=\log _{n}n_{i}$ we have the following recurrence for the exponents of $n_{i}$ .

$\begin{aligned} a_{0} & =0\\ a_{i+1} & =a_{i}(1-1/k)+(1+\epsilon )/k=:a_{i}b+c. \end{aligned}$

This gives

$\begin{aligned} a_{i}=c\sum _{j\le i}b{}^{j}=c\frac {1-b^{i+1}}{1-b}=(1+\epsilon )(1-b^{i+1}). \end{aligned}$

If it was $a'_{i+1}=a'_{i}+(1+\epsilon )/k$ obviously $a'_{k}$ would already be $1+\epsilon$ . Instead for $a_{i}$ we need to get to $k\log (1/\epsilon )$ .

My two cents..

I am not sure I need more evidence that making progress on long-standing bounds in complexity theory is hard, but I do find it interesting to prove these links; we have quite a few by now! The fact that we have been stuck forever just short of proving “the whole thing” makes me think that these long-sought bounds may in fact be false. Would love to be proved wrong, but it’s 2019, this connection is proved by balancing a tree better, and you feel confident that P $\ne$ NP?

References

[AK10] Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. J. of the ACM, 57(3), 2010.

[IPS97] Russell Impagliazzo, Ramamohan Paturi, and Michael E. Saks. Size-depth tradeoffs for threshold circuits. SIAM J. Comput., 26(3):693–707, 1997.

Statement of concern regarding Marijuana in Massachusetts

You can read it here. If you don’t want to click, some key takeaways are:

We disagree with how marijuana policy is being shaped in the Commonwealth.
The science is clear; marijuana, specifically the psychoactive chemical THC (delta-9-tetrahydrocannabinol), has the potential to do significant harm to public health.
Diversion of high THC products (≥10%), vapes and edibles, to MA youth is a growing concern.
When public health is not prioritized in the regulation of addictive substances, the public and our young people are put at risk.

You can also find in the statement a list of negative effects of THC. This is all signed by a dozen+ doctors. The various marijuana players with zero medical knowledge will probably dismiss the experts’ opinion with, at best, a shrug. Instead, they are looking into opening marijuana cafes. And the first marijuana retail store will open in Newton this Saturday.

If you want to get even more worked up about marijuana reading my previous post might help.

Finally, on June 5^th there will be a luncheon event at the JFK Library titled: Marijuana: Addiction, Mental Health and Policy – Advances in Research…What have we learned in the past 5 years?

And this is me with my buddies

E-ink on the move

Today I was overjoyed to notice that the MBTA is installing e-ink signs. I didn’t know about this when I wrote in the previous post that the market for e-ink monitors will be huge.

I was actually about to report more on my experience, and by another standard coincidence today a reader asks:

Some time have passed, is your evaluation the same? Did you come across any unexpected difficulties?

Well, I wrote a paper entirely in e-ink. But I regret to admit that towards the end of the semester I got really busy with the usual end-of-Spring matters at the university, and I switched back to my back-lit 30-inch Dell monitor. I had to interact with a number of computer systems where I could not easily change font size (the story of my life), and where color tended to matter, and I felt that the new monitor was slowing me down. I haven’t switched back to the e-ink monitor yet, partly because I am still recovering from the burst.

However I look forward to using the e-ink monitor more during this summer, especially outdoors. Here the fact that it’s usb powered will be essential. In the MBTA project they use solar power which I think is really cool and makes me think of bringing my monitor to the secluded off-the-grid cabin in Maine I don’t have.

A dream come true, sort of: E-ink monitors

Spending your life staring at a (traditional) computer screen may not be ideal for your eyes (and more); so since an early age I have been dreaming of a “purely mechanical” monitor that you could stare at more or less indefinitely, like at parchment.

This dream is now becoming reality, sort of. The Dasung E-ink monitor has no backlight and instead reportedly uses electric flows to move ink droplets.

After some consideration, spending yet more hours reading reviews online and watching youtube videos about it sealed the deal. I shelled out $1300 and bought the thing.

I have had it for a few days now and I am sort of happy. I went from using a giant 30-inch monitor far away (my theory for avoiding eye strain) to using a ~13-inch monitor at pretty much the same distance as reading a book. I had to avoid sunlight, now I seek it (see the picture).

20190307_094550

The monitor makes your computer look like Windows 3.1 on a monochrome screen from the 80’s. The refresh is slow, and there is a ghosting effect, meaning there are shadows of previous images — which you can clear out. Also, it’s 4:3 instead of 16:9, which is a pain because it means I have to change resolution when I am forced to use my other monitor (for example if I have to check colors — the screen is gray-scale, did I mention that?). It makes browsing the internet quite painful, which is a nice side effect.

Contrary to advice, I am using it as my primary monitor. I am sort of happy with it and don’t regret buying it. I have started writing and reading papers with it and it’s working well enough.

I think as soon as the technology improves the market for these things will be huge. Already having a 17″ monitor in 16:9 ratio, ideally touch-screen, even if gray scale, would be a dream come true.

Selling your town to the marijuana industry

I vowed to quit with marijuana, but I just can’t. It’s addictive.

We can go back to 2016, when voters were hit with legalese that can only be described as a trap. Basically, under the mask of legalizing the consumption of marijuana, the ballot question was really about opening recreational pot shops around the corner. No doubt many, many people voted for legalization without knowledge of this and with no desire to have pot shops in their town. What exultation must have come from the lawyers working for the industry, when their masterstroke made it to the fine print:

A town voting to legalize marijuana may MUST open pot shops.

At the same time, the administration of Newton changed. Councilors who liked the place the way it is and wanted to protect it lost to others who wanted it more vibrant. The new councilors and the new mayor sided with the marijuana industry.

The way in which they eventually won is sinister. The context was that everybody in Newton wants at least some restriction on the number of marijuana stores. But don’t take my word for this claim: even the pro-pot councilors believe so, and in fact almost unanimously they put a question on the ballot about restricting the number of stores. At the same time, many people in Newton wanted zero stores. In another masterstroke of the saga, the councilors were able to put one group against the other. They added another question about having zero stores, following a massive, grassroots petition which however should have put the question at a different time. Then they forced the people who wanted zero stores to vote against restricting the number of stores. This is genius. Also, if it isn’t illegal I believe it should be. And in perfect coup style, media outlets censored several pieces explaining the situation to the voters. The end result was what the administration had always wanted: no restriction on the number of stores. Ignore the alarms of the doctors, the police officers, and the people. What do they know about what’s best for Newton? The bottom line is that the revenue will do good things for the city! Oh yes, the revenue. Newton has 1 billion dollars in deficit. You read well, 1 billion. For decades we will have a fraction of the city budget wiped out to repay that. I guess they can say we are so desperately in debt that we should rake in every penny we can zone in town. But I think a more accurate perspective is that even in their wildest dreams, cannabis sales won’t make a dent in that. And maybe they should spend a couple of minutes thinking about the dozens of other ways we can bring money to the city without bringing the drugs.

Executing their sophisticated plan cost in the neighborhood of $100k, mostly spent on a political strategy group which helped win the election. To add insult to injury, key members of this marijuana combine, including the political strategists and those who funded them, don’t live in Newton but in towns where recreational pot stores are banned. The marijuana combine is effectively carving out suburban Boston in areas where it’s good to live and areas where it’s good to sell pot.

As is well known, nobody has any problem with legalizing marijuana consumption. Moreover, there is absolutely no problem with buying this stuff over the internet, or stocking up at out-of-the-way stores. Well, absolutely no problem except one. The money wouldn’t go into the pockets of X, Y, and Z.

My last 3.5 years

I haven’t breathed (freely) since 3.5 years ago. Precisely since the day before I left my Cambridge flat, when the Pods guy told me he couldn’t park. I had to vacate within 24 hours, had no place to put all the stuff I had never used since moving there in 2008, and also happened to have a 3-hour CPR course planned long ago, starting in minutes. I took that life-saving course on the edge of the seat, each 5-minute break dashing out to call movers who might have had an unlikely last minute cancellation in the busiest day of the year (August 31).

Oh the times I wished that the fireproof storage where the things eventually went burned down to the ground. Instead I was going to have to move my never used belongings a million times up and down stairs.

Anyway, after Cambridge I went to the Simons institute. Even with all the help from the staff, finding housing was atrocious, and I had to change it during the semester. I didn’t have a place to come back, and from Berkeley I eventually found a short-term rental in Needham, MA. The idea was to buy a house in that short term. This proved impossible. So we had to find another rental. In the process, I was discriminated against three times. One time the landlord rejected in writing my application claiming that they did not want to rent to families. The other two times the landlord simply rejected my application, and then lowered the price. I thought these moves made them dumb, but maybe they are actually much smarter than me, because after toying with the idea I did not, in fact, sue.

Eventually we found another longer-term rental. From there, with more excruciating difficulties I wrote about earlier, I bought a house, which however required 1 year of renovations (not exactly cosmetic — more about this later). These were completed just in time to store my useless stuff there: I left for another semester at the Simons institute.

My second visit to the institute was also great. In fact I enjoyed it even more than the semester on fine-grained: I was there for the program on lower bounds, which are exactly the problems I went into computer science to study. I had the best time, and lots of research exchanges.

But again, the housing situation in Berkeley was desperate. Twice I lost a house for 1 hour. Meaning, the landlord called to make the deal, I couldn’t pick up the phone, and when I called back 1 hour later the place was gone. I still think it would be better if the institute bought a block of houses, and also provided computers. Even better if they make it easier to print, rather than having to stand in a corner or go through a complicated set up.

Another interesting pattern is that during my first visit there was a heat wave and the AC broke, and it was hot. This time there was a rather serious wildfire, causing very unhealthy conditions in the bay area, and at times they couldn’t run the heating systems to avoid sucking in the smoke, and it was cold.

Berkeley isn’t Princeton, but it’s hard for me not to compare the logistics of my visits to Simons and the IAS in Princeton. In the latter I was put in a house steps from the Institute, with minimal effort and at a fraction of the price. In my office there was already a working computer, connected to a printer.

Here’s the meaning of cloud computing, remote desktop, telnet, etc in 2019, here’s the progress, the sustainability, the sharing economy: everybody brings their own laptop.

Back from Simons, I can’t help but be surprised that I still have an office. In fact this happens every time I go up the stairs, turn the corner and see my name on the tag, and it says “Professor”. Really? Under my name? I have a startle each time. I know this feeling is irrational, but is there. Coming back from California, the feeling is intense.

Back to business, I am now teaching algorithms. I am running an online section, for which I am making videos on my youtube channel. It’s the future.

$50M to Northeastern Computer Science

Northeastern Computer Science is receiving a $50M gift. If you are looking for a faculty position, check out our many openings, including the joint math-cs position. Also if you are applying for a PhD take a look at our college. In particular as I mentioned already I am looking for students.

Symmetry

Yesterday at the Simon institute there was a fun talk about The edge of physics by its author, Anil Ananthaswamy. To divulgate the theory of computation isn’t as easy, since you can’t talk about mega experiments done at the South Pole or massive telescopes built on top of mountains. (It would also be a lot easier if we could resolve P vs. NP.) For some inspiration we can look at books related to mathematics. Here I would like to recommend Symmetry, by Marcus du Sautoy. I enjoyed very much reading and re-reading this book, much more than his previous book The music of the primes, which I don’t really recommend. Symmetry is a gripping history of group theory. The purpose isn’t so much explaining the math as making you excited about the historical developments of the theory and the people that worked and are working on it.

	Emanuele on Non-abelian combinatorics and…
	NG on Non-abelian combinatorics and…
	Emanuele on Statement of concern regarding…
	Anonymous on Statement of concern regarding…
	Emanuele on And this is me with my bu…

2 Two parties

3 Proof of Theorem 1

3.1 Step 1

3.2 Step 2

3.3 Step 3

4 Three parties, number-in-hand

4.1 A randomized protocol for the hypercube

4.2 A randomized protocol for

4.3 Quasirandom groups

5 Proof of Theorem 1

5.0.1 mixing

5.0.2 Back to protocols

6 Three parties, number-on-forehead

7 The corners theorem for quasirandom groups

7.1 Proof idea

7.2 Weak Regularity Lemma

7.3 Getting more for rectangles

7.4 Proof

7.4.1 Parameters

References

References

A town voting to legalize marijuana may MUST open pot shops.

4.2 A randomized protocol for $\mathbb {Z}_{N}$

5.0.1 $XY$ mixing