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

Approximate counting of inversions in a data stream

Miklós Ajtai, T.S. Jayram, et al.

STOC 2002

Paper

Testing random variables for independence and identity

Tuğkan Batu, Eldar Fischer, et al.

Annual Symposium on Foundations of Computer Science - Proceedings

Review

A generalization of resource-bounded measure, with application to the BPP VS. EXP problem

Harry Buhrman, Dieter Van Melkebeer, et al.

SIAM Journal on Computing

Conference paper

An improved data stream algorithm for frequency moments

Don Coppersmith, Ravi Kumar

SODA 2004

View all publications

Abstract

Related

Approximate counting of inversions in a data stream

Testing random variables for independence and identity

A generalization of resource-bounded measure, with application to the BPP VS. EXP problem

An improved data stream algorithm for frequency moments