Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR25-153 | 21st October 2025
Isaac M Hair, Amit Sahai

SVP$_p$ is NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\epsilon} n}$

We prove that SVP$_p$ is NP-hard to approximate within a factor of $2^{\log^{1 - \varepsilon} n}$, for all constants $\varepsilon > 0$ and $p > 2$, under standard deterministic Karp reductions. This result is also the first proof that \emph{exact} SVP$_p$ is NP-hard in a finite $\ell_p$ norm. Hardness for ... more >>>


TR25-152 | 20th October 2025
Tal Herman, Guy Rothblum

Proving Natural Distribution Properties is Harder than Testing Them

Suppose that an untrusted analyst claims that it ran a distribution tester and determined that an unknown distribution has a certain property. Can the untrusted analyst prove that its assertion is correct to a verifier that does not have sufficient samples and computational resources to run the tester on its ... more >>>


TR25-151 | 17th October 2025
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Raghuvansh Saxena

Constant Rate Codes for Adaptive Broadcasts Do Not Exist

Can the $n$-party broadcast channel, where any symbol sent by one party is received by all, be made resilient to noise with low overhead? Namely, is it possible to construct interactive error-correcting codes that convert any protocol designed for the noiseless broadcast channel into one that works over the noisy ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint