[CSDM] Fwd: Pei Wu @ Theory Lunch This Friday!

[Toniann Pitassi]

Should be a good talk! --Toni

---------- Forwarded message ---------
From: Barak Nehoran <bnehoran at princeton.edu>
Date: Fri, Sep 16, 2022 at 10:56 AM
Subject: Re: Pei Wu @ Theory Lunch This Friday!
To: <theory-read at lists.cs.princeton.edu>, Linda Cai <tcai at princeton.edu>
Cc: <discretemath at math.princeton.edu>, <
alg-ml-reading-group at lists.cs.princeton.edu>


Reminder that this is happening in 1 hour in the Friend Center Convocation
Room.

On Tue, Sep 13, 2022, 11:43 PM Barak Nehoran <bnehoran at princeton.edu> wrote:

> Hello everyone,
>
> 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!
>
> 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.
>
> Location of the talk: Friend Center Convocation Room.
>
> The details of the talk are as follows.
>
> Title: Random restrictions on boolean functions with small influences
>
> 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}$.
>
> 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.
>
> See you there!
>
> Barak and Linda
>
>
> 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
>
> https://lists.cs.princeton.edu/mailman/listinfo/theory-read
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://imap.math.ias.edu/pipermail/csdm/attachments/20220916/32928550/attachment.html>