next up previous
Next: Learning polynomials with queries: Up: The First 1.5 Years Previous: Private Information Retrieval

Free Bits, PCPs and Non-Approximability - Towards Tight Results

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).


\fbox{\begin{minipage}{40em}
{\bf Abstract ({abbr.}):} {This paper continues th...
...ul transformations between proof checking
complexity classes.}
\end{minipage}}


Comments: Authored by M. Bellare, O. Goldreich and M. Sudan. Appeared in



Oded Goldreich
2003-07-30