in case you are going to Oded's talk and are not on the CS mailing
lists, note that the room has changed.
---------- Forwarded message ----------
From: Debbie Lehto <dlehto(a)csail.mit.edu>
Date: Thu, Apr 23, 2015 at 1:42 PM
Subject: [Theory-seminars] Room Change for Today's TOC Seminar - Now
Taken Place in Star D463 Oded Regev: Faster algorithms for the
Shortest Vector Problem
To: theory-seminars(a)csail.mit.edu, seminars(a)csail.mit.edu
Please note the new location for today's seminar will be Star Conf Room D463
Oded Regev: Faster Algorithms for the Shortest Vector Problem
Speaker: Oded Regev, Courant Institute of Mathematical Sciences
Host: Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod Vaikuntanathan
Date: Thursday, April 23, 2015
Time: 4:15 PM to 5:15 PM
Refreshments Time: 4:00 PM
Location: G449 (Patil/Kiva)
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.
Relevant URL:
For more information please contact: Deborah Lehto, 617.324.7303, <a
href="mailto:dlehto@csail.mit.edu">dlehto@csail.mit.edu</a>
_______________________________________________
Theory-seminars mailing list
Theory-seminars(a)lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/theory-seminars
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip