期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Proving circuit lower bounds has been an important but extremely hard problem for decades. Although one may show that almost every function f:Fn2F2 requires circuit of size (2nn) 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+186)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 31n−o(n) for affine dispersers. To get this result, we strengthen the gate elimination approach for (3+186)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.
