Improving the lower bound on size complexity of explicit functions and some limitations on subsequent improvements

by Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, Alexander Knop, and Alexander Kulikov

Oded's comments

For more than three decades, $3n-o(n)$ was the record lower bound on the size of circuits for an explicit function. The first paper improves this record to slightly about $3.01n$, whereas the second paper shows that the gate elimination method (which undelies all results of the current type) cannot yield a super-linear lower bound.

The original abstract of the first work

A better-than-3n lower bound for the circuit complexity of an explicit functions by Magnus Gausdal Find, Alexander Golovnev, Edward Hirsch, and Alexander Kulikov.

We consider Boolean circuits over the full binary basis. We prove a $(3+(1/86))n-o(n)$ lower bound on the size of such a circuit for an explicitly defined predicate, namely an affine disperser for sublinear dimension. This improves the $3n-o(n)$ bound of Norbert Blum (1984). The proof is based on the gate elimination technique extended with the following three ideas. We generalize the computational model by allowing circuits to contain cycles, this in turn allows us to perform affine substitutions. We use a carefully chosen circuit complexity measure to track the progress of the gate elimination process. Finally, we use quadratic substitutions that may be viewed as delayed affine substitutions.

See ECCC TR15-166.

The original abstract of the second work

On the Limits of Gate Elimination by Alexander Golovnev, Edward Hirsch, Alexander Knop, and Alexander Kulikov

Although a simple counting argument shows the existence of Boolean functions of exponential circuit complexity, proving superlinear circuit lower bounds for explicit functions seems to be out of reach of the current techniques. There has been a (very slow) progress in proving linear lower bounds with the latest record of $3\frac1{86}n-o(n)$. All known lower bounds are based on the so-called gate elimination technique. A typical gate elimination argument shows that it is possible to eliminate several gates from an optimal circuit by making one or several substitutions to the input variables and repeats this inductively. In this note we prove that this method cannot achieve linear bounds of $cn$ beyond a certain constant $c$, where $c$ depends only on the number of substitutions made at a single step of the induction.

See ECCC TR16-119.


Back to list of Oded's choices.