In this work we show that Unique k-SAT is as hard as k-SAT for every $k \in {\mathds N}$.

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 \cite{VV85}) for $k$-\sat, using $\Omega\left(\log{s}\right)$ number of random bits, to isolate an element of a family of size ${\cal O}\left(2^s\right)$. It shown by Chari, Rohatgi and Srinivasan in \cite{CRS93}, that $\Omega\left(\log{s}\right)$ number of random bits is the lower-bound of randomness complexity for Isolation Lemma.

Comments on "Unique k-SAT is as Hard as k-SAT" Comment on: TR06-062

The paper "Unique $k$-SAT is as Hard as $k$-SAT",
by Subhas Kumar Ghosh, has many flaws,
both technical and academic, and
some invalidate the proof of the main result.
The following comments describe some of the errors.
It is assumed that the reader is intimately familiar
with the paper.

Some things I could not understand in TR06-062 Comment on: TR06-062

After reading the whole paper, I did not understood
some parts of the proofs used in it.

Comment on first submission

First version of ECCC Report TR06-062 has a serious flaw - which Revision 01 addresses, please use this version