Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

DOI10.1007/978-3-662-48054-0_19zbMath1465.68201OpenAlexW2223137809MaRDI QIDQ2946392

Ruiwen Chen

Publication date: 16 September 2015

Published in: Mathematical Foundations of Computer Science 2015 (Search for Journal in Brave)

Full work available at URL: https://www.pure.ed.ac.uk/ws/files/20054890/Chen_MFCS.pdf

zbMATH Keywords

random restrictionsatisfiability algorithmBoolean formulaaverage-case lower bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational aspects of satisfiability (68R07)

Related Items (3)

Unnamed Item ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Affine extractors over prime fields
• Mining circuit lower bound proofs for meta-algorithms
• Improving exhaustive search implies superpolynomial lower bounds
• An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
• Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
• A measure & conquer approach for the analysis of exact algorithms
• The Shrinkage Exponent of de Morgan Formulas is 2
• The effect of random restrictions on formula size
• Shrinkage of de Morgan formulae under restriction
• Pseudorandomness from Shrinkage
• Average-case lower bounds for formula size
• Which bases admit non-trivial shrinkage of formulae?

This page was built for publication: Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases