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

Rank aggregation methods for the web

Cynthia Dwork, Ravi Kumar, et al.

WWW 2001

Conference paper

Efficient Similarity Search and Classification via Rank Aggregation

Ronald Fagin, Ravi Kumar, et al.

SIGMOD 2003

Paper

Information theory methods in communication complexity

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

Proceedings of the Annual IEEE Conference on Computational Complexity

Conference paper

On polynomial approximation to the shortest lattice vector length

Ravi Kumar, D. Sivakumar

ACM-SIAM 2001

View all publications

Abstract

Related

Rank aggregation methods for the web

Efficient Similarity Search and Classification via Rank Aggregation

Information theory methods in communication complexity

On polynomial approximation to the shortest lattice vector length