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$.
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.