log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
Degree vs. Approximate Degree and Quantum Implications of Huang’s Sensitivity Theorem
Robin Kothari - Microsoft
Virtual Via Zoom: https://umd.zoom.us/j/92582655277?pwd=WVU2MHlMRXl2YzNPTFhkbzBvd1R3QT09
Wednesday, February 10, 2021, 11:00 am-12:15 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
Abstract

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 https://arxiv.org/abs/2010.12629.

Join Zoom Meeting

https://umd.zoom.us/j/92582655277?pwd=WVU2MHlMRXl2YzNPTFhkbzBvd1R3QT09

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: https://umd.zoom.us/u/ar7VZKLCK

Join by SIP

92582655277@zoomcrc.com

Join by H.323

162.255.37.11 (US West)

162.255.36.11 (US East)

115.114.131.7 (India Mumbai)

115.114.115.7 (India Hyderabad)

213.19.144.110 (Amsterdam Netherlands)

213.244.140.110 (Germany)

103.122.166.55 (Australia)

149.137.40.110 (Singapore)

64.211.144.160 (Brazil)

69.174.57.160 (Canada)

207.226.132.110 (Japan)

Meeting ID: 925 8265 5277

Passcode: 156236

This talk is organized by Andrea F. Svejda