[Colloquium] Reminder: Talk by Parikshit Gopalan, University of Washington, Today

[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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20080303/756b8d58/attachment.html