Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!

aqora_bot

Posted 7mo ago

Rational degree is polynomially related to degree

External link

Matt Kovacs-Deak, Daochen Wang, Rain Zimin Yang (Jan 14 2026).

Abstract: We prove that

\mathrm{deg}(f) \leq 2 \, \mathrm{rdeg}(f)^4

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.

Arxiv: https://arxiv.org/abs/2601.08727

Order by:

Want to join this discussion?

Join our community today and start discussing with our members by participating in exciting events, competitions, and challenges. Sign up now to engage with quantum experts!