Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SUM CHECK PROTOCOL:
Reports tagged with Sum Check Protocol:
TR11-119 | 4th September 2011
Subhash Khot, Preyas Popat, Nisheeth Vishnoi

$2^{\log^{1-\epsilon} n}$ Hardness for Closest Vector Problem with Preprocessing

We prove that for an arbitrarily small constant $\eps>0,$ assuming NP$\not \subseteq$DTIME$(2^{{\log^{O(1/\epsilon)} n}})$, the preprocessing versions of the closest vector problem and the nearest codeword problem are hard to approximate within a factor better than $2^{\log ^{1-\epsilon}n}.$ This improves upon the previous hardness factor of $(\log n)^\delta$ for some $\delta ... more >>>


TR25-182 | 16th November 2025
Oded Goldreich

Proving the PCP Theorem with 1.5 proof compositions (or yet another PCP construction)

Revisions: 1

The original proof of the PCP Theorem composes a Reed-Muller-based PCP with itself, and then composes the resulting PCP with a Hadamard-based PCP [Arora, Lund, Motwani, Sudan and Szegedy ({\em JACM}, 1998)].
Hence, that proof applies a (general) proof composition result twice.
(Dinur's alternative proof consists of logarithmically many gap ... more >>>




ISSN 1433-8092 | Imprint