Rational degree is polynomially related to degree

This paper resolves a longstanding open problem from 1994 by proving that the degree of any Boolean function is polynomially bounded by its rational degree, specifically establishing that $\mathrm{deg}(f) \leq \widetilde{O}(\mathrm{rdeg}(f)^3)$.

The Gist

Imagine you are trying to describe a complex rule for a game, like "Who wins this chess match?" or "Is this email spam?"

In the world of computer science, we often try to describe these rules using mathematical formulas (polynomials). The paper you're asking about solves a decades-old puzzle about how "complicated" these formulas need to be.

Here is the story, broken down into simple concepts and analogies.

1. The Two Ways to Write the Rule

Imagine you have a Boolean function $f$. This is just a fancy name for a rule that takes a list of 0s and 1s (like a string of switches) and outputs a single 0 or 1 (like a light turning on or off).

To understand how "hard" this rule is, mathematicians look at how complex the formula needs to be to describe it. The paper compares two specific ways of writing this formula:

• The "Standard" Formula (Degree):
  Imagine you have to write the rule using a single, giant equation.

  • Analogy: You are trying to describe a mountain range using one single piece of clay. You have to mold the whole shape out of one lump. If the mountain is jagged and complex, you need a huge, complicated lump of clay (a high-degree polynomial).
  • The Measure: The "Degree" is the size of that lump.

• The "Fraction" Formula (Rational Degree):
  Imagine you are allowed to write the rule as a fraction: $\frac{\text{Numerator}}{\text{Denominator}}$.

  • Analogy: Instead of one giant lump of clay, you can use two smaller lumps. You mold one into a shape (the top) and another into a shape (the bottom), and then you divide them.
  • The Measure: The "Rational Degree" is the size of the larger of the two lumps.
  • Why it matters: Sometimes, it's much easier to describe a complex shape by dividing two simple shapes than by molding one giant, twisted shape. For example, describing a curve might be easy if you divide a parabola by a line, but hard if you try to do it with just one polynomial.

2. The Big Question

For over 30 years, computer scientists (specifically Nisan, Szegedy, and Fortnow) asked a simple question:

"If I can describe a rule easily using a fraction (Rational Degree), does that mean I can also describe it easily using a single lump (Standard Degree)?"

Or, in other words: Is the "Fraction" method just a clever shortcut, or does it actually hide a much more complex reality?

If the answer is "Yes," then the two methods are polynomially related. This means if the fraction method takes size $X$, the single lump method will take something like $X^3$ or $X^4$. They grow together.
If the answer is "No," then the fraction method could be tiny while the single lump method is astronomically huge, which would break many of our assumptions about how computers process information.

3. The Solution: The "Magic Bridge"

The authors of this paper (Kothari, Kovacs-Deak, Wang, and Yang) proved that the answer is YES.

They showed that no matter how complex the rule is, if you can describe it with a fraction of size $k$, you can definitely describe it with a single lump of size roughly $k^3$ (or slightly more, but still a manageable power).

The Analogy of the Bridge:
Imagine the "Fraction" method is a sleek, modern bridge across a river. The "Standard" method is a rough, winding dirt path.
For 30 years, people wondered: "Is the dirt path miles longer than the bridge, or is it just a few miles longer?"
This paper builds a bridge between the two. It proves that even if the dirt path is longer, it's not infinitely longer. It's just a few times longer. Specifically, they proved the dirt path is at most the cube of the bridge's length.

4. How Did They Do It? (The Detective Work)

To prove this, they didn't just look at the math formulas directly. They used a clever detective strategy involving three concepts:

1. The "Sensitivity" Detective: They looked at how much the answer changes if you flip just one switch in the input. If a rule is very sensitive (changing one bit flips the result), the formula must be complex.
2. The "Certificate" Detective: They looked for the smallest piece of evidence needed to prove the answer is "Yes" or "No."
3. The "Randomized" Detective: They introduced a new tool called "Randomized Certificate Complexity." Imagine a detective who doesn't check every single clue but picks a random sample. If the sample is good enough, they can guess the answer.

The Strategy:
They showed that:

• The "Fraction" size is linked to how hard it is to find a "Certificate" (evidence).
• The "Standard" size is linked to how many "Sensitive" switches there are.
• By using their new "Randomized" detective tool, they connected the dots. They proved that the "Fraction" size controls the "Certificate" size, which in turn controls the "Standard" size.

