[Colloquium] Re: [Faculty] Theory Seminars at Computer Science
Alexander Razborov via Colloquium
colloquium at mailman.cs.uchicago.edu
Tue Apr 11 09:37:11 CDT 2017
Hi Donna,
Does Andrej have a hotel reservation (he said he had not received any
confirmation)?
Thank you,
Sasha
> On Apr 6, 2017, at 8:12 AM, Donna Brooms via Colloquium via faculty <faculty at mailman.cs.uchicago.edu> wrote:
>
> Combinatorics & Theoretical Seminar
>
> Tuesday, April 18, 2017
> Ryerson 251 @ 3pm
>
> Andrej Bogdanov
> Chinese University of Hong Kong
> http://www.cs.washington.edu/homes/jrl/
>
> Title: “Small bias requires large formulas”
> A small-biased function is a randomized function whose distribution of truth-tables is small-biased. We show that known explicit lower bounds on the size of (1) general Boolean formulas, (2) Boolean formulas of fan-in two, (3) de Morgan formulas, as well as (4) correlation lower bounds against small de Morgan formulas apply to small-biased functions. As a consequence, any strongly explicit small-biased generator is subject to the best known explicit formula lower bounds in all these models.
>
> On the other hand, we give a construction of a small-biased function that is tight with respect to lower bounds (1) and (2) for the relevant range of parameters. We interpret this construction as a natural-like barrier against substantially stronger lower bounds for general formulas.
>
> Host: Prof. Alexander Razborov
>
> Refreshments will be served before the talk in Ry 255.
>
>
>
>
> _______________________________________________
> Colloquium mailing list - Colloquium at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium
> _______________________________________________
> faculty mailing list - faculty at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/mailman/listinfo/faculty
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170411/9351db2c/attachment.html>
More information about the Colloquium
mailing list