Improving $3N$ circuit complexity lower bounds (Q6184294): Difference between revisions

@@ Property / cites work @@
+A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds
+Normal rank
@@ Property / cites work @@
+A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
+Normal rank
@@ Property / cites work @@
+Extractors for Polynomials Sources over Constant-Size Fields of Small Characteristic
+Normal rank
@@ Property / cites work @@
+Affine dispersers from subspace polynomials
@@ Property / cites work: Affine dispersers from subspace polynomials / rank @@
+Normal rank
@@ Property / cites work @@
+Short PCPs with Projection Queries
@@ Property / cites work: Short PCPs with Projection Queries / rank @@
+Normal rank
@@ Property / cites work @@
+A Boolean function requiring 3n network size
@@ Property / cites work: A Boolean function requiring 3n network size / rank @@
+Normal rank
@@ Property / cites work @@
+Q4258566
@@ Property / cites work: Q4258566 / rank @@
+Normal rank
@@ Property / cites work @@
+Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits
+Normal rank
@@ Property / cites work @@
+Mining circuit lower bound proofs for meta-algorithms
+Normal rank
@@ Property / cites work @@
+The Complexity of DNF of Parities
@@ Property / cites work: The Complexity of DNF of Parities / rank @@
+Normal rank
@@ Property / cites work @@
+Q5351929
@@ Property / cites work: Q5351929 / rank @@
+Normal rank
@@ Property / cites work @@
+An Elementary Proof of a 3n − o(n) Lower Bound on the Circuit Complexity of Affine Dispersers
+Normal rank
@@ Property / cites work @@
+New lower bounds on circuit size of multi-output functions
+Normal rank
@@ Property / cites work @@
+Extractors for varieties
@@ Property / cites work: Extractors for varieties / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity theory of parallel time and hardware
@@ Property / cites work: Complexity theory of parallel time and hardware / rank @@
+Normal rank
@@ Property / cites work @@
+A measure &amp; conquer approach for the analysis of exact algorithms
+Normal rank
@@ Property / cites work @@
+On the Limits of Gate Elimination
@@ Property / cites work: On the Limits of Gate Elimination / rank @@
+Normal rank
@@ Property / cites work @@
+Weighted Gate Elimination
@@ Property / cites work: Weighted Gate Elimination / rank @@
+Normal rank
@@ Property / cites work @@
+The Shrinkage Exponent of de Morgan Formulas is 2
@@ Property / cites work: The Shrinkage Exponent of de Morgan Formulas is 2 / rank @@
+Normal rank
@@ Property / cites work @@
+Beiträge zur Störungstheorie der Spektralzerlegung
+Normal rank
@@ Property / cites work @@
+Q5121895
@@ Property / cites work: Q5121895 / rank @@
+Normal rank
@@ Property / cites work @@
+The effect of random restrictions on formula size
@@ Property / cites work: The effect of random restrictions on formula size / rank @@
+Normal rank
@@ Property / cites work @@
+Q4708583
@@ Property / cites work: Q4708583 / rank @@
+Normal rank
@@ Property / cites work @@
+Method of determining lower bounds for the complexity of \(\Pi\)-circuits
+Normal rank
@@ Property / cites work @@
+Q5567891
@@ Property / cites work: Q5567891 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4398780
@@ Property / cites work: Q4398780 / rank @@
+Normal rank
@@ Property / cites work @@
+A new approach to proving upper bounds for MAX-2-SAT
+Normal rank
@@ Property / cites work @@
+Circuit Complexity and Multiplicative Complexity of Boolean Functions
+Normal rank
@@ Property / cites work @@
+New methods for 3-SAT decision and worst-case analysis
+Normal rank
@@ Property / cites work @@
+Explicit lower bound of             <i>4.5n - o(n)</i>             for boolena circuits
+Normal rank
@@ Property / cites work @@
+.1             <i>n</i>             −             <i>o</i>             (             <i>n</i>             ) circuit lower bounds for explicit functions
+Normal rank
@@ Property / cites work @@
+Q5545524
@@ Property / cites work: Q5545524 / rank @@
+Normal rank
@@ Property / cites work @@
+Shrinkage of de Morgan formulae under restriction
@@ Property / cites work: Shrinkage of de Morgan formulae under restriction / rank @@
+Normal rank
@@ Property / cites work @@
+A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
+Normal rank
@@ Property / cites work @@
+Cyclic Boolean circuits
@@ Property / cites work: Cyclic Boolean circuits / rank @@
+Normal rank
@@ Property / cites work @@
+Circuit Lower Bounds for Merlin–Arthur Classes
@@ Property / cites work: Circuit Lower Bounds for Merlin–Arthur Classes / rank @@
+Normal rank
@@ Property / cites work @@
+Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
+Normal rank
@@ Property / cites work @@
+The combinational complexity of equivalence
@@ Property / cites work: The combinational complexity of equivalence / rank @@
+Normal rank
@@ Property / cites work @@
+A satisfiability algorithm and average-case hardness for formulas over the full binary basis
+Normal rank
@@ Property / cites work @@
+Dispersers for Affine Sources with Sub-polynomial Entropy
+Normal rank
@@ Property / cites work @@
+An Introduction to Randomness Extractors
@@ Property / cites work: An Introduction to Randomness Extractors / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for polynomial evaluation and interpolation problems
+Normal rank
@@ Property / cites work @@
+On the combinational complexity of certain symmetric Boolean functions
+Normal rank
@@ Property / cites work @@
+Bemerkung zur vorstehenden Arbeit von Herrn Chevalley
+Normal rank
@@ Property / cites work @@
+Improving Exhaustive Search Implies Superpolynomial Lower Bounds
+Normal rank
@@ Property / cites work @@
+Nonuniform ACC Circuit Lower Bounds
@@ Property / cites work: Nonuniform ACC Circuit Lower Bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Affine extractors over prime fields
@@ Property / cites work: Affine extractors over prime fields / rank @@
+Normal rank
@@ Property / cites work @@
+A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
+Normal rank

Improving \(3N\) circuit complexity lower bounds (Q6184294): Difference between revisions

Revision as of 21:32, 23 August 2024

Statements

Identifiers

Sitelinks

Mathematics(1 entry)