<p>On techniques for proving poly-log circuit-depth lower bounds, all current approaches work under <em>restricted</em> settings.
Like, in the <a href="http://dx.doi.org/10.1137/S0097539794282930">work leading to GCT</a> that you mention, the lower bound applies to a restricted PRAM model without bit operations.</p>

<p>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 (<a href="http://eccc.hpi-web.de/report/2012/185/">ECCC</a> and <a href="http://dx.doi.org/10.1145/2213977.2214024">STOC</a>).
This improves on an earlier <a href="http://dx.doi.org/10.1007/s004930050062">result</a> by Ran Raz and Pierre McKenzie, which extends the <a href="http://dx.doi.org/10.1137/0403021">communication game framework</a> of Mauricio Karchmer and Avi Wigderson concerning circuit-depth.</p>

<p>Another line of research to extend the Karchmer–Wigderson game was proposed as a <a href="http://doi.acm.org/10.1145/1490270.1490272">referred communication game</a> 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 (<a href="http://eccc.hpi-web.de/report/2011/122">ECCC</a> and <a href="http://dx.doi.org/10.1145/2422436.2422487">ITCS</a>).</p>

<p>Apart from studying the syntactic restriction of monotonicity, there is an <a href="http://doi.acm.org/10.1145/2077336.2077337">approach</a> 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 <a href="http://arxiv.org/abs/1101.2705">strong lower bound</a> under the thrifty restriction by Dustin Wehr, matching the best known <a href="http://doi.acm.org/10.1145/322003.322015">upper bound</a> 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]$).</p>

<p>About the question relating the size and depth of circuits, the following approach may be related.
Richard Lipton and Ryan Williams <a href="http://doi.ieeecomputersociety.org/10.1109/CCC.2012.44">show</a> 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 <a href="http://eccc.hpi-web.de/report/2008/038/">result</a> 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.</p>

<p>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 <a href="http://dx.doi.org/10.1137/S0097539794282930">Mulmuley</a>, the competing-prover protocol approach studied by <a href="http://eccc.hpi-web.de/report/2011/122">Kol–Raz</a>, and the size-depth trade-off approach of <a href="http://eccc.hpi-web.de/report/2008/038/">Allender–Koucký </a> and <a href="http://doi.ieeecomputersociety.org/10.1109/CCC.2012.44">Lipton–Williams</a> all concern both the size and the depth of circuits.
The results in <a href="http://eccc.hpi-web.de/report/2012/185/">Chan–Potechin</a>, <a href="http://dx.doi.org/10.1007/s004930050062">Raz–McKenzie</a>, <a href="http://doi.acm.org/10.1145/2077336.2077337">Cook–McKenzie–Wehr–Braverman–Santhanam</a>, and <a href="http://arxiv.org/abs/1101.2705">Wehr</a> give circuit-depth lower bounds under restricted settings regardless of size.
Also, the referred communication game of <a href="http://doi.acm.org/10.1145/1490270.1490272">Aaronson–Wigderson</a> concerns only circuit-depth.</p>

<p>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.</p>

