Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function

Håstad [6] proved the KRW conjecture for ${\mathrm{𝖪𝖶}}_f\diamond {\mathrm{𝖪𝖶}}_{\mathrm{𝖷𝖮𝖱}}$. However it is still an open question to prove the KRW conjecture for ${\mathrm{𝖪𝖶}}_{\mathrm{𝖷𝖮𝖱}}\diamond {\mathrm{𝖪𝖶}}_f$. In this paper, we study the strong composition ${\mathrm{𝖪𝖶}}_{{\mathrm{𝖷𝖮𝖱}}_m}⊛{\mathrm{𝖪𝖶}}_f$ of the parity function ${\mathrm{𝖷𝖮𝖱}}_m$ with a random function $f:{\{0,1\}}^{\log m}\to \{0,1\}$. Since Alice and Bob receive an input of size $m\log m$, we estimate the size of ${\mathrm{𝖪𝖶}}_{{\mathrm{𝖷𝖮𝖱}}_m}⊛{\mathrm{𝖪𝖶}}_f$ in terms of $n=m\log m$. It is not difficult to see that the communication complexity of the corresponding game is at most $3\log n$: ${\mathrm{𝖪𝖶}}_f$ can be solved in $\log m$ bits of communication, whereas ${\mathrm{𝖪𝖶}}_{{\mathrm{𝖷𝖮𝖱}}_m}$ can be solved in $2\log m$ bits of communication, using the standard divide-and-conquer approach (Alice sends the parity of the first half, Bob then identifies the half in which the parity differs, thus, by utilizing 2 bits of communication, the input size is reduced by a factor of two). We prove that if the function $f$ is well balanced and hard to approximate (which happens with probability $1-o(1)$), then the bound $3\log n$ is essentially optimal. Below, we state the result in terms of the protocol size (i.e., the number of leaves), rather than depth, since this gives a more general lower bound. In particular, it immediately implies a $(3-o(1))\log n$ depth lower bound.

In turn, this result follows from the following general lower bound, given in terms of ${𝖫}_{\frac{3}{4}}$ that stands for the smallest size of a formula that agrees with $f$ on a $\frac{3}{4}$ fraction of inputs.

In contrast to many results mentioned above and similarly to the bound by de Rezende at al. [2], our result works for a wide range of inner functions $f$, what brings us closer to resolving KRW, which makes a claim about the complexity of composing any pair of functions. Also, many of the previous techniques work well in the regime where the outer function is hard and give no strong lower bounds when the outer function is easy (as it is the case with the $\mathrm{𝖷𝖮𝖱}$ function). For example, random restrictions (as one of the most successful methods for proving lower bounds) does not seem to give meaningful lower bounds for ${\mathrm{𝖪𝖶}}_{{\mathrm{𝖷𝖮𝖱}}_m}⊛{\mathrm{𝖪𝖶}}_f$, as under a random restriction this composition turns into a $\mathrm{𝖷𝖮𝖱}$ of a small number of variables which is easy to compute. The lower bound by Meir (see Theorem 1) also gives strong lower bounds in the regime where the outer function is hard (and only gives a trivial lower bound of the form $o(\log n)$ for the function that we study).

To prove the lower bound, we exploit formal complexity measures. As in [4, 15], we consider two stages of a protocol solving ${\mathrm{𝖪𝖶}}_{{\mathrm{𝖷𝖮𝖱}}_m}⊛{\mathrm{𝖪𝖶}}_f$. During the first stage, we track the progress using the classical measure by Khrapchenko [13] and ensure that even after many steps of the protocol, there are still many instances of $f$ that need to be solved. At the second stage, we switch to another formal complexity measure and show that the remaining communication problem is, roughly, not easier than ${\mathrm{𝖪𝖶}}_{\mathrm{𝖮𝖱}}⊛{\mathrm{𝖪𝖶}}_f$. We believe that this proof technique is interesting on its own, since it is not only easy to show that Khrapchenko’s measure cannot give superquadratic size lower bounds, but it is also known that natural generalizations of this measure are also unable to give stronger than quadratic lower bounds [8]. For more details on Khrapchenko’s measure and its limitations, see Sections 2.1 and 2.5.

