An improved deterministic \#SAT algorithm for small De Morgan formulas
type: Item
instance of: scholarly article
title: An improved deterministic \#SAT algorithm for small De Morgan formulas
zbMATH Open document ID: 1353.68115
author: Ruiwen Chen
author: Valentine Kabanets
author: Nitin Saurabh
published in: Algorithmica
publication date: 2016-11-01T00:00:00Z
full work available at URL: Chen Kabanets ET AL 2014 An Improved Deterministic sat algorithm for small de morgan formulas.pdf
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6646533
zbMATH Keywords: De Morgan formulas
zbMATH Keywords: random restrictions
zbMATH Keywords: shrinkage exponent
zbMATH Keywords: concentrated shrinkage
zbMATH Keywords: algorithms from circuit lower bounds
zbMATH Keywords: deterministic \#SAT algorithms
MaRDI profile type: Publication
OpenAlex ID: W2167866552
cites work: Q3772136
cites work: Mining circuit lower bound proofs for meta-algorithms
cites work: The Shrinkage Exponent of de Morgan Formulas is 2
cites work: Q5743451
cites work: Pseudorandomness from Shrinkage
cites work: The effect of random restrictions on formula size
cites work: Average-case lower bounds for formula size
cites work: Shrinkage of de Morgan formulae under restriction
cites work: Q4484662
cites work: A satisfiability algorithm and average-case hardness for formulas over the full binary basis
cites work: Q3281059
cites work: Improving exhaustive search implies superpolynomial lower bounds
DOI: 10.1007/S00453-015-0020-Z
description: scientific article; zbMATH DE number 6646533