Conference paper
Approximate counting of inversions in a data stream
Miklós Ajtai, T.S. Jayram, et al.
STOC 2002
Paper
On polynomial-factor approximations to the shortest lattice vector length
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+ε.
Related
Conference paper
A note on the set systems used for broadcast encryption
Ravi Kumar, Alexander Russell
SODA 1998
T.S. Jayram, Subhash Khot, et al.
Journal of Computer and System Sciences
Shuchi Chawla, Robert Krauthgamer, et al.
Computational Complexity