Mining circuit lower bound proofs for meta-algorithms (Q2351392): Difference between revisions

@@ Property / DOI @@
-.1007/s00037-015-0100-0
@@ Property / DOI: 10.1007/s00037-015-0100-0 / rank @@
-Normal rank
@@ Property / Wikidata QID @@
+Q113906247
@@ Property / Wikidata QID: Q113906247 / rank @@
+Normal rank
@@ Property / cites work @@
+FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
+Normal rank
@@ Property / cites work @@
+Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
+Normal rank
@@ Property / cites work @@
+Simple Constructions of Almost k-wise Independent Random Variables
+Normal rank
@@ Property / cites work @@
+Q3772136
@@ Property / cites work: Q3772136 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4938624
@@ Property / cites work: Q4938624 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Polylogarithmic Independence Can Fool DNF Formulas
+Normal rank
@@ Property / cites work @@
+How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
+Normal rank
@@ Property / cites work @@
+Q4385519
@@ Property / cites work: Q4385519 / rank @@
+Normal rank
@@ Property / cites work @@
+Polylogarithmic independence fools             <i>AC</i>             <sup>0</sup>             circuits
+Normal rank
@@ Property / cites work @@
+The Complexity of Satisfiability of Small Depth Circuits
+Normal rank
@@ Property / cites work @@
+An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
+Normal rank
@@ Property / cites work @@
+A Greedy Heuristic for the Set-Covering Problem
@@ Property / cites work: A Greedy Heuristic for the Set-Covering Problem / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of theorem-proving procedures
@@ Property / cites work: The complexity of theorem-proving procedures / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness of approximate two-level logic minimization and PAC learning with membership queries
+Normal rank
@@ Property / cites work @@
+Efficient Learning Algorithms Yield Circuit Lower Bounds
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+Normal rank
@@ Property / cites work @@
+Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors
+Normal rank
@@ Property / cites work @@
+Learning and Lower Bounds for AC 0 with Threshold Gates
+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 @@
+A Pseudorandom Generator from any One-way Function
+Normal rank
@@ Property / cites work @@
+Q3942397
@@ Property / cites work: Q3942397 / rank @@
+Normal rank
@@ Property / cites work @@
+In search of an easy witness: Exponential time vs. probabilistic polynomial time.
+Normal rank
@@ Property / cites work @@
+Q5743451
@@ Property / cites work: Q5743451 / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandomness from Shrinkage
@@ Property / cites work: Pseudorandomness from Shrinkage / rank @@
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for combinatorial problems
+Normal rank
@@ Property / cites work @@
+Boolean function complexity. Advances and frontiers.
+Normal rank
@@ Property / cites work @@
+Easiness assumptions and hardness tests: Trading time for zero error
+Normal rank
@@ Property / cites work @@
+Circuit minimization problem
@@ Property / cites work: Circuit minimization problem / rank @@
+Normal rank
@@ Property / cites work @@
+Derandomizing polynomial identity tests means proving circuit lower bounds
+Normal rank
@@ Property / cites work @@
+Circuit-size lower bounds and non-reducibility to sparse sets
+Normal rank
@@ Property / cites work @@
+On derandomization and average-case complexity of monotone functions
+Normal rank
@@ Property / cites work @@
+Average-case lower bounds for formula size
@@ Property / cites work: Average-case lower bounds for formula size / rank @@
+Normal rank
@@ Property / cites work @@
+Constant depth circuits, Fourier transform, and learnability
+Normal rank
@@ Property / cites work @@
+On the ratio of optimal integral and fractional covers
+Normal rank
@@ Property / cites work @@
+Q3249579
@@ Property / cites work: Q3249579 / rank @@
+Normal rank
@@ Property / cites work @@
+Q5545524
@@ Property / cites work: Q5545524 / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / 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 @@
+The complexity of monotone boolean functions
@@ Property / cites work: The complexity of monotone boolean functions / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
+Normal rank
@@ Property / cites work @@
+Q4850554
@@ Property / cites work: Q4850554 / rank @@
+Normal rank
@@ Property / cites work @@
+Natural proofs
@@ Property / cites work: Natural proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3918047
@@ Property / cites work: Q3918047 / 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 @@
+Q3281059
@@ Property / cites work: Q3281059 / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators without the XOR lemma
@@ Property / cites work: Pseudorandom generators without the XOR lemma / rank @@
+Normal rank
@@ Property / cites work @@
+Quadratic Goldreich-Levin Theorems
@@ Property / cites work: Quadratic Goldreich-Levin Theorems / rank @@
+Normal rank
@@ Property / cites work @@
+Q3762226
@@ Property / cites work: Q3762226 / rank @@
+Normal rank
@@ Property / cites work @@
+Improving exhaustive search implies superpolynomial lower bounds
+Normal rank
@@ Property / cites work @@
+Natural Proofs versus Derandomization
@@ Property / cites work: Natural Proofs versus Derandomization / rank @@
+Normal rank
@@ Property / DOI @@
+.1007/S00037-015-0100-0
@@ Property / DOI: 10.1007/S00037-015-0100-0 / rank @@
+Normal rank