scientific article; zbMATH DE number 1507221

MaRDI QIDQ4503941zbMATH OpenFDO

Authors Irit Dinur

Publication date 15 December 2002

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
• A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.
• scientific article; zbMATH DE number 1335879
• Approximating the SVP to within a factor \((1+1/\dim^\varepsilon)\) is NP-hard under randomized reductions
• Inapproximability of the shortest vector problem: toward a deterministic reduction

Cited in

(7)

• Approximating \(SVP_{\infty}\) to within almost-polynomial factors is NP-hard
• Approximating CVP to within almost-polynomial factors is NP-hard
• The projection games conjecture and the hardness of approximation of Super-SAT and related problems
• Computing the norm ∥A∥∞,1 is NP-hard^∗
• An improved lower bound for approximating the minimum integral solution problem with preprocessing over \(\ell_\infty\) norm
• A Digital Signature Scheme Based on CVP  ∞
• Diagonally dominant matrices for cryptography

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4503941)