For a rooted tree, the depth of its node is the number of edges on the path from the node to the root; the depth of the tree is the maximum depth of its nodes.

Let $G(V,E)$ be a graph and $\mathrm{\varnothing }\ne A\subseteq V$ be its nonempty subset of nodes. By $G[A]$, we denote a subgraph of $G$ induced by $A$. By $\mathrm{avgdeg}(G,A)$, we denote the average degree of $A$:

For a biparite graph $G(A\bigsqcup B,E)$ with nonempty parts, let

Clearly, $\psi (G)\le |A|\cdot |B|$. The lemma below shows that this graph measure is subadditive.

By ${𝔹}_n$, we denote the set of all Boolean functions on $n$ variables. For two disjoint sets $A,B\subseteq {\{0,1\}}^n$, the set $A\times B$ is called a combinatorial rectangle, and it is called full if $A$ and $B$ form a partition of ${\{0,1\}}^n$. Clearly, there is a bijection between ${𝔹}_n$ and full combinatorial rectangles. For $f\in {𝔹}_n$, by $R_f=f^{-1}(1)\times f^{-1}(0)$, we denote the corresponding full rectangle. We say that a Boolean function $f$ is balanced if $|f^{-1}(0)|=|f^{-1}(1)|$.

In this paper, it will prove convenient to apply a function $g\in {𝔹}_m$ not only to Boolean vectors $x\in {\{0,1\}}^m$, but also to matrices $X\in {\{0,1\}}^{n\times m}$:

i.e., $g(X)\in {\{0,1\}}^n$ results by applying $g$ to every row of $X$. This allows to define a composition in a natural way. For $f\in {𝔹}_m$ and $g\in {𝔹}_n$, their composition $f\diamond g:{\{0,1\}}^{m\times n}\to \{0,1\}$ treats the input as an $m\times n$ matrix and first applies $g$ to all its rows and then applies $f$ to the resulting column-vector:

For a set of matrices $𝒳\subseteq {\{0,1\}}^{m\times n}$, by $i$-th projection ${\mathrm{proj}}_i𝒳$, we denote the set of all $i$-th rows among the matrices of $𝒳$:

In the proof of the main result, we will be dealing with Boolean matrices of dimension $n\times \log n$. Let $𝒳\subseteq {\{0,1\}}^{n\times \log n}$ be a set of such matrices. We say that $𝒳$ is $\alpha$-bounded if $|{\mathrm{proj}}_i𝒳|\le \alpha n$, for all $i\in [n]$. The $i$-th projection of $𝒳$ is called sparse if , and dense otherwise. The following lemma shows that if $|𝒳|$ is large and $𝒳$ is $\alpha$-bounded, then the number of sparse projections of $𝒳$ is low. Later on, we will be applying this lemma for $𝒳$ which is almost $0.5$-bounded and whose size gradually decreases to argue that the number of sparse projections cannot grow too fast.

The computational model studied in this paper is de Morgan formulas: it is a binary tree whose leaves are labeled by variables $x_1,\mathrm{\dots },x_n$ and their negations whereas internal nodes (called gates) are labeled by $\vee$ and $\wedge$ (binary disjunction and conjunction, respectively). Such a formula computes a Boolean function $f(x_1,\mathrm{\dots },x_n)\in {𝔹}_n$. We also say that a formula $F$ separates a rectangle $A\times B$, if $f(a)=1$ and $f(b)=0$, for all $(a,b)\in A\times B$. This way, if a formula $F$ computes a function $f$, then it separates $R_f$.

For a formula $F$, the size $𝖫(F)$ is defined as the number of leaves in $F$. This extends to Boolean functions: for $f\in {𝔹}_n$, by $𝖫(f)$ we denote the smallest size of a formula computing $f$. Similarly, the depth $𝖣(F)$ is the depth of the tree whereas $𝖣(f)$ is the smallest depth of a formula computing $f$.

By ${𝖫}_{\frac{3}{4}}(f)$, we denote the smallest size of a formula $F$ that agrees with $f$ on a $\frac{3}{4}$ fraction of inputs, i.e.,

We say that $F$ approximates $f$.

It is known that formulas can be balanced: $𝖣(f)=\mathrm{\Theta }(\log 𝖫(f))$ (see references in [10, Section 6.1]): this is proved by showing that, for any formula $F$, there exists an equivalent formula $F^{\prime }$ with $𝖫(F^{\prime })\le 𝖫{(F)}^{O(1)}$ and $𝖣(F^{\prime })\le O(\log 𝖫(F))$. The following theorem further refines this: by allowing a larger constant in the depth upper bound, one can control the size of the resulting balanced formula.

Using a counting argument, one can show that, with probability $1-o(1)$, for a random Boolean function $f\in {𝔹}_n$, $𝖫(f)=\mathrm{\Omega }(2^n/\log n)$. To prove this, one compares the number of small size formulas with the number of Boolean functions $|{𝔹}_n|=2^{2^n}$, using the following estimate (see [10, Lemma 1.23]). It ensures that the number of formulas of size at most $\frac{2^n}{100\log n}$ is $o(|{𝔹}_n|)$:

Karchmer and Wigderson [12] came up with the following characterization of Boolean formulas. For a Boolean function $f\in {𝔹}_n$, the Karchmer–Wigderson game ${\mathrm{𝖪𝖶}}_f$ is the following communication problem. Alice is given $a\in f^{-1}(1)$, whereas Bob is given $b\in f^{-1}(0)$, and their goal is to find an index $i\in [n]$ such that $a_i\ne b_i$. A communication protocol for ${\mathrm{𝖪𝖶}}_f$ is a rooted binary tree whose leaves are labeled with indices from $[n]$ and each internal node $v$ is labeled either by a function $A_v:f^{-1}(1)\to \{0,1\}$ or by a function $B_v:f^{-1}(0)\to \{0,1\}$. For any pair $(a,b)\in f^{-1}(1)\times f^{-1}(0)$, one can reach a leaf of the protocol by traversing a path from the root to a leaf to determine to which of the two children to proceed from a node $v$, one computes either $A_v(a)$ or $B_v(b)$. We say that a protocol solves ${\mathrm{𝖪𝖶}}_f$, if for any $(a,b)\in f^{-1}(1)\times f^{-1}(0)$, one reaches a leaf $i\in [n]$ such that $a_i\ne b_i$. Similarly to formulas, we say that a protocol separates a combinatorial rectangle $A\times B$, if it works correctly for all pairs $(a,b)\in A\times B$.

Karchmer and Wigderson showed that formulas computing $f$ and protocols solving ${\mathrm{𝖪𝖶}}_f$ can be transformed (even mechanically) into one another. In particular, the smallest number of leaves in the protocol solving ${\mathrm{𝖪𝖶}}_f$ is equal to $𝖫(f)$, whereas the smallest depth of a protocol (also known as the communication complexity of ${\mathrm{𝖪𝖶}}_f$, denoted by $\mathrm{𝖢𝖢}({\mathrm{𝖪𝖶}}_f)$) is nothing else but $𝖣(f)$. By $𝖫(A\times B)$ for a combinatorial rectangle $A\times B$, we denote the minimum number of leaves in a protocol separating $A$ and $B$.

With each node of a protocol solving ${\mathrm{𝖪𝖶}}_f$, one can associate a combinatorial rectangle in a natural way. The root of the protocol corresponds to $R_f$. For the two children of Alice’s node $v$ with a rectangle $A\times B$, one associates two rectangles $A_0\times B$ and $A_1\times B$, where $A_i=\{a\in A:A_v(a)=i\}$. This way, Alice splits the current rectangle horizontally. Similarly, when Bob speaks, he splits the current rectangle vertically. Each leaf of a protocol solving ${\mathrm{𝖪𝖶}}_f$ is associated with a monochromatic rectangle, i.e., a rectangle $A\times B$ such that there exists $i\in [n]$ for which $a_i\ne b_i$ for all $(a,b)\in A\times B$.