5. Why Should You Care?

This isn't just about abstract math; it has real-world implications for Quantum Computing and Cryptography.

• Quantum Computing: The "Fraction" method is actually a measure of how hard a problem is for a specific type of quantum computer (one that can "post-select," or cheat by only looking at the lucky outcomes). This paper proves that if a quantum computer can solve a problem easily using this "cheat," a classical computer (using standard math) can also solve it, just with a bit more effort (cubed). It puts a limit on how much quantum computers can "cheat."
• The "Nullstellensatz" (The Magic Spell): In algebra, there's a famous theorem called the Nullstellensatz. It's like a magic spell that says, "If two things don't overlap, you can combine them to make 1." This paper gives a new, more efficient version of this spell for computer science problems, showing exactly how much "magic power" (degree) is needed.

Summary

• The Problem: Can a complex rule be described simply as a fraction, even if it's impossible to describe simply as a single equation?
• The Answer: No. If it's simple as a fraction, it's also simple as a single equation (just a bit more complex, but not exponentially so).
• The Result: The complexity of the single equation is at most the cube of the complexity of the fraction.
• The Impact: This closes a 30-year-old gap in our understanding of how computers (both classical and quantum) handle information, proving that "fractional" shortcuts aren't magic loopholes that break the laws of complexity.

Technical Summary

1. Problem Statement

The paper addresses a fundamental open problem in Boolean function complexity theory, originally posed by Nisan and Szegedy (attributed to Fortnow) in 1994. The problem concerns the relationship between two complexity measures:

• Degree ($\deg(f)$): The minimum degree of a real polynomial $p$ such that $p(x) = f(x)$ for all $x \in \{0,1\}^n$.
• Rational Degree ($\text{rdeg}(f)$): The minimum value of $\max(\deg(p), \deg(q))$ such that $p, q$ are real polynomials and $f(x) = p(x)/q(x)$ for all $x \in \{0,1\}^n$ (with $q(x) \neq 0$).

While it is trivial that $\text{rdeg}(f) \leq \deg(f)$ (by setting $q=1$), it was unknown whether $\deg(f)$ could be exponentially larger than $\text{rdeg}(f)$. The authors prove that these measures are polynomially related, specifically resolving the conjecture that $\deg(f) \leq \text{poly}(\text{rdeg}(f))$.

2. Methodology

The authors employ a multi-stage proof strategy that bridges algebraic properties of polynomials with combinatorial complexity measures. The methodology evolves from a simpler, weaker bound to a stronger, near-optimal bound.

A. Core Concepts and Tools

• Nondeterministic Degree ($\text{ndeg}(f)$): The minimum degree of a polynomial $p$ such that $p(x) \neq 0 \iff f(x)=1$. The paper utilizes the identity $\text{rdeg}(f) = \max(\text{ndeg}(f), \text{ndeg}(\neg f))$.
• Block Sensitivity ($bs_x(f)$) and Certificate Complexity ($C_x(f)$): Combinatorial measures describing how sensitive a function is to bit flips or how many bits determine the output.
• Fractional Block Sensitivity ($fbs_x(f)$) and Randomized Certificate Complexity ($RC_x(f)$): The authors leverage linear programming duality, noting that $fbs_x(f)$ and $RC_x(f)$ are $\Theta$-equivalent. This allows them to move from integer constraints to fractional relaxations, which are easier to bound analytically.
• Potential Functions: To bound the number of queries in a deterministic decision tree, the authors construct a potential function $\Phi(r)$ based on the maximal monomials of a nondeterministic polynomial representation. This function decreases geometrically with each query step.

B. Proof Structure

The proof proceeds in two main phases:

Phase 1: A Simpler Quadratic Bound (Section 3)
The authors first establish a weaker bound: $\deg(f) \leq O(\text{rdeg}(f)^4)$.

1. They relate the minimum block sensitivity ($\min_x bs_x(f)$) to the sign degree ($\deg_\pm(f)$) using Markov's inequality and polynomial symmetrization.
2. They show that a nondeterministic polynomial has a "hitting set" of size proportional to $\deg(p) \cdot \min bs_x(f)$.
3. By constructing a decision tree that queries these hitting sets, they bound the decision tree complexity $D(f)$, and consequently $\deg(f)$, in terms of $\text{rdeg}(f)$.

