An improved deterministic \#SAT algorithm for small De Morgan formulas

DOI10.1007/S00453-015-0020-ZMaRDI QIDQ334923zbMATH OpenOpenAlexFDO

Authors Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

Publication date 1 November 2016

Published in Algorithmica (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

zbMATH Keywords

algorithms from circuit lower boundsconcentrated shrinkageDe Morgan formulasdeterministic \#SAT algorithmsrandom restrictionsshrinkage exponent

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Shrinkage of de Morgan formulae under restriction
• Algorithms and Computation
• The Shrinkage Exponent of de Morgan Formulas is 2
• Improved average-case lower bounds for De Morgan formula size: matching worst-case lower bound

Cites work

• scientific article; zbMATH DE number 3162894 (Why is no real title available?)
• scientific article; zbMATH DE number 4031582 (Why is no real title available?)
• scientific article; zbMATH DE number 1452705 (Why is no real title available?)
• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• A satisfiability algorithm for \(\mathrm{AC}^0\)
• Average-case lower bounds for formula size
• Improving exhaustive search implies superpolynomial lower bounds
• Mining circuit lower bound proofs for meta-algorithms
• Pseudorandomness from shrinkage
• Shrinkage of de Morgan formulae under restriction
• The Shrinkage Exponent of de Morgan Formulas is 2
• The effect of random restrictions on formula size

Cited in

(5)

• Shrinkage of de Morgan formulae under restriction
• DNF sparsification and a faster deterministic counting algorithm
• An improved deterministic \#SAT algorithm for small De Morgan formulas
• Gate elimination: circuit size lower bounds and \#SAT upper bounds
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression

This page was built for publication: An improved deterministic \#SAT algorithm for small De Morgan formulas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q334923)