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

A graph-theoretic approach to extract storylines from search results

Ravi Kumar, Uma Mahadevan, et al.

KDD 2004

Conference paper

Reductions in streaming algorithms, with an application to counting triangles in graphs

Ziv Bar-Yossef, Ravi Kumar, et al.

SODA 2002

Paper

The complexity of approximating the entropy

Tuǧkan Batu, Sanjoy Dasgupta, et al.

SIAM Journal on Computing

Paper

On the hardness of approximating multicut and sparsest-cut

Shuchi Chawla, Robert Krauthgamer, et al.

Computational Complexity

View all publications

Abstract

Related

A graph-theoretic approach to extract storylines from search results

Reductions in streaming algorithms, with an application to counting triangles in graphs

The complexity of approximating the entropy

On the hardness of approximating multicut and sparsest-cut