[Theory] TCS+ talk tomorrow

[Janos Simon]

This may be of interest
https://sites.google.com/site/plustcs/
(12-1 Wed)

1:00pm (ET)
 TCS+ talk: Shravas Rao (Northwestern University)
WhenWed, October 27, 1pm – 2pm
DescriptionTitle: Degree vs. Approximate Degree and Quantum Implications of
Huang's Sensitivity Theorem

Abstract:  Based on the recent breakthrough of Huang (2019), we show that
for any total Boolean function f,

-  The degree of f is at most quadratic in the approximate degree of f.
This is optimal as witnessed by the OR function.
- 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).

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)).

Based on joint work with Scott Aaronson, Shalev Ben-David, Robin Kothari,
and Avishay Tal

Link:
https://berkeley.zoom.us/j/98954371813?pwd=V1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09
<https://www.google.com/url?q=https%3A%2F%2Fberkeley.zoom.us%2Fj%2F98954371813%3Fpwd%3DV1hxN2Nrc2c5OEJFSWRqS29JeWM1dz09&sa=D&ust=1635698351653000&usg=AOvVaw1MUmShASS30IWXP1wFh2RJ>
more details»
<https://www.google.com/calendar/event?eid=MjFta29rcjZjNmE4ZTMydG0xc2lxZHVzb3IgcGx1c3Rjc0Bt&ctz=America/Toronto>
  copy to my calendar
<https://calendar.google.com/calendar/u/1/r/eventedit/copy/MjFta29rcjZjNmE4ZTMydG0xc2lxZHVzb3IgcGx1c3Rjc0Bt>


Janos Simon
Professor, Department of Computer Science and The College
Director of Graduate Studies, Computer Science
The University of Chicago
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20211026/f0ddd3b2/attachment.html>