Rational degree is polynomially related to degree

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

arxiv: 2601.08727 · v2 · submitted 2026-01-13 · 💻 cs.CC · cs.DM· quant-ph

Rational degree is polynomially related to degree

Robin Kothari , Matt Kovacs-Deak , Daochen Wang , Rain Zimin Yang This is my paper

Pith reviewed 2026-05-16 14:36 UTC · model grok-4.3

classification 💻 cs.CC cs.DMquant-ph

keywords Boolean functionspolynomial degreerational degreequery complexityNisan-Szegedy problems

0 comments

The pith

The degree of any Boolean function is at most roughly the cube of its rational degree.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that ordinary polynomial degree and rational degree of Boolean functions are related by a polynomial bound. For any Boolean function f, its degree is at most the cube of its rational degree up to logarithmic factors. This equivalence means the two measures capture similar complexity for all such functions. A reader cares because the result closes a specific open question from 1994 on whether rational representations could be exponentially more efficient than polynomial ones.

Core claim

We prove that deg(f) ≤ Õ(rdeg(f)^3) for every Boolean function f, where deg(f) is the degree of f and 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.

What carries the argument

An algebraic construction that turns a low-degree rational representation of a Boolean function into a polynomial representation whose degree is cubic in the rational degree.

If this is right

Polynomial degree and rational degree are polynomially equivalent complexity measures for every Boolean function.
Analyses of query complexity or decision tree depth that rely on one measure now transfer directly to the other up to polynomial factors.
The 1994 question on the relationship between these two degree notions is settled in the affirmative.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar conversion techniques might apply to approximate degree or other relaxed representations of Boolean functions.
The cubic exponent could be improved or shown tight by constructing specific functions that nearly achieve the bound.
The result suggests rational functions do not yield exponential savings over polynomials for exact representation on the Boolean cube.

Load-bearing premise

The standard algebraic definitions of polynomial degree and rational degree over the reals apply to all Boolean functions on the hypercube without further restrictions.

What would settle it

A Boolean function where ordinary degree exceeds the cube of rational degree by more than a polylogarithmic factor would falsify the bound.

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper proves deg(f) ≤ Õ(rdeg(f)^3) for Boolean functions and thereby closes the second open problem from Nisan and Szegedy 1994.

read the letter

The key takeaway is that this work proves deg(f) is at most the cube of rdeg(f), up to logarithmic factors, for every Boolean function f. It directly answers the second open question posed by Nisan and Szegedy in 1994. They achieve this with a direct proof that stays within the standard algebraic definitions over the reals. No extra conditions on the function class or the field are introduced, and the argument builds from the original formulation without circularity or fitted parameters. This is genuinely new because no polynomial relation of any kind was known before. The paper does a good job of stating the result clearly in the abstract and focusing on the exact bound needed. The stress-test note confirms there are no visible inconsistencies in the high-level construction. The soft spots are mostly around verification. Since the full manuscript details aren't fully expanded here, I can't inspect the individual lemmas or the exact way the cubic bound is derived. That leaves some uncertainty about whether the proof is tight or if there are any overlooked edge cases in the Boolean function setting. The bound itself is polynomial, which is sufficient to resolve the open problem, but the specific exponent of three could perhaps be improved with more work. This paper is for anyone working in Boolean function analysis, circuit complexity, or related areas like quantum query complexity. Readers who use degree or rational degree in their arguments will find the relation useful for translating results between the two measures. It deserves serious peer review because the claim is important and the approach looks grounded. Even if revisions are needed after checking the details, the core contribution is worth referee time. I recommend putting it through peer review.

Referee Report

0 major / 2 minor

Summary. The paper proves that deg(f) ≤ Õ(rdeg(f)^3) for every Boolean function f, where deg(f) is the (real) polynomial degree and rdeg(f) is the rational degree. This resolves the second of the three open problems posed by Nisan and Szegedy in 1994, using the standard algebraic definitions over the reals without additional restrictions on f or the field.

Significance. If the proof holds, the result is significant: it establishes a polynomial relationship between two independently defined complexity measures for Boolean functions, closing a 30-year-old question with a direct argument that begins from the 1994 Nisan-Szegedy formulation. The absence of auxiliary restrictions or fitted parameters strengthens the contribution to communication complexity and circuit lower bounds.

minor comments (2)

[Abstract] The abstract states the bound cleanly but does not indicate the high-level proof strategy (e.g., whether it proceeds via approximate degree or via direct rational-function manipulation); adding one sentence would improve accessibility.
[Section 1] Notation for the Õ notation and the precise definition of rational degree (numerator/denominator degrees) should be restated once in the main body before the first theorem, even if standard.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report and the recommendation to accept the manuscript. We appreciate the recognition that the result resolves the second open problem from Nisan and Szegedy (1994) using the standard definitions.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes deg(f) ≤ Õ(rdeg(f)^3) via a direct proof from the standard real-valued definitions of polynomial degree and rational degree (Nisan-Szegedy 1994 formulation). No step reduces by construction to a fitted parameter, self-definition, or load-bearing self-citation chain; the central inequality is between two independently defined quantities and resolves an external open problem without internal reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard definitions of degree and rational degree from prior literature; no new free parameters or invented entities are introduced in the abstract.

axioms (1)

domain assumption Standard definitions of polynomial degree and rational degree for Boolean functions over the reals
Invoked implicitly as the objects of the inequality; taken from Nisan-Szegedy 1994 and related works.

pith-pipeline@v0.9.0 · 5369 in / 1057 out tokens · 24904 ms · 2026-05-16T14:36:36.686554+00:00 · methodology

Rational degree is polynomially related to degree

Core claim

What carries the argument

If this is right

Where Pith is reading between the lines

Load-bearing premise

What would settle it

discussion (0)