A {\em supermodel} is a satisfying assignment of a boolean formula for which any small alteration, such as a single bit flip, can be repaired by another small alteration, yielding a nearby satisfying assignment. We study computational problems associated with super models and some generalizations thereof. For general formulas, it ... more >>>

We show new tradeoffs for satisfiability and nondeterministic linear time. Satisfiability cannot be solved on general purpose random-access Turing machines in time $n^{1.618}$ and space $n^{o(1)}$. This improves recent results of Lipton and Viglas and Fortnow. more >>>

A dichotomy theorem for a class of decision problems is a result asserting that certain problems in the class are solvable in polynomial time, while the rest are NP-complete. The first remarkable such dichotomy theorem was proved by T.J. Schaefer in 1978. It concerns the class of generalized satisfiability problems ... more >>>

We study the space complexity of refuting unsatisfiable random $k$-CNFs in the Resolution proof system. We prove that for any large enough $\Delta$, with high probability a random $k$-CNF over $n$ variables and $\Delta n$ clauses requires resolution clause space of $\Omega(n \cdot \Delta^{-\frac{1+\epsilon}{k-2-\epsilon}})$, for any $0<\epsilon<1/2$. For constant $\Delta$, ... more >>>

We prove that, with high probability, the space complexity of refuting a random unsatisfiable boolean formula in $k$-CNF on $n$ variables and $m = \Delta n$ clauses is $O(n \cdot \Delta^{-\frac{1}{k-2}})$. more >>>

We describe a deterministic algorithm that, for constant k, given a k-DNF or k-CNF formula f and a parameter e, runs in time linear in the size of f and polynomial in 1/e and returns an estimate of the fraction of satisfying assignments for f up to an additive error ... more >>>

Bayesian inference and counting satisfying assignments are important problems with numerous applications in probabilistic reasoning. In this paper, we show that plain old DPLL equipped with memoization can solve both of these problems with time complexity that is at least as good as all known algorithms. Furthermore, DPLL with memoization ... more >>>

$k$-SAT is one of the best known among a wide class of random constraint satisfaction problems believed to exhibit a threshold phenomenon where the control parameter is the ratio, number of constraints to number of variables. There has been a large amount of work towards estimating the 3-SAT threshold. We ... more >>>

The satisfiability problem of Boolean Formulae in 3-CNF (3-SAT) is a well known NP-complete problem and the development of faster (moderately exponential time) algorithms has received much interest in recent years. We show that the 3-SAT problem can be solved by a probabilistic algorithm in expected time O(1,3290^n). Our approach ... more >>>

We study approximation hardness and satisfiability of bounded occurrence uniform instances of SAT. Among other things, we prove the inapproximability for SAT instances in which every clause has exactly 3 literals and each variable occurs exactly 4 times, and display an explicit approximation lower bound for this problem. We also ... more >>>

Abstract. It is known that random k-SAT formulas with at least (2^k*ln2)*n random clauses are unsatisfiable with high probability. This result is simply obtained by bounding the expected number of satisfy- ing assignments of a random k-SAT instance by an expression tending to 0 when n, the number of variables ... more >>>

We prove results on the computational complexity of instances of 3SAT in which every variable occurs 3 or 4 times. more >>>

Boolean satisfiability problems are an important benchmark for questions about complexity, algorithms, heuristics and threshold phenomena. Recent work on heuristics, and the satisfiability threshold has centered around the structure and connectivity of the solution space. Motivated by this work, we study structural and connectivity-related properties of the space of solutions ... more >>>

We prove the first time-space tradeoffs for counting the number of solutions to an NP problem modulo small integers, and also improve upon the known time-space tradeoffs for Sat. Let m be a positive integer, and define MODm-Sat to be the problem of determining if a given Boolean formula has ... more >>>

Ever since the fundamental work of Cook from 1971, satisfiability has been recognized as a central problem in computational complexity. It is widely believed to be intractable, and yet till recently even a linear-time, logarithmic-space algorithm for satisfiability was not ruled out. In 1997 Fortnow, building on earlier work by ... more >>>

We show that tree-like OBDD proofs of unsatisfiability require an exponential increase ($s \mapsto 2^{s^{\Omega(1)}}$) in proof size to simulate unrestricted resolution, and that unrestricted OBDD proofs of unsatisfiability require an almost-exponential increase ($s \mapsto 2^{ 2^{\left( \log s \right)^{\Omega(1)}}}$) in proof size to simulate $\Res{O(\log n)}$. The ``OBDD proof ... more >>>

Consider the following two-player communication process to decide a language $L$: The first player holds the entire input $x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $x$; their goal is to cooperatively decide whether $x$ belongs to $L$ at small ... more >>>