Dear quanta,
Below is an announcement for a talk on classical algorithms but for a
problem where people have been looking for quantum algorithms and using
some techniques that resemble some quantum techniques for lattice problems.
aram
----
*Speaker:* Oded Regev, Courant Institute of Mathematical Sciences
*Date:* Thursday, April 23, 2015
*Time:* 4:15 PM to 5:15 PM
*Refreshments:* 4:00 PM
*Location:* G449 (Patil/Kiva)
*Host:* Costis Daskalakis, Ankur Moitra, Dana Moshkovitz and Vinod
Vaikuntanathan
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.
See other events that are part of the Theory of Computation (TOC)
Seminar Series 2015. <https://calendar.csail.mit.edu/seminar_series/7977>
_______________________________________________
qip mailing list
qip(a)mit.edu
http://mailman.mit.edu/mailman/listinfo/qip