Published: October 11, 2016
Author(s)
Magnus Find (NIST), Alexander Golovnev (New York University), Edward Hirsch (Steklov Institute of Mathematics at St. Petersburg), Alexander Kulikov (Steklov Institute of Mathematics at St. Petersburg)
Conference
Name: IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS 2016)
Dates: 10/09/2016 - 10/11/2016
Location: New Brunswick, New Jersey, United States
Citation: Proceedings. 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016), pp. 89-98
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.
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...
See full abstract
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.
Hide full abstract
Keywords
affine disperser; Boolean circuits; lower bounds
Control Families
None selected
) or https:// don't prove our archive is authentic, only that you securely accessed it. Note that we are working to fix that :)
