Rational degree is polynomially related to degree

Abstract

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 rational degree of $f$. This resolves the second of the three open problems stated by Nisan and Szegedy, and attributed to Fortnow, in 1994.

26 pages; v2: added an author, improved main result