CC BY-SA 3.0
2013-03-01T11:27:41.060Z
thanks! So far as you know, a statement which is in Q2 is not found by everyone, is it? That is,unlike communication complexity lower bound methods, we've not got any mathematical quantity giving the lower bounds of the NC circuit ?
shen
CC BY-SA 3.0
2013-03-01T12:34:00.230Z
@shen, I added two more paragraphs at the end. Hope that it is helpful.
siuman
CC BY-SA 3.0
2013-03-01T14:04:07.807Z
The idea that weak size lower bounds can be amplified, used in the Lipton–Williams paper, is actually due to Allender and Koucký (http://eccc.hpi-web.de/report/2008/038/).
Emil Jeřábek
CC BY-SA 3.0
2013-03-02T09:37:41.723Z
@EmilJeřábek Thanks! I added that paper. Hope that the answer looks better now.
siuman
CC BY-SA 3.0
2013-03-01T06:57:52.737Z
2013-03-02T09:37:08.540Z
2013-03-02T09:37:08.540Z
siuman
<p>Following the suggestion of Kaveh, I am putting my comment as an (expanded) answer.</p>
<p>
 <b>Concerning <span class="math-container">$Q1$</span></b>, a word of caution is in order: even <i>logarithmic</i> depth if far from being understood, not speaking about poly-logarithmic. So, in the non-monotone world, the real problem is much less ambitious:
<blockquote>
<b>Beating Log-depth Problem:</b> Prove a super-linear(!) lower bound for <span class="math-container">$NC^1$</span>-circuits.
</blockquote>
The problem remains open (for now more than 30 years) even for <i>linear</i> <span class="math-container">$NC^1$</span>-circuits. These are fanin-<span class="math-container">$2$</span> circuits over the basis <span class="math-container">$\{\oplus,1\}$</span>, and they compute linear transformations <span class="math-container">$f(x)=Ax$</span> over <span class="math-container">$GF(2)$</span>. Easy counting show that almost all matrices <span class="math-container">$A$</span> require 
<span class="math-container">$\Omega(n^2/\log n)$</span> gates, in any depth.
<p>
<b>Concerning <span class="math-container">$Q2$</span></b>: Yes, we <b>have</b> 
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 <span class="math-container">$NC^1$</span>-circuits, such a measure is the <a href="http://eccc.hpi-web.de/report/2005/070/" rel="nofollow noreferrer">rigidity</a> <span class="math-container">$R_A(r)$</span> of the matrix <span class="math-container">$A$</span>. This is the smallest number of entries of <span class="math-container">$A$</span> that one needs to change in order to reduce the rank to <span class="math-container">$r$</span>.
It is easy to <a href="https://web.vu.lt/mif/s.jukna/boolean/rigidity.html" rel="nofollow noreferrer">show</a> that <span class="math-container">$R_A(r)\leq (n-r)^2$</span> holds for every boolean <span class="math-container">$n\times n$</span> matrix <span class="math-container">$A$</span>, 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 <span class="math-container">$n\times n$</span> matrices <span class="math-container">$A$</span> such that
<blockquote>
<span class="math-container">$R_A(\epsilon n)\geq n^{1+\delta}$</span> for constants <span class="math-container">$\epsilon,\delta&gt;0$</span>.
</blockquote> 
The best we know so far are matrices <span class="math-container">$A$</span> with <span class="math-container">$R_A(r)\geq (n^2/r)\log(n/r)$</span>. For Sylvester matrices (i.e. inner product matrices), the lower bound of <span class="math-container">$\Omega(n^2/r)$</span> is <a href="http://blog.computationalcomplexity.org/2005/07/matrix-rigidity.html" rel="nofollow noreferrer">easy to show</a>.
<p>
We have combinatorial measures for general (non-linear) <span class="math-container">$NC^1$</span>-circuits, as well For a bipartite <span class="math-container">$n\times n$</span>
graph <span class="math-container">$G$</span>, let <span class="math-container">$t(G)$</span> be the smallest number <span class="math-container">$t$</span> such that <span class="math-container">$G$</span> can be written as an intersection
of <span class="math-container">$t$</span> bipartite graphs, each being a union of at most <span class="math-container">$t$</span> complete bipartite graphs. To beat
the general log-depth circuits, it would be enough to find a sequence of graphs with
<blockquote> 
<span class="math-container">$t(G_n)\geq n^{\epsilon}$</span> for a constant <span class="math-container">$\epsilon &gt;0$</span>
</blockquote> 
(see, e.g. <a href="https://web.vu.lt/mif/s.jukna/ftp/graph-compl.pdf" rel="nofollow noreferrer">here</a> on how this happens). Again, almost all graphs have
<span class="math-container">$t(G)\geq n^{1/2}$</span>. However, the best remains a lower bound <span class="math-container">$t(G)\geq \log^3 n$</span> for Sylvester matrices, due to <a href="http://dx.doi.org/10.1007/s00224-002-1068-0" rel="nofollow noreferrer">Lokam</a>.
<p>
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 <span class="math-container">$n\times n$</span> graph <span class="math-container">$G$</span>, let <span class="math-container">$c(G)$</span> be the smallest number of
fanin-<span class="math-container">$2$</span> union (<span class="math-container">$\cup$</span>) and intersection (<span class="math-container">$\cap$</span>) operations required to produce <span class="math-container">$G$</span> 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 <span class="math-container">$c(G)=\Omega(n^2/\log n)$</span>. On the other hand, a lower bound of 
<blockquote>
<span class="math-container">$c(G_n)\geq (4+\epsilon)n$</span> for a constant <span class="math-container">$\epsilon&gt;0$</span>
</blockquote>
would imply a lower bound <span class="math-container">$\Omega(2^{N/2})$</span> on the non-monotone circuit complexity of an explicit boolean function <span class="math-container">$f_G$</span> of <span class="math-container">$N$</span> variables. If <span class="math-container">$G$</span> is <span class="math-container">$n\times m$</span> graph with <span class="math-container">$m=o(n)$</span>, then even a lower bound   <span class="math-container">$c(G_n)\geq (2+\epsilon)n$</span> is enough (again, see, e.g. hereon how this happens). Lower bounds <span class="math-container">$c(G)\geq (2-\epsilon)n$</span> can be shown for relatively simple graphs. The problem, however, is to do this with "<span class="math-container">$-\epsilon$</span>" replaced by "<span class="math-container">$+\epsilon$</span>".  More combinatorial measures lower-bounding circuit complexity (including the <span class="math-container">$ACC$</span>-circuits) 
can be found in the
 [book](https://web.vu.lt/mif/s.jukna/boolean/index.html). 
 <p>
P.S. So,
are we by a constant factor of <span class="math-container">$2+\epsilon$</span> from showing <span class="math-container">$P\neq NP$</span>?
Of course - not.
I mentioned this latter measure <span class="math-container">$c(G)$</span> 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 <i>something</i> about what properties of functions make them computationally hard. This may be useful for proving an <i>indirect</i> lower bound: some complexity class contains a function requiring large circuits or formulas. But the ultimate goal is to come up with an <i>explicit</i> hard function, whose definition does not have an "algorithmic smell", does not have any hidden complexity aspects. 

CC BY-SA 3.0
2013-03-02T21:12:05.610Z
I find this very interesting: 1. superlinear lower-bound for linear functions over $GF(2)$ seems a very concrete lower-bound question. 2. lower-bounds on mathematical concepts not directly related to computation are related to circuit lower-bound.
Kaveh
CC BY-SA 3.0
2013-03-03T15:06:17.157Z
matrix rigidity is an apparently unifying concept however its structure seems in strong contrast to almost all lower bounds expressed as $\Omega(f(n))$, whereas it is in terms instead of $\Omega(f(n,r))$ (or say $\Omega(f({\sqrt n},r))$ where $n$ is input size because its for square matrices). has anyone seen other ways to express matrix rigidity eg in terms of $\Omega(f(n))$?
vzn
CC BY-SA 3.0
2013-03-03T20:23:10.113Z
@vzn: The strongest lower bound on $R_A(r)$ *independent* or $r$ is $0$, because $R_A(n)=0$. I am afraid, you misinterpret what rigidity actually means.
Stasys
CC BY-SA 4.0
2013-03-02T19:04:00.427Z
2022-02-11T19:42:04.043Z
2022-02-11T19:42:04.043Z
Stasys
<p>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.</p>

<p>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.</p>

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

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

<p>Second, how useful is the following statement for the theory community?</p>

<p>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. </p>

CC BY-SA 3.0
2013-03-01T12:11:50.683Z
A word of caution is in order: even *logarithmic* depth if far from being understood. We still have no super-linear(!) lower bound for NC^1-circuits. Here, matrix rigidity is a desired "combinatorial quantity", but we lack strong enough lower bounds on this quantity. Even more depressingly, no super-linear lower bound is known for NC^1-circuits computing a linear transformation f(x)=Ax over GF(2), even if only fanin-2 XOR's are allowed as gates. (Almost all matrices A then require about n^2/\log n gates, in any depth.)
Stasys
CC BY-SA 3.0
2013-03-02T07:23:35.073Z
@Stasys, I think your comment can be an answer.
Kaveh
<cc.complexity-theory><circuit-complexity><lower-bounds><dc.parallel-comp><gct>
Status on circuit lower bounds for polylog-bounded depth circuits
shen
# Status on circuit lower bounds for polylog-bounded depth circuits

(Asked by: username_0 on 2013-03-01)

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.

**Tags:** cc.complexity-theory, circuit-complexity, lower-bounds, dc.parallel-comp, gct
> **Comments:**
> **username_1**: A word of caution is in order: even *logarithmic* depth if far from being understood. We still have no super-linear(!) lower bound for NC^1-circuits. Here, matrix rigidity is a desired "combinatorial quantity", but we lack strong enough lower bounds on this quantity. Even more depressingly, no super-linear lower bound is known for NC^1-circuits computing a linear transformation f(x)=Ax over GF(2), even if only fanin-2 XOR's are allowed as gates. (Almost all matrices A then require about n^2/\log n gates, in any depth.)  
> **username_2**: @Stasys, I think your comment can be an answer.  

---

## 2 answers

### Answer by username_3 on 2013-03-01. Score: 16

On techniques for proving poly-log circuit-depth lower bounds, all current approaches work under *restricted* settings.
Like, in the [work leading to GCT](http://dx.doi.org/10.1137/S0097539794282930) 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](http://eccc.hpi-web.de/report/2012/185/) and [STOC](http://dx.doi.org/10.1145/2213977.2214024)).
This improves on an earlier [result](http://dx.doi.org/10.1007/s004930050062) by Ran Raz and Pierre McKenzie, which extends the [communication game framework](http://dx.doi.org/10.1137/0403021) 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](http://doi.acm.org/10.1145/1490270.1490272) 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](http://eccc.hpi-web.de/report/2011/122) and [ITCS](http://dx.doi.org/10.1145/2422436.2422487)).

Apart from studying the syntactic restriction of monotonicity, there is an [approach](http://doi.acm.org/10.1145/2077336.2077337) 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](http://arxiv.org/abs/1101.2705) under the thrifty restriction by Dustin Wehr, matching the best known [upper bound](http://doi.acm.org/10.1145/322003.322015) 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](http://doi.ieeecomputersociety.org/10.1109/CCC.2012.44) 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](http://eccc.hpi-web.de/report/2008/038/) 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](http://dx.doi.org/10.1137/S0097539794282930), the competing-prover protocol approach studied by [Kol–Raz](http://eccc.hpi-web.de/report/2011/122), and the size-depth trade-off approach of [Allender–Koucký](http://eccc.hpi-web.de/report/2008/038/)  and [Lipton–Williams](http://doi.ieeecomputersociety.org/10.1109/CCC.2012.44) all concern both the size and the depth of circuits.
The results in [Chan–Potechin](http://eccc.hpi-web.de/report/2012/185/), [Raz–McKenzie](http://dx.doi.org/10.1007/s004930050062), [Cook–McKenzie–Wehr–Braverman–Santhanam](http://doi.acm.org/10.1145/2077336.2077337), and [Wehr](http://arxiv.org/abs/1101.2705) give circuit-depth lower bounds under restricted settings regardless of size.
Also, the referred communication game of [Aaronson–Wigderson](http://doi.acm.org/10.1145/1490270.1490272) 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.

> **Comments:**
> **username_0**: thanks! So far as you know, a statement which is in Q2 is not found by everyone, is it? That is,unlike communication complexity lower bound methods, we've not got any mathematical quantity giving the lower bounds of the NC circuit ?  
> **username_3**: @shen, I added two more paragraphs at the end. Hope that it is helpful.  
> **username_4**: The idea that weak size lower bounds can be amplified, used in the Lipton–Williams paper, is actually due to Allender and Koucký (http://eccc.hpi-web.de/report/2008/038/).  
> **username_3**: @EmilJeřábek Thanks! I added that paper. Hope that the answer looks better now.  

---

### Answer by username_1 on 2013-03-02. Score: 14

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](http://eccc.hpi-web.de/report/2005/070/) $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](https://web.vu.lt/mif/s.jukna/boolean/rigidity.html) 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](http://blog.computationalcomplexity.org/2005/07/matrix-rigidity.html).

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](https://web.vu.lt/mif/s.jukna/ftp/graph-compl.pdf) 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](http://dx.doi.org/10.1007/s00224-002-1068-0).

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.

> **Comments:**
> **username_2**: I find this very interesting: 1. superlinear lower-bound for linear functions over $GF(2)$ seems a very concrete lower-bound question. 2. lower-bounds on mathematical concepts not directly related to computation are related to circuit lower-bound.  
> **username_5**: matrix rigidity is an apparently unifying concept however its structure seems in strong contrast to almost all lower bounds expressed as $\Omega(f(n))$, whereas it is in terms instead of $\Omega(f(n,r))$ (or say $\Omega(f({\sqrt n},r))$ where $n$ is input size because its for square matrices). has anyone seen other ways to express matrix rigidity eg in terms of $\Omega(f(n))$?  
> **username_1**: @vzn: The strongest lower bound on $R_A(r)$ *independent* or $r$ is $0$, because $R_A(n)=0$. I am afraid, you misinterpret what rigidity actually means.  

---

