ECCC-Report TR21-023https://eccc.weizmann.ac.il/report/2021/023Comments and Revisions published for TR21-023en-usSun, 21 Feb 2021 08:59:55 +0200
Paper TR21-023
| $3.1n - o(n)$ Circuit Lower Bounds for Explicit Functions |
Tianqi Yang,
Jiatu Li
https://eccc.weizmann.ac.il/report/2021/023Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function $f:\mathbb{F}_2^n\to\mathbb{F}_2$ requires circuit of size $\Omega(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 $3n-o(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+\frac{1}{86})n-o(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.1n - o(n)$ for affine dispersers. To get this result, we strengthen the gate elimination approach for $(3+\frac{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.Sun, 21 Feb 2021 08:59:55 +0200https://eccc.weizmann.ac.il/report/2021/023