Next: The First 1.5 Years
Up: The Technion Period (1986-94)
Previous: Tiny Families of Functions
The main result is that any set having an interactive proof of
logarithmic statistical-knowledge complexity, can be recognized
in probabilistic polynomial-time with the help of an NP-orcale.
Comments:
Authored by O. Goldreich, R. Ostrovsky and E. Petrank. Appeared in
- Proc. of the 26th STOC,
pp. 534-543, 1994.
- SIAM Jour. on Comp.,
Volume 27, Number 4, pp. 1116-1141, August 1998.
Oded Goldreich
2003-07-30