On the Rational Degree of Boolean Functions and Applications

Vishnu Iyer, Siddhartha Jain, Robin Kothari +5

We study a natural complexity measure of Boolean functions known as the rational degree. Denoted $\text{rdeg}(f)$, it is the minimal degree of a rational function that is equal t…