Improving $3N$ Circuit Complexity Lower Bounds
- 16 December 2023
- journal article
- research article
- Published by Springer Nature in computational complexity
- Vol. 32 (2) , 1-82
Abstract
No abstract availableKeywords
This publication has 48 references indexed in Scilit:
- Affine extractors over prime fieldsCombinatorica, 2011
- A measure & conquer approach for the analysis of exact algorithmsJournal of the ACM, 2009
- New methods for 3-SAT decision and worst-case analysisTheoretical Computer Science, 1999
- Shrinkage of de Morgan formulae under restrictionRandom Structures & Algorithms, 1993
- The effect of random restrictions on formula sizeRandom Structures & Algorithms, 1993
- A Boolean function requiring 3n network sizeTheoretical Computer Science, 1983
- On the combinational complexity of certain symmetric Boolean functionsTheory of Computing Systems, 1976
- The combinational complexity of equivalenceTheoretical Computer Science, 1976
- Method of determining lower bounds for the complexity of P-schemesMathematical Notes, 1971
- Beiträge zur Störungstheorie der SpektralzerleungMathematische Annalen, 1951