Status on circuit lower bounds for polylog-bounded depth circuits

Question

Bounded depth circuit complexity is one of the main areas of research within circuit complexity theory. This topic has origins in results like "the parity function is not in $AC^{0}$" and "the mod $p$ function is not computed by $AC^{0}[q]$", where $AC^0[q]$ is the class of languages decidable by non-uniform, constant depth, polynomial size, unbounded fan-in AND, OR, NOT and modulo $q$ gates, where $\gcd(p,q)=1$. However, getting concrete lower bounds results on polylogarithmic depth circuits seems to be out of reach by using classical methods like restricting inputs and approximating polynomials on finite fields.

I know a STOC'96 paper which leads to geometric complexity theory and which shows that efficient parallel computing using operations without bit-wise ones cannot compute the min-cost-flow problem.

This means that in certain limited settings, we can prove $NC$ lower bounds for some $P$-complete problem.

First, are there other methods or techniques that may be plausible approaches for proving polylogarithmic depth circuit lower bounds?

Second, how useful is the following statement for the theory community?

The size of an $NC$ circuit computing a Boolean function $f\colon\{0,1\}^{n}\rightarrow \{0,1\}$ is at least $l$, where $l$ is some mathematical quantity depending on the hardness of the target function $f$. The value of $l$ may be, for example, a combinatorial quantity like discrepancy, a linear algebraic quantity like the rank of certain type of matrix over a field, or some entirely new quantity which has not previously been used in complexity theory.

Answer 1

On techniques for proving poly-log circuit-depth lower bounds, all current approaches work under restricted settings. Like, in the work leading to GCT that you mention, the lower bound applies to a restricted PRAM model without bit operations.

Under another restriction, which is the monotone restriction for monotone boolean functions, there is a Fourier-analytic (or enumerative-combinatorial) approach for proving monotone circuit-depth lower bounds, in my joint work with Aaron Potechin (ECCC and STOC). This improves on an earlier result by Ran Raz and Pierre McKenzie, which extends the communication game framework of Mauricio Karchmer and Avi Wigderson concerning circuit-depth.

Another line of research to extend the Karchmer–Wigderson game was proposed as a referred communication game by Scott Aaronson and Avi Wigderson, whose extension to a competing-prover protocol is suggested as an approach to separate NC from P by Gillat Kol and Ran Raz (ECCC and ITCS).

Apart from studying the syntactic restriction of monotonicity, there is an approach to study a semantic restriction related to pebble games (called thrifty branching programs) by Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, and Rahul Santhanam. There is a strong lower bound under the thrifty restriction by Dustin Wehr, matching the best known upper bound for P-complete problems. These results concern deterministic space complexity, which lower bounds parallel time or circuit-depth by known simulation results (e.g. since $\text{AlternatingTime}[t] \subseteq \text{DeterministicSpace}[t]$).

About the question relating the size and depth of circuits, the following approach may be related. Richard Lipton and Ryan Williams show that, given a sufficiently strong lower bound on depth (i.e. $n^{1-O(1)}$), a weak size lower bound (i.e. $n^{1+\Omega(1)}$) can separate NC from P. This result follows from a size-depth trade-off argument based on block-respecting simulations. An earlier result on trading depth for size is due to Allender and Koucký based on the idea of self-reducibility, but it studied smaller complexity classes like NC$^1$ and NL.

Note that among the above mentioned approaches, some of them consider both the size and the depth of circuits, while other approaches consider only circuit-depth. In particular, the semi-algebro-geometric approach of Mulmuley, the competing-prover protocol approach studied by Kol–Raz, and the size-depth trade-off approach of Allender–Koucký and Lipton–Williams all concern both the size and the depth of circuits. The results in Chan–Potechin, Raz–McKenzie, Cook–McKenzie–Wehr–Braverman–Santhanam, and Wehr give circuit-depth lower bounds under restricted settings regardless of size. Also, the referred communication game of Aaronson–Wigderson concerns only circuit-depth.

It is still consistent with our knowledge that some P-complete problem cannot be computed by circuits of small depth (i.e. $\log^{O(1)}n$), regardless of size. If size does not matter for small depth circuits (of bounded fan-in), then perhaps it makes sense to focus more on circuit-depth, than to focus on the size of small depth circuits.

Answer 2

Following the suggestion of Kaveh, I am putting my comment as an (expanded) answer.

