<div dir="ltr"><br>Should be a good talk! --Toni<div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">---------- Forwarded message ---------<br>From: <strong class="gmail_sendername" dir="auto">Barak Nehoran</strong> <span dir="auto"><<a href="mailto:bnehoran@princeton.edu">bnehoran@princeton.edu</a>></span><br>Date: Fri, Sep 16, 2022 at 10:56 AM<br>Subject: Re: Pei Wu @ Theory Lunch This Friday!<br>To: <<a href="mailto:theory-read@lists.cs.princeton.edu">theory-read@lists.cs.princeton.edu</a>>, Linda Cai <<a href="mailto:tcai@princeton.edu">tcai@princeton.edu</a>><br>Cc: <<a href="mailto:discretemath@math.princeton.edu">discretemath@math.princeton.edu</a>>, <<a href="mailto:alg-ml-reading-group@lists.cs.princeton.edu">alg-ml-reading-group@lists.cs.princeton.edu</a>><br></div><br><br><div dir="auto">Reminder that this is happening in 1 hour in the Friend Center Convocation Room.</div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Sep 13, 2022, 11:43 PM Barak Nehoran <<a href="mailto:bnehoran@princeton.edu" target="_blank">bnehoran@princeton.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="auto"><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:arial;color:rgb(0,0,0);font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">Hello everyone,</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:arial;color:rgb(0,0,0);font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">After two years of pandemic we are officially having our first Theory Lunch of the year this Friday (September 16th)! We are delighted to have Pei Wu from IAS as our first speaker! </span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:arial;color:rgb(0,0,0);font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">The food will be served at 11:45 am, and the talk will start at 12 pm. Please come early for lunch so that the talk starts on time.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:arial;color:rgb(0,0,0);font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">Location of the talk: Friend Center Convocation Room.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:arial;color:rgb(0,0,0);font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">The details of the talk are as follows. </span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:arial;color:rgb(0,0,0);font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">Title: Random restrictions on boolean functions with small influences</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:arial;color:rgb(0,0,0);font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">Abstract: In the talk, we discuss the probability of Boolean functions with small max influence to become constant under random restrictions. Let f be a Boolean function such that the variance of f is $\Omega(1)$ and all its individual influences are bounded by $\tau$. We show that when restricting all but a $\tilde{\Omega}((\log1/\tau)^{-1})$ fraction of the coordinates, the restricted function remains nonconstant with overwhelming probability. This bound is essentially optimal, as witnessed by the tribes function $AND_{n/C\log n} \circ OR_{C\log n}$.</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:arial;color:rgb(0,0,0);font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">We extend it to an anti-concentration result, showing that the restricted function has nontrivial variance with probability 1-o(1). This gives a sharp version of the ``it ain't over till it's over'' theorem due to Mossel, O'Donnell, and Oleszkiewicz.</span></p><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:arial;color:rgb(0,0,0);font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">See you there!</span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:arial;color:rgb(0,0,0);font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">Barak and Linda </span></p><br><br><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><span style="font-size:11pt;font-family:arial;color:rgb(0,0,0);font-variant-numeric:normal;font-variant-east-asian:normal;vertical-align:baseline;white-space:pre-wrap">P.S. If you'd like to be notified about future Theory Lunch talks, and you're not already on the mailing list, you can add yourself at </span></p><p dir="ltr" style="line-height:1.38;margin-top:0pt;margin-bottom:0pt"><a href="https://lists.cs.princeton.edu/mailman/listinfo/theory-read" style="text-decoration-line:none" rel="noreferrer" target="_blank"><span style="font-size:11pt;font-family:arial;color:rgb(17,85,204);font-variant-numeric:normal;font-variant-east-asian:normal;text-decoration-line:underline;vertical-align:baseline;white-space:pre-wrap">https://lists.cs.princeton.edu/mailman/listinfo/theory-read</span></a></p></div>
</blockquote></div>
</div></div></div>