<div dir="ltr"><div dir="ltr"><p dir="ltr" style="color:rgb(0,0,0);font-family:-webkit-standard;line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-family:Arial;color:rgb(47,47,47);background-color:transparent;font-weight:700;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"><span style="color:rgb(0,0,0);font-family:arial,helvetica,sans-serif">When: </span><span style="color:rgb(0,0,0);font-family:arial,helvetica,sans-serif;font-weight:400">    Wednesday, May 8th </span><span class="gmail-m_7448609273631148031gmail-m_-2154329794935359533gmail-m_-8793282726721029490gmail-m_-3244609389970801979gmail-m_-3623658629141391452gmail-m_9092035972284487620gmail-m_3787129533418353062m_8623545428725725323gmail-m_2873882304663502708gmail-m_-3789046984517165451gmail-m_6280573200025755333gmail-m_5159318120685850543gmail-m_1790959466673216095gmail-m_-5333227643664982572m_2625127627517695854m_2683896348608817813gmail-m_7672563966056633266gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il" style="color:rgb(0,0,0);font-family:arial,helvetica,sans-serif;font-weight:400">at</span><span style="color:rgb(0,0,0);font-family:arial,helvetica,sans-serif;font-weight:400"> </span><b style="color:rgb(0,0,0);font-family:arial,helvetica,sans-serif">11:00 am</b>
</span></p><div class="gmail_default"><font color="#000000" face="arial, helvetica, sans-serif"><br></font></div><div class="gmail_default" style="font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif">Where:<span style="font-weight:400">    </span><span class="gmail-m_7448609273631148031gmail-m_-2154329794935359533gmail-m_-8793282726721029490gmail-m_-3244609389970801979gmail-m_-3623658629141391452gmail-m_9092035972284487620gmail-m_3787129533418353062m_8623545428725725323gmail-m_2873882304663502708gmail-m_-3789046984517165451gmail-m_6280573200025755333gmail-m_5159318120685850543gmail-m_1790959466673216095gmail-m_-5333227643664982572m_2625127627517695854m_2683896348608817813gmail-m_7672563966056633266gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-m_8421504075585210435gmail-m_3262824545120381495gmail-m_-1141671822915777344gmail-m_-7219251726624328345gmail-m_-8588148075564318222gmail-m_-8767966813928691312gmail-m_-1542318334608687154gmail-m_5717104778280916634gmail-m_4845490158781220632gmail-m_5124567205141626540gmail-m_3209361100497750746gmail-m_2953668934074478317gmail-m_-3155518689668024534m_9067904842688472155gmail-m_3071693547520408192gmail-il" style="font-weight:400"><span class="gmail-m_7448609273631148031gmail-m_-2154329794935359533gmail-m_-8793282726721029490gmail-m_-3244609389970801979gmail-m_-3623658629141391452gmail-m_9092035972284487620gmail-m_3787129533418353062m_8623545428725725323gmail-m_2873882304663502708gmail-m_-3789046984517165451gmail-m_6280573200025755333gmail-m_5159318120685850543gmail-m_1790959466673216095gmail-m_-5333227643664982572m_2625127627517695854m_2683896348608817813gmail-m_7672563966056633266gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-m_8517121454174849988gmail-m_-6691959996525573090gmail-m_1517372298344856049gmail-m_491069367152086750gmail-m_-8327640324523575189gmail-m_2420618808463760418gmail-m_7960197898027616883gmail-m_8692226636264124041gmail-m_2794822896869921223gmail-m_7508998950622620526gmail-m_-7153355664495542534gmail-il"><span class="gmail-m_7448609273631148031gmail-m_-2154329794935359533gmail-m_-8793282726721029490gmail-m_-3244609389970801979gmail-m_-3623658629141391452gmail-m_9092035972284487620gmail-m_3787129533418353062m_8623545428725725323gmail-m_2873882304663502708gmail-m_-3789046984517165451gmail-m_6280573200025755333gmail-m_5159318120685850543gmail-m_1790959466673216095gmail-m_-5333227643664982572m_2625127627517695854m_2683896348608817813gmail-m_7672563966056633266gmail-m_-6461243813863673855gmail-m_-742000311328020925gmail-m_7559459027998801583gmail-m_4801029585485711767gmail-il">TTIC</span></span></span><span style="font-weight:400">, 6045 S Kenwood Avenue, 5th Floor, Room 526</span></font></div><div class="gmail_default" style="font-weight:bold"><font color="#000000" face="arial, helvetica, sans-serif"><span style="font-weight:400"><br></span></font></div><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(47,47,47);background-color:transparent;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"><font style="color:rgb(34,34,34);white-space:normal"><span style="color:rgb(0,0,0)"><b>Who:</b></span><span style="color:rgb(0,0,0)"><b> </b>      </span></font></span><font color="#000000">Pritish Kamath, MIT</font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><font color="#000000"><br></font></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(47,47,47);background-color:transparent;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"><font face="arial, helvetica, sans-serif"><b>Title:        </b></font></span><font face="arial, helvetica, sans-serif" style="" color="#000000">Non-Interactive Agreement and Dimension Reduction for Polynomials</font></p><p dir="ltr" style="color:rgb(0,0,0);line-height:1.38;margin-top:0pt;margin-bottom:0pt"><br></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="color:rgb(34,34,34);background-color:transparent;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap"><font face="arial, helvetica, sans-serif"><b>Abstract: </b></font></span><font face="arial, helvetica, sans-serif" style="" color="#000000">The ability to harness and work with randomness has been at the heart of information theory and theoretical computer science. Of particular interest to this talk is the use of randomness by a set of parties that are spread out geographically. For example, randomness can enable such parties to generate and share secrets.</font></p><div class="gmail_default" style=""><font face="arial, helvetica, sans-serif" color="#000000"><br></font></div><div class="gmail_default" style=""><div class="gmail_default" style=""><font face="arial, helvetica, sans-serif" color="#000000">The "Non-interactive Agreement Distillation" problem, specified by a joint distribution P(x,y) and a target alphabet size k, is defined as follows: Two players observe sequences (X_1, ... , X_n) and (Y_1, ... , Y_n) respectively where {(X_i, Y_i)} are drawn i.i.d. from P(x,y). Both players look at their share of randomness, and output an element of [k]. Their goal is to maximize the probability that their outputs are the same, while ensuring that their outputs are marginally uniform.</font></div><div class="gmail_default" style=""><font face="arial, helvetica, sans-serif" color="#000000"><br></font></div><div class="gmail_default" style=""><font face="arial, helvetica, sans-serif" color="#000000">Given P(x,y) and k, what is the largest correlation (agreement probability) that the players can achieve? It turns out that this value is not well understood, even in some well motivated special cases. A priori, this value is not even "computable", as there is no immediate upper bound on the number of samples the players need to draw in order to achieve the best possible correlation!</font></div><div class="gmail_default" style=""><font face="arial, helvetica, sans-serif" color="#000000"><br></font></div><div class="gmail_default" style=""><font face="arial, helvetica, sans-serif" color="#000000">This talk will describe a recent line of work that obtains an explicit bound on the number of samples needed to get \epsilon-close to the maximum achievable correlation. At the heart of our result is a new technique that we call "Dimension Reduction for Polynomials". It can be viewed as a generalization of the well-known Johnson-Lindenstrauss lemma, which in this context, corresponds to the special case of degree-1 polynomials. We believe this technique could be of broader interest.</font></div><div class="gmail_default" style=""><font face="arial, helvetica, sans-serif" color="#000000"><br></font></div><div class="gmail_default" style=""><font face="arial, helvetica, sans-serif" color="#000000">This talk will discuss the motivational aspects of the problem, its moral and technical connections to other problems in theoretical computer science and will mainly focus on the technique of "dimension reduction for polynomials".</font></div><div class="gmail_default" style=""><font face="arial, helvetica, sans-serif" color="#000000"><br></font></div><div class="gmail_default" style=""><font face="arial, helvetica, sans-serif" color="#000000"><font style="">Based on joint works with Badih Ghazi, Prasad Raghavendra and Madhu Sudan. [</font><a href="https://arxiv.org/abs/1607.04322" target="_blank" style="">arXiv:1607.04322</a>, <a href="https://arxiv.org/abs/1708.03808" target="_blank" style="">arXiv:1708.03808</a>]</font></div><div class="gmail_default" style=""><font face="arial, helvetica, sans-serif" color="#000000"><br></font></div></div><div><b style="color:rgb(33,33,33)">Host: </b><font face="arial, helvetica, sans-serif" style="color:rgb(33,33,33)"><a href="mailto:nati@ttic.edu">Nati Srebro</a></font></div><div><br></div>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><b><font color="#0b5394">Alicia McClarin</font></b><div><div><font color="#0b5394"><i>Toyota Technological Institute at Chicago</i></font></div><div><div><font color="#0b5394"><i>6045 S. Kenwood Ave., </i></font><i style="color:rgb(11,83,148)">Office 510</i></div><div><font color="#0b5394"><i>Chicago, IL 60637</i></font></div><div><font color="#0b5394"><i>773-702-5370</i></font></div></div><div><a href="http://www.ttic.edu/" target="_blank"><font color="#0b5394"><i>www.ttic.edu</i></font></a></div></div></div></div></div></div></div></div></div>