Next: A Sublinear Bipartitness Tester
Up: Sabbatical at MIT (1996-1998)
Previous: Computational Indistinguishability: A Sample
The work presents constant-round interactive proofs for two
promise problems that capture approximation problems in lattices.
Specifically, this refers to the Shortest Vector and Closest
Vector problems, and the approximation factor is smaller
than the square root of the dimention of the lattice.
Comments:
Authored by O. Goldreich and S. Goldwasser. Appeared in
- Proc. of the 30th STOC,
pp. 1-9, 1998.
- JCSS, Vol. 60, pages 540-563, 2000.
Oded Goldreich
2003-07-30