### DIMACS Theory of Computing Seminar

Title: On the Quantitative Hardness of CVP

Speaker: **Noah Stephens-Davidowitz**, Princeton University

Date: Wednesday, September 27, 2017 11:00am-12:00pm

Location: CoRE Bldg, Room 301, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

For odd integers p >= 1 (and p = \infty), we show that the
Closest Vector Problem in the \ell_p norm (CVP_p) over rank n
lattices cannot be solved in 2^{(1-\eps) n} time for any constant
\eps > 0 unless the Strong Exponential Time Hypothesis (SETH)
fails. We then extend this result to ``almost all'' values
of p \geq 1, not including the even integers. This comes
tantalizingly close to settling the quantitative time complexity of
the important special case of CVP_2 (i.e., CVP in the Euclidean
norm), for which a 2^{n +o(n)}-time algorithm is
known.

We also show a similar
SETH-hardness result for SVP_\infty; hardness of approximating CVP_p
to within some constant factor under the so-called Gap-ETH
assumption; and other hardness results for CVP_p and CVPP_p for any
1 <= p < \infty under different
assumptions.

See: https://sites.google.com/view/dimacs-theory-seminar/home