Phase 2: The Improved Cubic Bound (Section 4)
To achieve the stronger result, the authors refine the strategy using "best-case" complexity measures and fractional relaxations:

1. Step 1 (Algorithmic Upper Bound): They upgrade the relationship between Decision Tree Complexity ($D(f)$) and Certificate Complexity. Instead of using standard certificate complexity, they use Randomized Certificate Complexity ($RC_{\min}^\downarrow(f)$), which is the minimum expected queries of a randomized verifier over all restrictions. They prove $D(f) \leq O(\text{rdeg}(f) \cdot RC_{\min}^\downarrow(f) \log n)$.
2. Step 2 (Duality): Using linear programming duality, they relate $RC_{\min}^\downarrow(f)$ to Fractional Block Sensitivity ($fbs_{\min}^\downarrow(f)$).
3. Step 3 (Analytic Lower Bound): They prove a new lower bound relating $fbs_{\min}^\downarrow(f)$ to the sign degree $\deg_\pm(f)$. This involves constructing a specific polynomial using Chebyshev polynomials to simulate partial-OR functions, showing $fbs_{\min}^\downarrow(f) \leq O(\deg_\pm(f)^2)$.
4. Synthesis: Combining these steps yields $D(f) \leq O(\text{rdeg}(f)^3 \log n)$. By restricting the function to a subcube of size $\deg(f)$, they remove the $\log n$ factor relative to the degree, resulting in the final bound.

3. Key Contributions and Results

Main Theorem

For every Boolean function $f$:
$$\deg(f) \leq \tilde{O}(\text{rdeg}(f)^3)$$
More precisely, they prove:
$$\deg(f) \leq O(\text{rdeg}(f) \cdot \deg_\pm(f)^2 \cdot \log(\text{rdeg}(f)))$$
Since $\deg_\pm(f) \leq 2\text{rdeg}(f)$, this implies the cubic relationship.

Secondary Results

1. Decision Tree Complexity: They prove $D(f) \leq O(\text{rdeg}(f)^3 \log n)$.
2. Effective Hypercube Nullstellensatz: The result is framed as an effective Nullstellensatz for the hypercube. If two polynomials $g_1, g_2$ have no common zeros on $\{0,1\}^n$ and their product is zero everywhere on the hypercube, there exist $h_1, h_2$ such that $h_1 g_1 + h_2 g_2 = 1$ with degrees bounded by $\tilde{O}(\deg(g_1)^{1.5} \deg(g_2)^{1.5})$.
3. Lower Bound on Rational Degree: They prove that for any function depending on $n$ variables, $\text{rdeg}(f) \geq \Omega(\log n)$. This implies that rational degree cannot be constant for functions depending on many variables.
4. Relations to Other Measures: The paper establishes polynomial relations between rational degree and other measures like sensitivity ($s(f)$) and nondeterministic degree ($\text{ndeg}$).

4. Significance

• Resolution of a 30-Year Open Problem: The paper definitively answers the question posed by Nisan, Szegedy, and Fortnow, confirming that rational degree and polynomial degree are polynomially related. This closes a major gap in the hierarchy of Boolean complexity measures.
• Quantum Complexity Implications: Rational degree characterizes exact postselected quantum query complexity ($PostQ_0$). The result implies that exact postselected quantum query complexity is polynomially related to deterministic query complexity ($D(f)$) and standard polynomial degree.
• New Techniques: The introduction of fractional block sensitivity and randomized certificate complexity as intermediate tools to bridge combinatorial and algebraic bounds provides a powerful new toolkit for complexity theory. The use of potential functions to analyze decision tree depth via polynomial restrictions is also a novel contribution.
• Optimality: The authors conjecture that the cubic bound is optimal (up to logarithmic factors), suggesting that the separation between rational degree and degree is at most cubic, which is a tight constraint compared to the previously unknown exponential gap.

In summary, this work unifies algebraic and combinatorial perspectives on Boolean functions, proving that the ability to represent a function as a ratio of polynomials (rational degree) does not offer an exponential advantage over representing it as a single polynomial (degree).