Rational degree is polynomially related to degree

Robin Kothari, Matt Kovacs-Deak, Daochen Wang +1

We prove that $\mathrm{deg}(f)\le \tilde{O}(\mathrm{rdeg}(f{)}^3)$ for every Boolean function $f$, where $\mathrm{deg}(f)$ is the degree of $f$ and $\mathrm{rdeg}(f)$ is the ra…