<html 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="PlaceName"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="PlaceType"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="State"/>
<o:SmartTagType namespaceuri="urn:schemas-microsoft-com:office:smarttags"
name="City"/>
<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;}
pre
{margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";
color:black;}
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><pre><font size=2 color=black face="Courier New"><span
style='font-size:10.0pt'>When: Tuesday, November 27, 2007 @ 10:00 AM<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>Where: TTI-C Conference Room<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>Who: Alexander Razborov - Institute for Advanced Study, <st1:place
w:st="on"><st1:City w:st="on">Princeton</st1:City> <st1:State w:st="on">NJ</st1:State></st1:place>.<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>Topic: The Sign-Rank of $AC^0$<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>The sign-rank of a matrix $M$ with $\pm 1$ entries is the smallest<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>rank of a real matrix $A$ such that $M_{ij}=sign(A_{ij})$ for all<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>$i,j$. We exhibit a $2^n\times 2^n$ matrix $M$ computable by depth 2<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>circuits of polynomial size whose sign-rank is exponential in $n$. Our<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>result has the following immediate applications.<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>1. In the context of communication complexity alternations can be more<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>powerful than unbounded-error probabilism. This solves a long-standing<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>open problem asked in the seminal paper by Babai, Frankl and Simon<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>(1986).<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>2. Exponential lower bounds on the dimension complexity of the class<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>of all DNF formulas. Our bound almost matches the upper bound proved<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>by Klivans and Servedio (2001) and provides apparently the first<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>unconditional exponential lower bound for PAC learning of DNF formulas<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>in a reasonable model.<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>3. The first exponential lower bound on the size of<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>thershold-of-majority circuits computing a function in $AC^0$.<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'>Joint work with Alexander Sherstov (<st1:place
w:st="on"><st1:PlaceType w:st="on">U.</st1:PlaceType> of <st1:PlaceName w:st="on">Texas</st1:PlaceName></st1:place>)<o:p></o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre><pre><font
size=2 color=black face="Courier New"><span style='font-size:10.0pt'><o:p> </o:p></span></font></pre>
<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>
</div>
</body>
</html>