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

Paper

Combinatorial feature selection problems

Moses Charikar, Venkatesan Guruswami, et al.

Annual Symposium on Foundations of Computer Science - Proceedings

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

Combinatorial feature selection problems

Information theory methods in communication complexity

On polynomial approximation to the shortest lattice vector length