An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
From MaRDI portal
Publication:2922605
DOI10.1007/978-3-662-44465-8_15zbMath1353.68114OpenAlexW5136647MaRDI QIDQ2922605
Nitin Saurabh, Ruiwen Chen, Valentine Kabanets
Publication date: 14 October 2014
Published in: Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)
Full work available at URL: https://www.pure.ed.ac.uk/ws/files/19354981/Chen_Kabanets_ET_AL_2014_An_Improved_Deterministic_sat_algorithm_for_small_de_morgan_formulas.pdf
Related Items (12)
Local Reductions ⋮ Improved Algorithms for Sparse MAX-SAT and MAX-k-CSP ⋮ Correlation bounds and \#SAT algorithms for small linear-size circuits ⋮ Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits ⋮ Strong ETH and resolution via games and the multiplicity of strategies ⋮ Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Fourier concentration from shrinkage ⋮ Negation-limited formulas ⋮ Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs ⋮ Mining circuit lower bound proofs for meta-algorithms
This page was built for publication: An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas
