An improved deterministic \#SAT algorithm for small De Morgan formulas
DOI10.1007/S00453-015-0020-ZzbMATH Open1353.68115OpenAlexW2167866552MaRDI QIDQ334923FDOQ334923
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
Recommendations
algorithms from circuit lower boundsconcentrated shrinkageDe Morgan formulasdeterministic \#SAT algorithmsrandom restrictionsshrinkage exponent
Cites Work
- A satisfiability algorithm for \(\mathrm{AC}^0\)
- Mining circuit lower bound proofs for meta-algorithms
- Improving exhaustive search implies superpolynomial lower bounds
- Title not available (Why is that?)
- A satisfiability algorithm and average-case hardness for formulas over the full binary basis
- Title not available (Why is that?)
- The Shrinkage Exponent of de Morgan Formulas is 2
- Title not available (Why is that?)
- 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
Cited In (5)
- Shrinkage of de Morgan formulae under restriction
- An improved deterministic \#SAT algorithm for small De Morgan formulas
- DNF sparsification and a faster deterministic counting algorithm
- 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)
