Daniel Rolf

The PPSZ algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formulas can be found in expected running time at most $\Oc(1.3071^n).$ Using the technique of limited independence, we can derandomize this algorithm yielding $\Oc(1.3071^n)$ ... more >>>

Daniel Rolf

The PPSZ Algorithm presented by Paturi, Pudlak, Saks, and Zane in 1998 has the nice feature that the only satisfying solution of a uniquely satisfiable $3$-SAT formula can be found in expected running time at most $O(1.3071^n)$. Its bound degenerates when the number of solutions increases. In 1999, SchÃ¶ning proved ... more >>>

Subhas Kumar Ghosh

In this work we show that Unique k-SAT is as Hard as k-SAT for every $k \in {\mathds N}$. This settles a conjecture by Calabro, Impagliazzo, Kabanets and Paturi \cite{CIKP03}. To provide an affirmative answer to this conjecture, we develop a randomness optimal construction of Isolation Lemma(see Valiant and Vazirani ... more >>>

Masaki Yamamoto

In [FOCS1998],

Paturi, Pudl\'ak, Saks, and Zane proposed a simple randomized algorithm

for finding a satisfying assignment of a $k$-CNF formula.

The main lemma of the paper is as follows:

Given a satisfiable $k$-CNF formula that

has a $d$-isolated satisfying assignment $z$,

the randomized algorithm finds $z$

with probability at ...
more >>>

Shyan Akmal, Lijie Chen, Ce Jin, Malvika Raj, Ryan Williams

In a Merlin-Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability $1$, and rejects invalid proofs with probability arbitrarily close to $1$. The running time of such a system is defined to be the length of Merlin's proof plus the running time of Arthur. We ... more >>>