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

DOI10.1007/s00453-015-0020-zzbMath1353.68115OpenAlexW2167866552MaRDI QIDQ334923

Valentine Kabanets, Nitin Saurabh, Ruiwen Chen

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

random restrictionsshrinkage exponentalgorithms from circuit lower boundsconcentrated shrinkageDe Morgan formulasdeterministic \#SAT algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

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

Cites Work

• A satisfiability algorithm and average-case hardness for formulas over the full binary basis
• Mining circuit lower bound proofs for meta-algorithms
• Improving exhaustive search implies superpolynomial lower bounds
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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