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+ε.

Paper

Cell-probe lower bounds for the partial match problem

T.S. Jayram, Subhash Khot, et al.

Journal of Computer and System Sciences

Conference paper

Self-similarity in the web

Stephen Dill, Ravi Kumar, et al.

VLDB 2001

Paper

Comparing top k lists

Ronald Fagin, Ravi Kumar, et al.

SIAM Journal on Discrete Mathematics

Conference paper

Sublinear algorithms for testing monotone and unimodal distributions

Tuǧkan Batu, Ravi Kumar, et al.

STOC 2004

View all publications

Abstract

Related

Cell-probe lower bounds for the partial match problem

Self-similarity in the web

Comparing top k lists

Sublinear algorithms for testing monotone and unimodal distributions