<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:st1="urn:schemas-microsoft-com:office:smarttags" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv=Content-Type content="text/html; charset=us-ascii">
<meta name=Generator content="Microsoft Word 11 (filtered medium)">
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="PlaceType"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="PlaceName"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="place"/>
<!--[if !mso]>
<style>
st1\:*{behavior:url(#default#ieooui) }
</style>
<![endif]-->
<style>
<!--
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman";}
a:link, span.MsoHyperlink
{color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:Arial;
color:windowtext;}
@page Section1
{size:8.5in 11.0in;
margin:1.0in 1.25in 1.0in 1.25in;}
div.Section1
{page:Section1;}
-->
</style>
</head>
<body lang=EN-US link=blue vlink=purple>
<div class=Section1>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial'>When:
Wed, Mar 5,
2008 @ 10:00 am<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial'>Where:
TTI-C Conference Room<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial'>Who:
Parikshit
Gopalan, <st1:place w:st="on"><st1:PlaceType w:st="on">University</st1:PlaceType>
of <st1:PlaceName w:st="on">Washington</st1:PlaceName></st1:place><o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial'>Topic:
</span></font><font
face=Arial><span style='font-family:Arial'>Fitting Polynomials to Noisy Data</span></font><font
size=2 face=Arial><span style='font-size:11.0pt;font-family:Arial'><o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>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. <o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>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.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>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.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>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.<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>Contact:
Julia Chuzhoy, TTI-C cjulia@tti-c.org
4-2490<o:p></o:p></span></font></p>
<p class=MsoNormal><font size=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
</div>
</body>
</html>