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

Self-similarity in the web

Stephen Dill, Ravi Kumar, et al.

VLDB 2001

Paper

The complexity of approximating the entropy

Tuǧkan Batu, Sanjoy Dasgupta, et al.

SIAM Journal on Computing

Conference paper

A graph-theoretic approach to extract storylines from search results

Ravi Kumar, Uma Mahadevan, et al.

KDD 2004

Conference paper

Comparing top k lists

Ronald Fagin, Ravi Kumar, et al.

SODA 1998

View all publications

Abstract

Related

Self-similarity in the web

The complexity of approximating the entropy

A graph-theoretic approach to extract storylines from search results

Comparing top k lists