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

On the hardness of approximating multicut and sparsest-cut

Shuchi Chawla, Robert Krauthgamer, et al.

CCC 2005

Conference paper

The complexity of approximating entropy

Tukan Batu, Sanjoy Dasgupta, 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

Cell-probe lower bounds for the partial match problem

On the hardness of approximating multicut and sparsest-cut

The complexity of approximating entropy

Comparing top k lists