Open Problems

Mathematics of Lattices

(Added 9/9) Find an explicitly constructible family of lattices $L = {L_n}_{n \in \naturals}$ for which there is a constant $c > 0$ such that for every large enough $n$, $\lambda_1(L_n) >= c \sqrt{n} det(L)^{1/n}$.

By explicitly constructibe, I mean that there should be an algorithm that, on input $n$, runs in time $poly(n)$ and outputs a basis of $L_n$.

(Added 9/23) Show a rank-preserving, deterministic, Karp reduction from SVP_{\gamma} to CVP_{\gamma} for any \gamma. (What's known: there is a rank-preserving deterministic, Cook reduction shown in class -- that is, the SVP algorithm makes many queries to the CVP oracle. there is also a rank-preserving, randomized, Karp reduction which we did not see in class)
(Added 9/23) Show a reduction from (search) SVP_{\gamma'} to gapSVP_{\gamma} for \gamma', \gamma > 1, and similarly for CVP. (What's known: we stated -- but did not prove -- in class that there is such a reduction with \gamma' = \gamma = 1. Also, since gapSVP_{\gamma} is NP-hard* for \gamma = 2^{(\log n)^{1-\epsilon}} for arbitrary constants \epsilon, we know such a reduction* for these values of \gamma. So, really, the question is for factors \gamma = poly(n)).

Here, * refers to the fact that these NP-hardness reductions run in super-polynomial time.
(Added 9/15) Show that CVP in the $\ell_2$ norm is ETH-hard. That is, there is are universal constants $c, c'$ such that if there is a $2^{cn}$-time algorithm for CVP in the $\ell_2$ norm for $n$-dimensional lattices, then there is a $2^{c'n}$-time algorithm for SAT on n variables.

Your goal is to make $c$ as large as possible and $c'$ as small as possible (This will give you a stronger theorem). Bonus points if you can make $c$ and $c'$ approximately equal.
(Added 9/15) (Harder) Show that SVP in the $\ell_2$ norm is ETH-hard.