ECCC-Report TR98-005https://eccc.weizmann.ac.il/report/1998/005Comments and Revisions published for TR98-005en-usWed, 28 Jan 1998 09:29:58 +0200
Paper TR98-005
| A new transference theorem and applications to Ajtai's connection factor |
Jin-Yi Cai
https://eccc.weizmann.ac.il/report/1998/005We 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.
Wed, 28 Jan 1998 09:29:58 +0200https://eccc.weizmann.ac.il/report/1998/005