<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div></div><div>Hi Donna,</div><div><br></div><div>Does Andrej have a hotel reservation (he said he had not received any</div><div>confirmation)?</div><div><br></div><div>Thank you,</div><div>Sasha</div><div><br>On Apr 6, 2017, at 8:12 AM, Donna Brooms via Colloquium via faculty <<a href="mailto:faculty@mailman.cs.uchicago.edu">faculty@mailman.cs.uchicago.edu</a>> wrote:<br><br></div><blockquote type="cite"><div><meta http-equiv="Content-Type" content="text/html charset=utf-8">Combinatorics & Theoretical Seminar<br class=""> <br class="">Tuesday, April 18, 2017<br class="">Ryerson 251 @ 3pm<br class=""><br class=""><b class="">Andrej Bogdanov</b><br class="">Chinese University of Hong Kong<br class=""><a href="http://www.cs.washington.edu/homes/jrl/" class="">http://www.cs.washington.edu/homes/jrl/</a><br class=""><br class="">Title: “Small bias requires large formulas”<br class="">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.<br class=""><br class=""><div class="">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.<br class=""><br class=""></div><div class="">Host: Prof. Alexander Razborov<br class=""><br class=""></div><div class="">Refreshments will be served before the talk in Ry 255.<br class=""><br class=""> <br class=""><br class=""> </div></div></blockquote><blockquote type="cite"><div><span>_______________________________________________</span><br><span>Colloquium mailing list - <a href="mailto:Colloquium@mailman.cs.uchicago.edu">Colloquium@mailman.cs.uchicago.edu</a></span><br><span><a href="https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium">https://mailman.cs.uchicago.edu/mailman/listinfo/colloquium</a></span><br></div></blockquote><blockquote type="cite"><div><span>_______________________________________________</span><br><span>faculty mailing list - <a href="mailto:faculty@mailman.cs.uchicago.edu">faculty@mailman.cs.uchicago.edu</a></span><br><span><a href="https://mailman.cs.uchicago.edu/mailman/listinfo/faculty">https://mailman.cs.uchicago.edu/mailman/listinfo/faculty</a></span><br></div></blockquote></body></html>