Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR98-005 | 27th January 1998 00:00

#### A new transference theorem and applications to Ajtai's connection factor

TR98-005
Authors: Jin-Yi Cai
Publication: 28th January 1998 09:29
Keywords:

Abstract:

We prove a new transference theorem in the geometry of numbers,
giving optimal bounds relating the successive minima of a lattice
with the minimal length of generating vectors of its dual.
It generalizes the transference theorem due to Banaszczyk.
We also prove a stronger bound for the special class of lattices
possessing $n^{\epsilon}$-unique shortest lattice vectors.
The theorems imply consequent improvement of the Ajtai connection
factors in the connection of average-case to worst-case
complexity of the shortest lattice vector problem.
Our proofs are non-constructive, based on methods from harmonic
analysis.

ISSN 1433-8092 | Imprint