[Colloquium] Talk Next Week @ TTI-C: Eli Ben-Sasson, 4/10 @ 12:15pm

[Katherine Cumming]

TOYOTA TECHNOLOGICAL INSTITUTE TALK
 
 
Show and Tell Series-Lunch 
 
Speaker:  Eli Ben-Sasson
Speaker's homepage:  http://www.tti-c.org//ben-sasson.html
 
Time:  Tuesday, May 10th @ 12:15pm
Location:  TTI-C Conference Room 
 
 
Title: On FFTs and PCPPs (for Reed-Solomon codes)
 
Abstract: A key component in recent constructions of short PCPs, is a
*PCP of Proximity* (PCPP, also known as *assignment tester*) for
*Reed-Solomon* codes (see definitions below). In this talk we describe
efficient constructions of such PCPPs and their connection to new Fast
Fourier Transform (FFT) algorithms. Time permitting, we will describe
how to obtain the PCP Theorem given solutions to our problem. The talk
is intended for a general audience with CS background.

The *Reed-Solomon* code of degree d over finite field F is the set of
functions p:F->F that are polynomials of degree at most d. Reed-Solomon
codes have numerous applications in theoretical computer science and are
heavily used in practice.

Let C be a set of functions with range R and domain D (in our case, C is
the Reed-Solomon code and R=D=F) A *PCPP* for C allows a (randomized
polynomial time) *verifier* to probe a function f:R->D and auxiliary
proof (of proximity) on few locations and distinguish between the case
that f belongs to C and the case that f is far (in Hamming distance)
from *any* function in C. In the first case (f in C), there exists a
"good" proof oracle such that f is accepted by the verifier with
probability one. In the second case (f far from C), the verifier rejects
f with probability 1/2, no matter what "proof" accompanies it.

Joint work with Madhu Sudan. 
 
 
 
 
-----------------------------------------------------------------
 
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 and 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/20050505/93edaa86/attachment.htm