skip to main content

TCS+ Talk

Wednesday, October 27, 2021
10:00am to 11:00am
Add to Cal
Online Event
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem
Shravas Rao, Postdoc, Northwestern University,

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


To watch the talk:

  • Watching the live stream. At the announced start time of the talk (or a minute before), a live video stream will be available on our "next talk" page. Simply connect to the page and enjoy the talk. No webcam or registration is needed. Questions and comments during the talk are welcome (text only, unfortunately); simply post a comment below the live video stream on YouTube.
  • Watching the recorded talk offline. The recorded talk will be made available shortly after the talk ends on our YouTube page. (Please leave a comment if you enjoyed it!)
For more information, please contact Bonnie Leung by email at [email protected].