Jin-Yi Cai (UW-Madison): On the Minimum Volume of a Perturbed Unit Cube.

This is a problem that came up in the study of the worst-case/average-case complexity for lattice problems. Suppose we have a unit cube. Perturb each of the n generating vectors by some vectors of length at most epsilon. What is the minimum volume of the perturbed unit cube? And what perturbations achieve this minimum?

In the work on lattice problems Cai and Nerurkar obtained an upper bound, which was sufficient for their purpose, but the exact nature of this minimization function remained unresolved. Recently Micciancio gave exact bounds for a large set of values of epsilon, and the minimizer was shown to be unique (and is the "obvious" culprit. (Now what is it?)) A small interval of epsilon remained where this proof does not apply.

It turned out the bahaviour of the minimization function becomes rather complicated within this small gap, and I believe I have the complete picture.

In this talk I will give a sketch of the proofs.