Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR98-005 | 27th January 1998 00:00

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

RSS-Feed




TR98-005
Authors: Jin-Yi Cai
Publication: 28th January 1998 09:29
Downloads: 3762
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