Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with SVP:
TR99-016 | 25th April 1999
Irit Dinur

Approximating SVP_\infty to within Almost-Polynomial Factors is NP-hard

This paper shows SVP_\infty and CVP_\infty to be NP-hard to approximate
to within any factor up to $n^{1/\log\log n}$. This improves on the
best previous result \cite{ABSS} that showed quasi-NP-hardness for
smaller factors, namely $2^{\log^{1-\epsilon}n}$ for any constant
$\epsilon>0$. We show a direct reduction from SAT to these
problems, that ... more >>>

TR21-179 | 8th December 2021
tatsuie tsukiji

Smoothed Complexity of Learning Disjunctive Normal Forms, Inverting Fourier Transforms, and Verifying Small Circuits

Comments: 1

This paper aims to derandomize the following problems in the smoothed analysis of Spielman and Teng. Learn Disjunctive Normal Form (DNF), invert Fourier Transforms (FT), and verify small circuits' unsatisfiability. Learning algorithms must predict a future observation from the only $m$ i.i.d. samples of a fixed but unknown joint-distribution $P(G(x),y)$ ... more >>>

ISSN 1433-8092 | Imprint