For functions $f\in {𝔹}_m$ and $g\in {𝔹}_n$, the strong composition of ${\mathrm{𝖪𝖶}}_f$ and ${\mathrm{𝖪𝖶}}_g$, denoted as ${\mathrm{𝖪𝖶}}_f⊛{\mathrm{𝖪𝖶}}_g$, is the following communication problem: Alice and Bob receive inputs $X\in {(f\diamond g)}^{-1}(1)$ and $Y\in {(f\diamond g)}^{-1}(0)$, respectively, and need to find indices $(i,j)$ such that $X_{i,j}\ne Y_{i,j}$ and $g(X_i)\ne g(Y_i)$. We say that a protocol strongly separates sets $𝒳\subseteq {(f\diamond g)}^{-1}(1)$ and $𝒴\subseteq {(f\diamond g)}^{-1}(0)$, if it solves the strong composition ${\mathrm{𝖪𝖶}}_f⊛{\mathrm{𝖪𝖶}}_g$ on inputs $𝒳\times 𝒴$.

For $f\in {𝔹}_n$, define a bipartite graph $G_f(f^{-1}(1)\bigsqcup f^{-1}(0),E_f)$ as follows:

where $d_H$ is the Hamming distance. Khrapchenko [13] proved that, for any $f\in {𝔹}_n$, $\psi (G_f)\le 𝖫(f)$ (recall (3) for the definition of $\psi (G)$). This immediately gives a lower bound $𝖫({\mathrm{𝖷𝖮𝖱}}_n)\ge n^2$. Note the two useful properties of $\psi (G_f)$: on the one hand, it is a lower bound to $𝖫(f)$, on the other hand, it is much easier to estimate than $𝖫(f)$.

Paterson [19, Section 8.8] noted that Khrapchenko’s approach can be cast as follows. A function $\mu :{𝔹}_n\to {𝖱}_{+}$ is called a formal complexity measure if it satisfies the following two properties:

1. 1.

   normalization: $\mu (x_i),\mu (\overline{x_i})\le 1$, for all $i\in [n]$,

2. 2.

   subadditivity: $\mu (f\vee g)\le \mu (f)+\mu (g)$ and $\mu (f\wedge g)\le \mu (f)+\mu (g)$, for all $f,g\in {𝔹}_n$.

Note that Khrapchenko’s measure can be defined in this notation as $\varphi (f)=\psi (G_f)$. Its subadditivity is shown in Lemma 4, whereas the normalization property can be easily seen.

It is not difficult to see that $𝖫$ itself is a formal complexity measure. Moreover, it turns out that it is the largest formal complexity measure.

We start by proving a lower bound on the size of any protocol solving ${\mathrm{𝖪𝖶}}_{{\mathrm{𝖷𝖮𝖱}}_m}⊛{\mathrm{𝖪𝖶}}_f$ and having a logarithmic depth. Then, using balancing techniques (see Theorem 7), we generalize the size lower bound to all protocols.

Fix a set $𝒵\subseteq {\{0,1\}}^{\log m}$ such that $|𝒵|=0.98m$ and $f$ is balanced on $𝒵$: $|{𝒳}_0|=|{𝒴}_0|=0.49m$, where ${𝒳}_0=f^{-1}(1)\cap 𝒵$ and ${𝒴}_0=f^{-1}(0)\cap 𝒵$.

