{"id":"arxiv/2601.08727","url":"https://arxiv.org/abs/2601.08727","tags":["cs.CC","cs.DM","quant-ph"],"score":0,"title":"Rational degree is polynomially related to degree","domain":"cs.CC","source":"arxiv","authors":["Robin Kothari","Matt Kovacs-Deak","Daochen Wang","Rain Zimin Yang"],"reviews":0,"subject":"cs.CC","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-13","reactions":{}}