[Colloquium] Talk by Parikshit Gopalan, University of Washington on March 3, 2008

[caseyk]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Monday, March 3, 2008
Time: 2:30 p.m.
Place: Ryerson 251, 1100 E. 58th Street

----------------------------------------------

Speaker:	Parikshit Gopalan

From:		University of Washington

Web page:	http://www.cs.washington.edu/homes/parik/

Title:  Fitting Polynomials to Noisy Data

Abstract:  The problem of finding the polynomial that best fits a  
noisy data-set (or polynomial reconstruction) has a long history,  
dating back to curve-fitting problems studied in the 1800s. In the  
last two decades, there has been tremendous progress on this problem  
in computer science, driven by the discovery of powerful new  
algorithms. These results have spurred exciting new developments in  
Coding theory, Computational learning, Cryptography and Hardness of  
Approximation. In this talk, we will explore this problem from the  
perspectives of Coding theory and Computational learning.
We begin with an algorithm for decoding a well-studied family of  
binary error-correcting codes called Reed-Muller codes, which are  
obtained from low-degree polynomials. The salient feature of this  
algorithm is that it works even when the number of errors far exceeds  
the so-called Johnson bound.

I will present an algorithm for agnostically learning decision trees  
under the uniform distribution. This is the first polynomial time  
algorithm for learning decision trees in a harsh noise model. This  
algorithm solves the reconstruction problem for real polynomials using  
tools from convex optimization.

I will also discuss settings where the reconstruction problem seems  
intractable. We will see evidence that the notorious Noisy Parity  
problem is hard under the uniform distribution. We will present  
hardness results suggesting that learning simple concepts with noise  
is impossible for arbitrary distributions.

-----------------------------------------------

Host: Laci Babai