On polynomial-factor approximations to the shortest lattice vector length

Ravi Kumar; D. Sivakumar

doi:10.1137/S0895480100379981

SIAM Journal on Discrete Mathematics

Paper

01 Apr 2003

On polynomial-factor approximations to the shortest lattice vector length

View publication

Abstract

For every constant ε > 0, we obtain a 2O(n(1/2+1/ε)) time randomized algorithm to approximate the length of the shortest vector in an n-dimensional lattice to within a factor of n3+ε.

Conference paper

On polynomial approximation to the shortest lattice vector length

Ravi Kumar, D. Sivakumar

ACM-SIAM 2001

Paper

An information statistics approach to data stream and communication complexity

Ziv Bar-Yossef, T.S. Jayram, et al.

Journal of Computer and System Sciences

Conference paper

Approximate counting of inversions in a data stream

Miklós Ajtai, T.S. Jayram, et al.

STOC 2002

Paper

Comparing top k lists

Ronald Fagin, Ravi Kumar, et al.

SIAM Journal on Discrete Mathematics

View all publications

Abstract

Related

On polynomial approximation to the shortest lattice vector length

An information statistics approach to data stream and communication complexity

Approximate counting of inversions in a data stream

Comparing top k lists