Rational degree is polynomially related to degree
arXiv:2601.0872787.91 citationsh-index: 2
AI Analysis
This solves a long-standing open problem in computational complexity theory, providing a fundamental relationship between two key complexity measures for Boolean functions.
The paper resolves the second of three open problems from 1994 by proving that the degree of any Boolean function is polynomially bounded by its rational degree, specifically deg(f) ≤ Õ(rdeg(f)^3).
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.