3.1n - o(n) circuit lower bounds for explicit functions

Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function f : F n 2 → F 2 requires circuit of size Ω(2 n /n) by a simple counting argument, it remains unknown whether there is an explicit function (for example, a function in NP) not computable by circuits of size 10n. In fact, a 3no(n) explicit lower bound by Blum (TCS, 1984) was unbeaten for over 30 years until a recent breakthrough by Find et al. (FOCS, 2016), which proved a (3 + 1 86 )no(n) lower bound for affine dispersers, a class of functions known to be constructible in P.

In this paper, we prove a stronger lower bound 3.1no(n) for affine dispersers. To get this result, we strengthen the gate elimination approach for (3 + 1 86 )n lower bound, by a more sophisticated case analysis that significantly decreases the number of bottleneck structures introduced during the elimination procedure. Intuitively, our improvement relies on three observations: adjacent bottleneck structures becomes less troubled; the gates eliminated are usually connected; and the hardest cases during gate elimination have nice local properties to prevent the introduction of new bottleneck structures.

later by Schnorr [Sch74]. Soon after, this lower bound was pushed up to 2.5n -O(1) for certain symmetric functions by Stockmeyer [Sto77] and a slightly weaker 2.5no(n) for combinations of storage access functions by Paul [Pau77]. The latter one was then improved by Blum [Blu84] to 3no(n) with a slightly modified function, which stood unbeaten for over thirty years. It was not