Mining circuit lower bound proofs for meta-algorithms

DOI10.1007/s00037-015-0100-0zbMath1401.68116OpenAlexW2053658780WikidataQ113906247 ScholiaQ113906247MaRDI QIDQ2351392

Antonina Kolokolova, David Zuckerman, Valentine Kabanets, Ruiwen Chen, Ronen Shaltiel

Publication date: 23 June 2015

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00037-015-0100-0

zbMATH Keywords

compressionrandom restrictionsaverage-case circuit lower boundscircuit-SAT algorithmsmeta-algorithmsnatural propertyshrinkage of De Morgan formulas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity ⋮ Zero-Fixing Extractors for Sub-Logarithmic Entropy ⋮ A Moderately Exponential Time Algorithm for k-IBDD Satisfiability ⋮ What Circuit Classes Can Be Learned with Non-Trivial Savings? ⋮ Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP ⋮ Circuit lower bounds from learning-theoretic approaches ⋮ An improved deterministic \#SAT algorithm for small De Morgan formulas ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ Improved exact algorithms for mildly sparse instances of MAX SAT ⋮ Proofs of Work from worst-case assumptions ⋮ Strong ETH and resolution via games and the multiplicity of strategies ⋮ Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ Algorithms and lower bounds for comparator circuits from shrinkage ⋮ Unnamed Item ⋮ Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound ⋮ Improving \(3N\) circuit complexity lower bounds ⋮ Solving sparse instances of Max SAT via width reduction and greedy restriction ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Agnostic Learning from Tolerant Natural Proofs ⋮ On the complexity of compressing obfuscation ⋮ Fourier concentration from shrinkage ⋮ A moderately exponential time algorithm for \(k\)-IBDD satisfiability ⋮ Average-case linear matrix factorization and reconstruction of low width algebraic branching programs ⋮ Satisfiability algorithm for syntactic read-\(k\)-times branching programs ⋮ Negation-limited formulas ⋮ Cubic Formula Size Lower Bounds Based on Compositions with Majority ⋮ Algorithms and lower bounds for de morgan formulas of low-communication leaf gates ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression ⋮ Unnamed Item ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• On derandomization and average-case complexity of monotone functions
• Boolean function complexity. Advances and frontiers.
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Approximation algorithms for combinatorial problems
• On the ratio of optimal integral and fractional covers
• Hardness vs randomness
• In search of an easy witness: Exponential time vs. probabilistic polynomial time.
• Natural Proofs versus Derandomization
• Improving exhaustive search implies superpolynomial lower bounds
• An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
• Constant depth circuits, Fourier transform, and learnability
• Invertible Zero-Error Dispersers and Defective Memory with Stuck-At Errors
• Circuit minimization problem
• Parity, circuits, and the polynomial-time hierarchy
• Circuit-size lower bounds and non-reducibility to sparse sets
• How to Generate Cryptographically Strong Sequences of Pseudorandom Bits
• Polylogarithmic independence fools AC ⁰ circuits
• Learning and Lower Bounds for AC 0 with Threshold Gates
• Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
• Polylogarithmic Independence Can Fool DNF Formulas
• The Complexity of Satisfiability of Small Depth Circuits
• A Greedy Heuristic for the Set-Covering Problem
• Simple Constructions of Almost k-wise Independent Random Variables
• The complexity of monotone boolean functions
• A Pseudorandom Generator from any One-way Function
• The Shrinkage Exponent of de Morgan Formulas is 2
• Shrinkage of de Morgan formulae under restriction
• Pseudorandomness from Shrinkage
• Efficient Learning Algorithms Yield Circuit Lower Bounds
• Computational Complexity
• Quadratic Goldreich-Levin Theorems
• Average-case lower bounds for formula size
• The complexity of theorem-proving procedures
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• Natural proofs
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Hardness of approximate two-level logic minimization and PAC learning with membership queries
• Pseudorandom generators without the XOR lemma
• Easiness assumptions and hardness tests: Trading time for zero error