User daniele micciancio - MathOverflow

Answer by Daniele Micciancio for Minkowski's successive minima: A quantity not much larger than det(L)^(1/n) and not much smaller than λ_n(L)?

2013-05-21T04:34:09Z

As already pointed out by Jean and Alexander, bound (2) does not hold in the opposite direction. For bound (1), the opposite inequality holds with $c_2=n$.

Theorem For any $n$-dimensional lattice $\Lambda$, $f_n(\Lambda)\geq \lambda_n(\Lambda)/n$.

Proof: Let ${\bf v}_1,\ldots,{\bf v}_n$ be a set of linearly independent vectors in a lattice minimizing $\max_i \|{\bf v}_i^*\|$. You can always turn ${\bf v}_1,\ldots,{\bf v}_n$ into a basis without increasing $\|{\bf v}_i^*\|$. So, assume it is a basis. Let ${\bf w}_1,\ldots,{\bf w}_n$ be a basis of the dual lattice $\Lambda^*$ such that ${\bf v_i}\cdot {\bf w_j}=\delta_{i,j}$.

Orthogonalizing ${\bf w}_1,\ldots,{\bf w}_n$ in reverse order gives $\|{\bf w}_i^*\| = \|{\bf v}_i^*\|^{-1}$. So, $\max_i \|{\bf v}_i^*\| = (\min_i \|{\bf w}_i^*\|)^{-1}$. Using the bound $\min_i \|{\bf w}_i^*\| \leq \lambda_1(\Lambda^*)$ and Banaszczyk's transference theorem $\lambda_n(\Lambda)\lambda_1(\Lambda^*)\leq n$ gives: $\max_i \|{\bf v}_i^*\| = (\min_i \|{\bf w}_i^*\|)^{-1} \geq \lambda_1(\Lambda^*)^{-1}\geq \lambda_n(\Lambda)/n$. So, $f_n(\Lambda)\geq \lambda_n(\Lambda)/n$. $\Box$

Answer by Daniele Micciancio for Polar body of a convex body that avoids a lattice

2011-06-15T04:36:39Z

If I understand the question correctly, I think the best known bound is still that of Wojciech Banaszczyk: "Inequalities for Convex Bodies and Polar Reciprocal Lattices in $R^n$ II: Application of $K$-Convexity". Discrete & Computational Geometry 16(3): 305-311 (1996) http://dx.doi.org/10.1007/BF02711514

The bound is $1/\epsilon_d = O(d\cdot \log(d))$. Not yet the optimal answer you were seeking, but within a log factor from optimal.

Answer by Daniele Micciancio for diameter of Voronoi cell of the lattice ? What about R^n ? What about small n =2,3,4 ?What about random lattice ?

2011-06-08T05:09:42Z

Computing the covering radius of a lattice (wrt $\ell_2$ norm) is not known to be NP-hard. (Will, if you got that piece of information from SLG, I guess SLG is wrong.)

Computing the covering radius of linear codes (wrt Hamming metric) and of lattices (wrt $\ell_p$ norm but only for large $p>2$) is NP-hard. In fact these problems are even $\Pi_2$ hard to approximate for small constant approximation factors. See papers

http://dx.doi.org/10.1007/s00037-005-0193-y (The complexity of the covering radius problem, Guruswami, Micciancio and Regev, Computational Complexity 14(2):90-121)
http://dx.doi.org/10.1109/CCC.2006.23 (Hardness of the covering radius problem on lattices, Haviv and Regev, in CCC 2006)

Approximating the covering radius of lattices in $\ell_2$ norm is also conjectured (in reference 1) to be $\Pi_2$ hard to approximate within some small constant factor (and NP-hard for any constant factor), but as far as I know this is an open problem.

For any fixed dimension n, the covering radius problem can be solved in polynomial time. So, for small $n$ (certainly for $n=2,3,4$, and probably for up to $n\leq 20$ or so), the problem can be solved efficiently. There are several ways to do that, but they are all based on enumerating all the vertices of the Voronoi cell, which takes at least $n^{O(n)}$ time. See http://dx.doi.org/10.1145/1806689.1806739 and references therein. Computing the covering radius in single exponential time $2^{O(n)}$ is an open problem.

For larger dimension it may be more effective to approximate the covering radius within a factor 2 as suggested in reference 1 above, by picking a random point in space and computing its distance to the lattice. This can be done in $2^{O(n)}$ time.

Answer by Daniele Micciancio for How many LLL reduced bases are there?

2011-06-07T16:58:42Z

Here is the answer.

Claim: Any given n-dimensional lattice has at most $2^{0(n^3)}$ LLL reduced bases.

Notice: the bound is a function of the dimension $n$ only, and does not depend on the determinant of the lattice. Here is a simple proof:

Proof: Fix a lattice $L(B)$ and let $\lambda$ be the minimum distance of the lattice. The first vector of an LLL reduced basis $B=[\vec b_1,\ldots,\vec b_n]$ has length at most $2^{O(n)}\lambda$. Since spheres of radius $\lambda/2$ centered around lattice points are disjoit, by a simple volume argument, the number of lattice points in a sphere of radius $r=2^{O(n)}\lambda$ is at most $(1+2r/\lambda)^n = 2^{O(n^2)}$. For any such first vector $\vec b_1$, let $\pi_1$ be the projection orthogonal to $\vec b_1$. By definition of LLL reduced basis, $\pi_1(B)$ is also LLL reduced. Using LLL size reduction conditions, each projected LLL reduced basis $\pi_1(B)$ thas a unique lift such that all its Gram-Schmidt coefficients are in the range $[-1/2,1/2)$. So, we can proceed by induction, and see that there are at most $2^{O((n-1)^2)}$ possible choices for $\vec b_2$, and so on. Overall, the number LLL reduced bases for $L$ is at most $\prod_{k=1}^n 2^{O(k^2)} = 2^{O(n^3)}$. This concludes the proof of the upper bound. [Q.E.D.]

Of course, the number of LLL bases for a given lattice can be much smaller, e.g., you can easily build lattices whose LLL basis is unique up to the sign of the basis vectors. (E.g., take an orthogonal lattice with longer and longer basis vectors.) So, the number of LLL reduced basis can be as low as $2^n$. Every lattice has at least these many LLL reduced basis because you can set the signs of the basis vectors arbitrarily. However, my guess is that the upper bound is asymptotically optimal in the worst case, i.e., there are lattices with $2^{\Omega(n^3)}$ LLL reduced bases. It should be possible to construct such lattices starting from examples lattices that achieve LLL worst case approximation factor $2^{O(n)}$ on the length of the shortest vector, but I didn't check the details.