Jin-Yi Cai (UW-Madison):
On the Average-Case Hardness of CVP
We prove a connection of the worst-case complexity to the average-case
complexity based on the Closest Vector Problem (CVP) for
lattices. Assuming that there is an efficient algorithm which can solve
approximately a random instance of CVP, with a non-trivial
success probability, for lattices under a certain natural distribution,
we show that one can approximately solve several lattice problems
(including a version of CVP) efficiently within a fixed polynomial factor,
for *every* lattice with high probability.
I will start slowly with an introduction to some of the lattice problems.
This may last several sessions.
This is from a paper to appear in FOCS 2001.