(Gap/S)ETH hardness of SVP

DOI10.1145/3188745.3188840zbMath1427.68101arXiv1712.00942OpenAlexW3100371077MaRDI QIDQ5230292

Noah Stephens-Davidowitz, Divesh Aggarwal

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1712.00942

zbMATH Keywords

latticesSVPfine-grained complexityquantitative hardness

Mathematics Subject Classification ID

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

Related Items (8)

Approximate CVP in time \(2^{0.802 n}\) -- now in any norm! ⋮ A note on the concrete hardness of the shortest independent vector in lattices ⋮ Approximate CVP_p in Time 2^{0.802 n} ⋮ The projection games conjecture and the hardness of approximation of Super-SAT and related problems ⋮ Approximate CVP\(_p\) in time \(2^{0.802n}\) ⋮ Fine-Grained Complexity Theory (Tutorial) ⋮ Hardness of bounded distance decoding on lattices in lp norms ⋮ Quantum Hardness of Learning Shallow Classical Circuits

This page was built for publication: (Gap/S)ETH hardness of SVP