Open Research Index

Rational degree is polynomially related to degree

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

arXivarxiv/2601.08727Jan 13, 2026cs.CCscore 0

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.

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2601.08727
curl -X POST /api/v1/records/arxiv/2601.08727/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.08727/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'