Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR06-062 | 29th June 2006 00:00

Unique k-SAT is as Hard as k-SAT

RSS-Feed




Revision #1
Authors: Subhas Kumar Ghosh
Accepted on: 29th June 2006 00:00
Downloads: 1193
Keywords: 


Abstract:

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


Paper:

TR06-062 | 24th April 2006 00:00

Unique k-SAT is as Hard as k-SAT





TR06-062
Authors: Subhas Kumar Ghosh
Publication: 7th May 2006 21:01
Downloads: 1220
Keywords: 


Abstract:

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.


Comment(s):

Comment #1 to TR06-062 | 29th July 2006 13:42

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





Comment #1
Authors: Chris Calabro
Accepted on: 29th July 2006 13:42
Downloads: 928
Keywords: 


Abstract:

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.


Comment #2 to TR06-062 | 29th July 2006 13:42

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





Comment #2
Authors: Yann Barsamian
Accepted on: 29th July 2006 13:42
Downloads: 828
Keywords: 


Abstract:

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


Comment #3 to TR06-062 | 29th July 2006 13:44

Comment on first submission





Comment #3
Authors: Subhas Kumar Ghosh
Accepted on: 29th July 2006 13:44
Downloads: 785
Keywords: 


Abstract:

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




ISSN 1433-8092 | Imprint