Next: Learning polynomials with queries:
Up: The First 1.5 Years
Previous: Private Information Retrieval
This 110-pages work contains numerous results regarding PCP and
their relation to non-approximability results. In retrospect,
the most influential contribution was the introduction of the Long-Code
(and/or the demonstration of its usefulness for the design of PCPs).
Comments:
Authored by M. Bellare, O. Goldreich and M. Sudan. Appeared in
- Proc. of the 36th FOCS, pp. 422-431, 1995.
- SIAM
Jour. on Comp.,
Vol. 27, No. 3, pp. 804-915, June 1998.
Oded Goldreich
2003-07-30