Oded Regev: Faster Algorithms for the Shortest Vector Problem

Speaker: Oded Regev, Courant Institute of Mathematical Sciences

Date: Thursday, April 23, 2015

Time: 4:15 PM to 5:15 PM Note: all times are in the Eastern Time Zone

Refreshments: 4:00 PM

Public: Yes

Location: G449 (Patil/Kiva)

Event Type:

Room Description:

Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan

Contact: Deborah Lehto, 617.324.7303, dlehto@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:

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

Reminder Subject: TALK: d Regev: Faster algorithms for the Shortest Vector Problem

Abstract: We give a randomized ~2^n-time algorithm for solving the Shortest Vector Problem (SVP)
on n-dimensional lattices, improving on the previous best running time of 4^n by Micciancio
and Voulgaris (STOC 2010). Despite being the fastest, the algorithm is arguably also the simplest in this line of work.

The main ingredients used are the discrete Gaussain distribution, an identity due to Riemann, and a
way to transform samples from a distribution p into samples from the “square of p”.
Time permitting, we will also discuss an algorithm running in time 2^n{n/2} that solves
another hard lattice problem.

Joint work with Divesh Aggarwal, Daniel Dadush, and Noah Stephens-Davidowitz.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) Seminar Series 2015.

Created by Deborah Goodwin Email at Tuesday, April 21, 2015 at 9:08 AM.