On the Quantitative Hardness of CVP

Speaker: Noah Stephens-Davidowitz , NYU

Date: Friday, May 26, 2017

Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: 32-G882

Event Type:

Room Description:

Host: Vinod Vaikuntanathan, MIT

Contact: Joanne Talbot Hanley, 61-253-6054, joanne@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
None

Reminders to: cis-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: TALK: CIS Seminar: Noah Stephens-Davidowitz, "On the Quantitative Hardness of CVP"-- FRIDAY, May 26!

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>=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. In particular, our result applies for any p=p(n) =/= 2 that approaches 2 as n goes to infinity.

Based on joint work with Huck Bennett and Sasha Golovnev.

Research Areas:

Impact Areas:

See other events that are part of the Cryptography and Information Seminar (CIS) 2017.

Created by Joanne Talbot Hanley at Thursday, May 25, 2017 at 1:14 PM.