The Ajtai random class of lattices

✍ Scribed by Thomas W. Cusick

• Book ID: 104326737
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 88 KB
• Volume: 226
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(99)00063-8

✦ Synopsis

Ajtai has recently given a reduction from the problem of approximating a short basis for a lattice in the worst case, to the problem of ÿnding a short lattice vector for a uniformly chosen lattice in a certain random class of lattices. Here we give an explicit formula for the number of lattices of the type used by Ajtai. We also prove some results about the average volume of the fundamental cell of such a lattice.