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

Scott Aaronson, Shalev Ben-David, Robin Kothari +2

Based on the recent breakthrough of Huang (2019), we show that for any total Boolean function $f$, $\bullet \mathrm{deg}(f)=O(\widetilde{\mathrm{deg}}(f{)}^2)$: The degree of…