We prove a lower bound for any protocol that strongly separates ${\mathrm{𝖪𝖶}}_{{\mathrm{𝖷𝖮𝖱}}_m}⊛{\mathrm{𝖪𝖶}}_f$ on inputs ${𝒳}_T\times {𝒴}_T$ (which are defined later). To this end, we associate, with nodes of the protocol, a graph similar to $G_{{\mathrm{𝖷𝖮𝖱}}_m}$ and use Khrapchenko’s measure to track the progress of the protocol. A node of the graph is associated with all inputs $X$ having the same vector $f(X)$. The reasoning is that, in a natural scenario, the protocol will first solve ${\mathrm{𝖷𝖮𝖱}}_m$, followed by solving $f$, implying that the protocol does not need to distinguish between $X$ and $X^{\prime }$ in the initial rounds, if $f(X)=f(X^{\prime })$. We connect two graph nodes by an edge if their vectors differ in exactly one coordinate.

We aim to ensure that each edge in the graph has a large projection: for any two nodes connected by an edge, the elements of blocks associated with them cover a substantial number of inputs for the function $f$. There will be no small protocol capable of solving the problem within these two blocks since $f$ is hard to approximate. This is the rationale behind ensuring that all edges in the graph have large projections on both sides. To achieve this, we enforce that each block that is associated with a node shrinks by at most a factor of two at each step of the protocol. This process ensures that a significant number of edges in the graph will maintain large projections on both sides.

Once the Khrapchenko measure becomes sufficiently small, we can assert that ${\mathrm{𝖷𝖮𝖱}}_m$ is nearly solved, and the protocol, in a sense, must now solve an instance of ${\mathrm{𝖮𝖱}}_d⊛f$. Using the fact that solving each edge independently is hard, we conclude that solving an ${\mathrm{𝖮𝖱}}_d⊛f$ over these edges should be as difficult as approximately $d\cdot {𝖫}_{\frac{3}{4}}(f)$.

Throughout this section, we assume that $m$ is large enough and $f\in {𝔹}_{\log m}$ is a fixed function that is $0.49$-balanced. Fix sets ${𝒳}_0\subseteq f^{-1}(1),{𝒴}_0\subseteq f^{-1}(0)$ of size $0.49m$ and let

Let $\alpha >0$ be a constant and $P$ be a protocol that strongly separates ${𝒳}_T\times {𝒴}_T$ and has depth at most $\alpha \log m$. Recall that each node $S$ of $P$ is associated with a rectangle ${𝒳}_S\times {𝒴}_S$. We build a subtree $D$ of $P$ having the same root and associate a graph $G_N$ to every node $N$ of $D$. The graphs $G_N$ are built inductively from the graphs associated with the parents of $N$ as explained below, but all these graphs are subsets of the $m$-dimensional hypercube: the set of nodes of each such graph is a subset of ${\{0,1\}}^m$ and for each edge $\{u,v\}$ it holds that $d_H(u,v)=1$.

For the root $T$ of the protocol $P$, the graph $G_T$ is simply $G_{{\mathrm{𝖷𝖮𝖱}}_m}$ (which is nothing else but the $m$-dimensional hypercube): its set of nodes is ${\{0,1\}}^m$, two nodes are joined by an edge with label $i$ if they differ in the $i$-th coordinate.

For any node $v$ of the graph $G_S$, we associate the following set of inputs called block:

We say that an edge $\{u,v\}$ with label $i$ of $G_S$ is heavy if the projection of both ${ℬ}_S(u)$ and ${ℬ}_S(v)$ onto the $i$th coordinate is dense, i.e.,

and light otherwise.

Since the nodes of the graph $G_S$ form a subset of ${\{0,1\}}^m$, we can naturally divide them into two parts, as their blocks correspond to subsets of either ${𝒳}_S$ or ${𝒴}_S$.

For a graph $G_S$, we define $d_A(G_S)$ as the average degree of the part $A_S$ and $d_B(G_S)$ as the average degree of the part $B_S$. We say that a graph $G_S$ is special if

We will construct the tree $D$ inductively. For a node $S$ in the tree $D$, we either stop the process if $G_S$ is special, or construct the two children of $S$ from the protocol $P$ and their graphs. We continue building $D$ on these two children inductively. Hence, all graphs corresponding to internal nodes of the tree $D$ are not special, while all graphs associated with leaves of $D$ are special.

We will ensure that all graphs $G_S$ for any node $S$ in the tree $D$ are adjusted.