Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SUBHAS KUMAR GHOSH:
All reports by Author Subhas Kumar Ghosh:

TR06-062 | 24th April 2006
Subhas Kumar Ghosh

Unique k-SAT is as Hard as k-SAT

Revisions: 1 , Comments: 3

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 >>>




ISSN 1433-8092 | Imprint