Rational degree is polynomially related to degree

arXiv (Cornell University) 2026 Preprint Open access

Read full text
Authors: Robin Kothari, Matt Kovacs-Deak, Daochen Wang, Rain Zimin Yang
DOI: 10.48550/arxiv.2601.08727
Cited by: 0

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.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Computability Logic AI Algorithms Polynomial and algebraic computation

Publication details

Journal / source
arXiv (Cornell University)
Publication date
13 January 2026
Document type
Preprint