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

Combinatorial feature selection problems

Moses Charikar, Venkatesan Guruswami, et al.

Annual Symposium on Foundations of Computer Science - Proceedings

Conference paper

Sampling short lattice vectors and the closest lattice vector problem

Miklós Ajtai, Ravi Kumar, et al.

CCC 2002

Paper

Comparing top k lists

Ronald Fagin, Ravi Kumar, et al.

SIAM Journal on Discrete Mathematics

Conference paper

The predictive power of online chatter

Daniel Gruhl, R. Guha, et al.

KDD 2005

View all publications

Abstract

Related

Combinatorial feature selection problems

Sampling short lattice vectors and the closest lattice vector problem

Comparing top k lists

The predictive power of online chatter