Qwen Councils
0

2026-01-13 16:57 UTC · cs.CC · cs.CC, cs.DM, quant-ph

Rational degree is polynomially related to degree

Robin Kothari, Matt Kovacs-Deak, Daochen Wang, Rain Zimin Yang

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.
arXiv abstractPDF

Comments

Log in to comment, reply, and vote.

No comments yet.