Gate elimination: Circuit size lower bounds and #SAT upper bounds
- 1 April 2018
- journal article
- research article
- Published by Elsevier in Theoretical Computer Science
- Vol. 719, 46-63
Abstract
No abstract availableKeywords
Funding Information
- MEXT (24106003)
- JSPS (26330011, 16H02782)
- John Mung Advanced Program of Kyoto University
- NSF (1319051)
- Government of the Russian Federation (14.Z50.31.0030)
- University of California, San Diego
This publication has 25 references indexed in Scilit:
- Affine Dispersers from Subspace PolynomialsSIAM Journal on Computing, 2012
- A well-mixed function with circuit complexity : Tightness of the Lachish–Raz-type boundsTheoretical Computer Science, 2011
- Affine extractors over prime fieldsCombinatorica, 2011
- Extractors And Rank Extractors For Polynomial Sourcescomputational complexity, 2009
- Circuit Lower Bounds for Merlin–Arthur ClassesSIAM Journal on Computing, 2009
- A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean FunctionsSIAM Journal on Computing, 1991
- A Boolean function requiring 3n network sizeTheoretical Computer Science, 1983
- A $2.5n$-Lower Bound on the Combinational Complexity of Boolean FunctionsSIAM Journal on Computing, 1977
- On the combinational complexity of certain symmetric Boolean functionsTheory of Computing Systems, 1976
- Zwei lineare untere Schranken für die Komplexität Boolescher FunktionenComputing, 1974