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