Rational degree is polynomially related to degree
Abstract
We prove that deg(f) = O~(rdeg(f)) 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.
Research Areas
