Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with SAT algorithms:
TR05-030 | 12th February 2005
Evgeny Dantsin, Alexander Wolpert

An Improved Upper Bound for SAT

We give a randomized algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its running time is at most $2^{n(1-1/\alpha)}$ up to a polynomial factor, where $\alpha = \ln(m/n) + O(\ln \ln m)$ and $n$, $m$ are respectively the number of variables ... more >>>

TR13-024 | 7th February 2013
Valentine Kabanets, Antonina Kolokolova

Compression of Boolean Functions

We consider the problem of compression for ``easy'' Boolean functions: given the truth table of an $n$-variate Boolean function $f$ computable by some \emph{unknown small circuit} from a \emph{known class} of circuits, find in deterministic time $\poly(2^n)$ a circuit $C$ (no restriction on the type of $C$) computing $f$ so ... more >>>

TR13-150 | 4th November 2013
Ruiwen Chen, Valentine Kabanets, Nitin Saurabh

An Improved Deterministic #SAT Algorithm for Small De Morgan Formulas

We give a deterministic #SAT algorithm for de Morgan formulas of size up to $n^{2.63}$, which runs in time $2^{n-n^{\Omega(1)}}$. This improves upon the deterministic #SAT algorithm of \cite{CKKSZ13}, which has similar running time but works only for formulas of size less than $n^{2.5}$.

Our new algorithm is based on ... more >>>

TR15-114 | 18th July 2015
Avishay Tal

#SAT Algorithms from Shrinkage

We present a deterministic algorithm that counts the number of satisfying assignments for any de Morgan formula $F$ of size at most $n^{3-16\epsilon}$ in time $2^{n-n^{\epsilon}}\cdot \mathrm{poly}(n)$, for any small constant $\epsilon>0$. We do this by derandomizing the randomized algorithm mentioned by Komargodski et al. (FOCS, 2013) and Chen et ... more >>>

TR16-037 | 15th March 2016
Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, Ronen Shaltiel

Pseudorandomness when the odds are against you

Impagliazzo and Wigderson showed that if $\text{E}=\text{DTIME}(2^{O(n)})$ requires size $2^{\Omega(n)}$ circuits, then
every time $T$ constant-error randomized algorithm can be simulated deterministically in time $\poly(T)$. However, such polynomial slowdown is a deal breaker when $T=2^{\alpha \cdot n}$, for a constant $\alpha>0$, as is the case for some randomized algorithms for ... more >>>

TR17-109 | 22nd June 2017
Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani

Does Looking Inside a Circuit Help?

The Black-Box Hypothesis, introduced by Barak et al. (JACM, 2012), states that any property of boolean functions decided efficiently (e.g., in BPP) with inputs represented by circuits can also be decided efficiently in the black-box setting, where an algorithm is given an oracle access to the input function and an ... more >>>

TR20-011 | 9th February 2020
Dominik Scheder, Navid Talebanfard

Super Strong ETH is true for strong PPSZ

We construct $k$-CNFs with $m$ variables on which the strong version of PPSZ $k$-SAT algorithm, which uses bounded width resolution, has success probability at most $2^{-(1 - (1 + \epsilon)2/k)m}$ for every $\epsilon > 0$. Previously such a bound was known only for the weak PPSZ algorithm which exhaustively searches ... more >>>

TR20-018 | 18th February 2020
Valentine Kabanets, Sajin Koroth, Zhenjian Lu, Dimitrios Myrisiotis, Igor Oliveira

Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates

The class $FORMULA[s] \circ \mathcal{G}$ consists of Boolean functions computable by size-$s$ de Morgan formulas whose leaves are any Boolean functions from a class $\mathcal{G}$. We give lower bounds and (SAT, Learning, and PRG) algorithms for $FORMULA[n^{1.99}]\circ \mathcal{G}$, for classes $\mathcal{G}$ of functions with low communication complexity. Let $R^{(k)}(\mathcal{G})$ be ... more >>>

ISSN 1433-8092 | Imprint