Rational degree is polynomially related to degree
The paper establishes a polynomial relationship between the standard degree of a Boolean function, deg(f), and its rational degree, rdeg(f). It proves that for any Boolean function f, deg(f) is bounded by O(rdeg(f)^3), resolving an open problem in quantum query complexity. This result connects algebraic measures of functions to practical bounds on deterministic query algorithms.