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 it can be shown that almost every function f:F2n→F2 requires circuit of size Ω(2n/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 3n−o(n) explicit lower bound by Blum (TCS, 1984) was unbeaten for over 30 years until a recent breakthrough by Find, Golovnev, Hirsch, and Kulikov (FOCS, 2016), which proved a (3+1/86)n−o(n) lower bound for affine dispersers, a class of functions known to be constructible in P. To obtain this improvement, Find, Golovnev, Hirsch, and Kulikov (FOCS, 2016) generalized the classical gate elimination method by keeping track of a bottleneck structure called troubled gates.