Next: Improved Derandomization of BPP
Up: Back at Weizmann (1998-2003)
Previous: Approximating shortest lattice vectors
This work focuses on functions from the n-wise
Cartesian product of any ordered set to the reals,
and presents a testing algorithm with complexity
that is linear in n and polylogarithmic in
the size of the basic set.
Comments:
Authored by Y. Dodis, O. Goldreich, E. Lehman, S. Raskhodnikova,
D. Ron and A. Samorodnitsky. Appeared in
- Random99, Springer LNCS, Vol. 1671, pages 97-108.
Oded Goldreich
2003-07-30