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