<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="City"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="country-region"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="place"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="PlaceName"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="PlaceType"/>
<!--[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;
font-family:Arial;
color:windowtext;}
span.EmailStyle18
{mso-style-type:personal;
font-family:Arial;
color:navy;}
span.EmailStyle19
{mso-style-type:personal-reply;
font-family:Arial;
color:navy;}
@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><b><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial;font-weight:bold'>When:
Wed, Mar 5,
2008 @ 10:00 am<o:p></o:p></span></font></b></p>
<p class=MsoNormal><b><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial;font-weight:bold'><o:p> </o:p></span></font></b></p>
<p class=MsoNormal><b><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial;font-weight:bold'>Where:
TTI-C Conference Room<o:p></o:p></span></font></b></p>
<p class=MsoNormal><b><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial;font-weight:bold'><o:p> </o:p></span></font></b></p>
<p class=MsoNormal><b><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial;font-weight:bold'>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></b></p>
<p class=MsoNormal><b><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial;font-weight:bold'><o:p> </o:p></span></font></b></p>
<p class=MsoNormal><b><font size=2 face=Arial><span style='font-size:11.0pt;
font-family:Arial;font-weight:bold'>Topic:
</span></font></b><b><font
face=Arial><span style='font-family:Arial;font-weight:bold'>Fitting Polynomials
to Noisy Data</span></font></b><b><font size=2 face=Arial><span
style='font-size:11.0pt;font-family:Arial;font-weight:bold'><o:p></o:p></span></font></b></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 color=navy face=Arial><span style='font-size:
10.0pt;font-family:Arial;color:navy'><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=3 color=navy face=Arial><span style='font-size:
12.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 color=navy face=Arial><span style='font-size:
12.0pt;font-family:Arial;color:navy'><o:p> </o:p></span></font></p>
<p class=MsoNormal><font size=3 face=Arial><span style='font-size:12.0pt;
font-family:Arial'>About Parikshit Gopalan:<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'>Parikshit Gopalan grew up in <st1:country-region w:st="on">India</st1:country-region>
in the city of <st1:place w:st="on"><st1:City w:st="on">Bombay</st1:City></st1:place>
(now called Mumbai). He graduated with an undergraduate degree from IIT-Bombay
(whose name, thankfully, has not changed). He received his Ph.D from Georgia
Tech in August 2006, under the guidance of Dick Lipton. Following this, he did
a short stint as a postdoctoral researcher at the <st1:PlaceType w:st="on">University</st1:PlaceType>
of <st1:PlaceName w:st="on">Texas</st1:PlaceName> at <st1:place w:st="on"><st1:City
w:st="on">Austin</st1:City></st1:place>. He is currently a postdoc at the <st1:PlaceType
w:st="on">University</st1:PlaceType> of <st1:PlaceName w:st="on">Washington</st1:PlaceName>,
visiting <st1:place w:st="on"><st1:PlaceName w:st="on">Princeton</st1:PlaceName>
<st1:PlaceType w:st="on">University</st1:PlaceType></st1:place>. <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'>His research focuses on theoretical computer science,
especially on algebraic problems arising from algorithms and complexity. He
also likes to dabble in other areas such as Data-stream algorithms and
Communication complexity.<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'>His website is: <a
href="http://www.cs.washington.edu/homes/parik">http://www.cs.washington.edu/homes/parik</a><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=2 face=Arial><span style='font-size:10.0pt;
font-family:Arial'><o:p> </o:p></span></font></p>
</div>
</body>
</html>