<div dir="ltr"><div>This may be of interest</div><div><a href="https://sites.google.com/site/plustcs/">https://sites.google.com/site/plustcs/</a></div><div>(12-1 Wed)</div><div><br></div><div><div class="event gmail-first-event"><div class="event-summary-expanded" id="gmail-1-20211027"><span class="event-time" alt="Wed, October 27, 1pm – 2pm" title="Wed, October 27, 1pm – 2pm">1:00pm (ET)<br></span><div class="gmail-title-wrapper"><span class="event-reply-status"> </span><span class="event-title" style="color:rgb(41,82,163)">TCS+ talk: Shravas Rao (Northwestern University)</span></div></div><div class="event-details" id="gmail-details-1-20211027"><div class="event-details-inner"><div class="gmail-detail-item"><span class="event-details-label">When</span><span class="event-when">Wed, October 27, 1pm – 2pm</span></div><div class="gmail-detail-item"><span class="event-details-label">Description</span><span class="event-description">Title: <span>Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem</span><br><span> </span><br><span>Abstract:  Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function f, <br> <br>-  The degree of f is at most quadratic in the approximate degree of f. This is optimal as witnessed by the OR function. <br>- The deterministic query complexity of f is at most quartic in the quantum query complexity of f. This matches the known separation (up to log factors) due to Ambainis, Balodis, Belovs, Lee, Santha, and Smotrovs (2017). <br> <br>We apply these results to resolve the quantum analogue of the Aanderaa--Karp--Rosenberg conjecture. We show that if f is a nontrivial monotone graph property of an n-vertex graph specified by its adjacency matrix, then Q(f)=Ω(n), which is also optimal. We also show that the approximate degree of any read-once formula on n variables is Θ(\sqrt(n)). <br> <br>Based on joint work with Scott Aaronson, Shalev Ben-David, Robin Kothari, and Avishay Tal</span><br><span> </span><br><span>Link: <a href="https://www.google.com/url?q=https%3A%2F%2Fberkeley.zoom.us%2Fj%2F98954371813%3Fpwd%3DV1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09&sa=D&ust=1635698351653000&usg=AOvVaw1MUmShASS30IWXP1wFh2RJ" target="_blank">https://berkeley.zoom.us/j/98954371813?pwd=V1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09</a> </span></span></div><div class="event-links"><a href="https://www.google.com/calendar/event?eid=MjFta29rcjZjNmE4ZTMydG0xc2lxZHVzb3IgcGx1c3Rjc0Bt&ctz=America/Toronto" target="_blank">more details»</a>  <a href="https://calendar.google.com/calendar/u/1/r/eventedit/copy/MjFta29rcjZjNmE4ZTMydG0xc2lxZHVzb3IgcGx1c3Rjc0Bt" target="_blank">copy to my calendar</a></div><div class="event-links"><br></div><div class="event-links"><br></div></div></div></div></div><div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr">Janos Simon<br>Professor, Department of Computer Science and The College</div><div dir="ltr">Director of Graduate Studies, Computer Science<br><div>The University of Chicago</div></div></div></div></div></div></div></div></div></div>