[Colloquium] Reminder: Show & Tell Series at TTI-C (Prahladh Harsha Today @ 12:15pm)

[Katherine Cumming]

TTI-C SHOW AND TELL SERIES
 
Presented by:  Toyota Technological Institute at Chicago
 
 
Speaker: Prahladh Harsha, TTI-C
Speaker's home page: http://www.tti-c.org//harsha.html
 
Time: Tuesday, November 1st, 2005
Location: TTI-C Conference Room
Lunch Provided @ 12:00pm 
Seminar @ 12:15pm
 
Short PCPs Verifiable in Polylogarithmic Time
 
Abstract:
 
The study of efficient probabilistic methods for verifying proofs was
initiated in the works of Babai et. al. [BFLS] and Feige at. al. [FGLSS]
with very different motivation and emphases. The work of Babai et. al.
considered the direct motivation of verifying proofs highly efficiently. In
contrast, Feige et. al. established a dramatic connection between efficient
probabilistically checkable proofs (PCPs) and the inapproximability of
optimization problems. Most succeeding works have focused on the latter
connection. On the other hand, no later work seems to have returned to the
extreme efficiency of the verifier. This is unfortunate because the latter
efficiency parameters are significant in the context of proof-verification.
 
Motivated by the recent progress in PCP constructions ([BGHSV,BS]), we
revisit the study of efficient PCPs. We show that every language in NP has a
probabilistically checkable proof of proximity (i.e., proofs asserting that
an instance is ``close'' to a member of the language), where the verifier's
running time is polylogarithmic in the input size and the length of the
probabilistically checkable proof is only polylogarithmically larger that
the length of the classical proof.
 
Of technical interest in our proof is a new complete problem for NEXP based
on constraint satisfaction problems with very low complexity constraints,
and techniques to arithmetize such constraints over fields of small
characteristic.
 
Joint work with Eli Ben-Sasson, Oded Goldreich, Madhu Sudan and Salil Vadhan

 
 
-----------------
If you have questions, or would like to meet the speaker, please contact
Katherine at 773-834-1994 or kcumming at tti-c.org.  For information on future
TTI-C talks or events, please go to the TTI-C Events page,
http://www.tti-c.org/events.html.  TTI-C (1427 East 60th Street, Chicago, IL
60637)
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20051101/b597308e/attachment.htm