Concerning $Q1$, a word of caution is in order: even logarithmic depth if far from being understood, not speaking about poly-logarithmic. So, in the non-monotone world, the real problem is much less ambitious:

Beating Log-depth Problem: Prove a super-linear(!) lower bound for $NC^1$-circuits.

The problem remains open (for now more than 30 years) even for linear $NC^1$-circuits. These are fanin-$2$ circuits over the basis $\{\oplus,1\}$, and they compute linear transformations $f(x)=Ax$ over $GF(2)$. Easy counting show that almost all matrices $A$ require $\Omega(n^2/\log n)$ gates, in any depth.

Concerning $Q2$: Yes, we have some algebraic/combinatoric measures, lower bounds on which would beat log-depth circuits. Unfortunately, so far, we cannot prove large enough bounds on these measures. Say, for linear $NC^1$-circuits, such a measure is the rigidity $R_A(r)$ of the matrix $A$. This is the smallest number of entries of $A$ that one needs to change in order to reduce the rank to $r$. It is easy to show that $R_A(r)\leq (n-r)^2$ holds for every boolean $n\times n$ matrix $A$, and Valiant (1977) has shown that this bound is tight for almost all matrices. To beat log-depth circuits, it is enough to exhibit a sequence of boolean $n\times n$ matrices $A$ such that

$R_A(\epsilon n)\geq n^{1+\delta}$ for constants $\epsilon,\delta>0$.

The best we know so far are matrices $A$ with $R_A(r)\geq (n^2/r)\log(n/r)$. For Sylvester matrices (i.e. inner product matrices), the lower bound of $\Omega(n^2/r)$ is easy to show.

We have combinatorial measures for general (non-linear) $NC^1$-circuits, as well For a bipartite $n\times n$ graph $G$, let $t(G)$ be the smallest number $t$ such that $G$ can be written as an intersection of $t$ bipartite graphs, each being a union of at most $t$ complete bipartite graphs. To beat the general log-depth circuits, it would be enough to find a sequence of graphs with

$t(G_n)\geq n^{\epsilon}$ for a constant $\epsilon >0$

(see, e.g. here on how this happens). Again, almost all graphs have $t(G)\geq n^{1/2}$. However, the best remains a lower bound $t(G)\geq \log^3 n$ for Sylvester matrices, due to Lokam.

Finally, let me mention that we even have a "simple" combinatorial measure (quantity) a weak (linear) lower bound on which would yield even exponential(!) lower bounds for non-monotone circuits. For a bipartite $n\times n$ graph $G$, let $c(G)$ be the smallest number of fanin-$2$ union ($\cup$) and intersection ($\cap$) operations required to produce $G$ when starting from stars; a star is a set of edges joining one vertex with all vertices on the other side. Almost all graphs have $c(G)=\Omega(n^2/\log n)$. On the other hand, a lower bound of

$c(G_n)\geq (4+\epsilon)n$ for a constant $\epsilon>0$

would imply a lower bound $\Omega(2^{N/2})$ on the non-monotone circuit complexity of an explicit boolean function $f_G$ of $N$ variables. If $G$ is $n\times m$ graph with $m=o(n)$, then even a lower bound $c(G_n)\geq (2+\epsilon)n$ is enough (again, see, e.g. hereon how this happens). Lower bounds $c(G)\geq (2-\epsilon)n$ can be shown for relatively simple graphs. The problem, however, is to do this with "$-\epsilon$" replaced by "$+\epsilon$". More combinatorial measures lower-bounding circuit complexity (including the $ACC$-circuits) can be found in the [book](https://web.vu.lt/mif/s.jukna/boolean/index.html).

P.S. So, are we by a constant factor of $2+\epsilon$ from showing $P\neq NP$? Of course - not. I mentioned this latter measure $c(G)$ only to show that one should treat "amplification" (or "magnification") of lower bounds with a healthy portion of skepticism: even though the bounds we need look "innocently", are much smaller (linear) than almost all graphs require (quadratic), the inherent difficulty of proving a (weak) lower bound may be even bigger. Of course, having found a combinatorial measure, we can say something about what properties of functions make them computationally hard. This may be useful for proving an indirect lower bound: some complexity class contains a function requiring large circuits or formulas. But the ultimate goal is to come up with an explicit hard function, whose definition does not have an "algorithmic smell", does not have any hidden complexity aspects.