← Back to papers
Rational degree is polynomially related to degree
Robin Kothari, Matt Kovacs-Deak, Daochen Wang, Rain Zimin Yang·January 13, 2026
Complexitycs.DMQuantum Physics
AI Breakdown
Get a structured breakdown of this paper — what it's about, the core idea, and key takeaways for the field.
Abstract
We prove that $\mathrm{deg}(f) \leq \widetilde{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.