Speaker: Ricky Rosen Tel Aviv University
Time: 2008-04-16 16:30-2008-04-16 17:30
Venue: FIT Building 4-603, Tsinghua University
Download: Click!

Abstract:

We present reductions from lattice problems in the l_2 norm to the corresponding problems in other norms such as l_1, l_\infty (and in fact in any other l_p norm where 1\leq p \leq \infty). We consider lattice problems such as the Shortest Vector Problem (SVP), Shortest Independent Vector Problem (SIVP), Closest Vector Problem (CVP) and the Closest Vector Problem with Preprocessing (CVPP).The reductions are based on embeddings of normed spaces. Among other things, our reductions imply that the Shortest Vector Problem in the l_1 norm and the Closest Vector Problem with Preprocessing in the l_\infty norm are hard to approximate to within any constant (and beyond). Previously, the former problem was known to be hard to approximate to within 2-\eps, while no hardness result was known for the latter problem.
 

Short Bio:

Ricky Rosen is a PhD student under the supervision of Prof. Oded Regev (Tel Aviv Univesity) and Prof. Ran Raz(The Weizmann Institute of Science). Her fields of interest is theoretical computer science, complexity pure and quantum and approximation algorithms.