Rational degree is polynomially related to degree

Matt Kovacs-Deak, Daochen Wang, Rain Zimin Yang (Jan 14 2026).

Abstract: We prove that $\mathrm{deg}(f) \leq 2 \, \mathrm{rdeg}(f)^4$ 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.

Arxiv: https://arxiv.org/abs/2601.08727