Seminars & Colloquia Calendar

Download as iCal file

DIMACS Theory of Computing Seminar

On the Quantitative Hardness of CVP Title On the Quantitative Hardness of CVP

Noah Stephens-Davidowitz, Princeton University

Location:  CoRE 301
Date & time: Wednesday, 27 September 2017 at 11:00AM - 12:00PM

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.

 

Special Note to All Travelers

Directions: map and driving directions. If you need information on public transportation, you may want to check the New Jersey Transit page.

Unfortunately, cancellations do occur from time to time. Feel free to call our department: 848-445-6969 before embarking on your journey. Thank you.