RSS icon
Twitter icon
Facebook icon
Vimeo icon
YouTube icon

Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem

February 10, 2021 - 11:00am
Robin Kothari

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function f, deg(f) = O(~deg(f)^2): The degree of f is at most quadratic in the approximate degree of f. This is optimal as witnessed by the OR function.  D(f) = O(Q(f)^4): 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)=Omega(n), which is also optimal. We also show that the approximate degree of any read-once formula on n variables is Theta(sqrt{n}).  This is joint work with Scott Aaronson, Shalev Ben-David, Shravas Rao, and Avishay Tal.  Preprint available at

Join Zoom Meeting

Meeting ID: 925 8265 5277
Passcode: 156236
One tap mobile
+13017158592,,92582655277# US (Washington D.C)
+19294362866,,92582655277# US (New York)

Dial by your location
        +1 301 715 8592 US (Washington D.C)
        +1 929 436 2866 US (New York)
        +1 312 626 6799 US (Chicago)
        +1 669 900 6833 US (San Jose)
        +1 253 215 8782 US (Tacoma)
        +1 346 248 7799 US (Houston)
Meeting ID: 925 8265 5277
Find your local number:

Join by SIP

Join by H.323 (US West) (US East) (India Mumbai) (India Hyderabad) (Amsterdam Netherlands) (Germany) (Australia) (Singapore) (Brazil) (Canada) (Japan)
Meeting ID: 925 8265 5277
Passcode: 156236