Depth-3 Circuits for Inner Product

by Mika Goos, Ziyi Guan, Tiberiu Mosnoi

In light of our difficulty to surpass the $\exp(\Omega(\sqrt n))$ size lower bound for depth three (unbounded fan-in) circuits, we try to make progress by imposing some restrictions. The restriction considered in the current work is on the fan-in of the lowest level (e.g., fan-in two), and the specific function considered is the inner product (modulo 2).

(Before proceeeding, let me violate my vow (not to mention my own work) and call attention to a restriction (i.e., restricted model) introduced by Avi and myself, which did not receive much attention so far. See also follow-up works HERE and HERE.)

Back to the current paper, what puzzled me was how is it possible to improve over the straightforward circuit that computes the parity of the $n$ two-way products. One starting observation is that if we are guaranteed that the number of non-zero products is at most $n'= \beta n$, for a constant $\beta$ smaller than 1/2, then we can do better than the straightforward circuit by trying all possibilities for the locations of the non-zeero products; that is, consider the circuit

$$C(x,y) = \bigvee_{I:|I|\leq n'} (\bigwedge_{i\in I}(x_i \wedge y_i) \wedge \bigwedge_{i\in [n]-I} (\neq x_i \vee \ned y_i))$$

The question is what to do when the said number is larger than $n'$. Here the idea is to use the specific pattern of the $(x_i,y_i)$ pairs, and match indices with equal pattern to one another (leaving a pair out if the number of pairs is odd). Specifically, let $N_{a,b}(x,y)$ denote the number indices $i\in[n]$ such that $(x_i,y_i)=(a,b)$. Then, we can get convinced that all four numbers are even by guessing four corresponding perfect matching (each matching indices of equal pattern) and verifying them. Let $M$ denote the union of these four perfect matching, and $\mu_M:[n]\to[n]$ be a corresponding permutation that maps pairs of matched indices. Using an adequate collection of perfect matching denoted $C$, this yields the circuit
$$C(x,y) = \bigvee_{M: M \in C} (\bigwedge_{i\in[n]}((x_i,y_i)=(x_{\mu_M(i)},y_{\mu_M(i)})$$
where $(x,y) = (x',y)$ is implemented by $(x=x')\wedge(y=y')$
and $(z,z')$ is implemennted by $(z \vee \neq z')\wedge(\neg z \vee z')$.

The key observation is that if $N_{1,1}$ is larger than $n'= \beta n$, for a constant $\beta$ larger than 1/4, then we can make a significant saving over letting $C$ be the collection of all perfect matchings (over $[n]$). Intuitively, this is the case because the probability that a random perfect matching is good for $(x,y)$ is related to the entropy of a random variable $\zeta_{x,y}$ that equals $(a,b)$ with probability $N_{a,b}/n$. Specifically, the probability that a random perfect matching is good is exponentially vanishing (to base 2) in $(n/2) H(\zeta{x,y})$, and the exponent is bounded away from $n$ (e.g., is smaller than $0.99 n$) when $N_{1,1}(x,y)$ is larger than $n'$ (e.g., larger than $0.499 n$). (Dealing with odd $N_{a,b}$'s can be done by indicating an index that fits $(a,b)$ and should be left out.)

The upper bound holds by combining the circuit for small values of $N_{1,1}$ (i.e. the case of $N_{1,1}$ smaller than $n'$) with the circuit for large values of $N_{1,1}$, and optimizing the choice of $n'$. (Indeed, any $n'$ such that $n'/n$ is strictly between $1/4$ and $1/2$ would yield an improvement over the straightforward circuit.) Of course, the focus of the paper is on the lower bound, which is proved by selecting a hard distribution of instances. Interestingly, this distribution is obtained by setting each bit independently according to a biased coin; specifically, each bit is set to 1 with proability $2/3$.

The original abstract (lightly revised)

What is the $\Sigma_3^2$-circuit complexity (depth 3, bottom-fanin 2) of the $2n$-bit inner product function? The complexity is known to be exponential $2^{\alpha_n n}$ for some $\alpha_n=\Omega(1)$. We show that the limiting constant $\alpha=\limsup \alpha_n$ is between 0.847 and 0.965.

Determining $\alpha$ is one of the seemingly-simplest open problems about depth-3 circuits. The question was recently raised by Golovnev, Kulikov, and Williams (ITCS 2021) and Frankl, Gryaznov, and Talebanfard (ITCS 2022), who observed that $\alpha\in[0.5,1]$. To obtain our improved bounds, we analyse a covering LP that captures the $\Sigma_3^2$-complexity up to polynomial factors. In particular, our lower bound is proved by constructing a feasible solution to the dual LP.

See ECCC TR23-106.

Back to list of Oded's choices.