[Colloquium] Show & Tell Series at TTI-C (2/8/05 @ 12:15)

[Katherine Cumming]

TTI-C SHOW AND TELL SERIES TALK
 
 
Speaker: Eli Ben-Sasson, TTI-C
Speaker's home page: http://www.tti-c.org//ben-sasson.html
 
Time: Tuesday, February 8, 2005
Location: TTI-C Conference Room
Lunch/Refreshments Provided  @ 12:00pm 
Seminar @ 12:15pm
 
 
Title: Sub-linear time verification of computations
 
Abstract: 
 
I will describe some of our recent work on Probabilistically 
Checkable Proofs (PCPs), Locally Testable Codes (LTCs) and their 
connections to Complexity Theory at large.
 
In particular, we will show that the task of verifying a computation 
reduces to the task of verifying that a function is close to a 
low-degree, uni-variate polynomial.
 
The talk is intended for a general CS audience.
 
Joint work with: Oded Goldriech, Prahladh Harsha, Madhu Sudan and Salil 
Vadhan.
 
 
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20050201/3083888d/attachment.htm