Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HARDNESS-OF-APPROXIMATION:
Reports tagged with hardness-of-approximation:
TR99-015 | 25th April 1999
Irit Dinur, S. Safra

#### On the hardness of approximating label cover

The label-cover problem was introduced in \cite{ABSS} and shown
there to be quasi-NP-hard to approximate to within a factor of
$2^{\log^{1-\delta}n}$ for any {\em constant} $\delta>0$. This
combinatorial graph problem has been utilized \cite{ABSS,GM,ABMP}
for showing hardness-of-approximation of numerous problems. We
present a direct combinatorial reduction from low
error-probability PCP ... more >>>

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

ISSN 1433-8092 | Imprint