On the Rational Degree of Boolean Functions and Applications
Abstract
We study a natural complexity measure of Boolean functions known as the (exact) rational
degree. For total functions f, it is conjectured that rdeg (f) is polynomially related to deg (f),
where deg (f) is the Fourier degree. Towards this conjecture, we show that symmetric functions
have rational degree at least deg (f)/2 and monotone functions have rational degree at least deg(f). We observe that both of these lower bounds are tight. In addition, we show that all
read-once depth-d Boolean formulae have rational degree at least Ω( deg (f )^1/d). Furthermore, we show that almost every Boolean function on n variables has rational degree at least n/2 − O(√n).
In contrast to total functions, we exhibit partial functions that witness unbounded separations
between rational and approximate degree, in both directions. As a consequence, we show that
for quantum computers, post-selection and bounded-error are incomparable resources in the
black-box model.
degree. For total functions f, it is conjectured that rdeg (f) is polynomially related to deg (f),
where deg (f) is the Fourier degree. Towards this conjecture, we show that symmetric functions
have rational degree at least deg (f)/2 and monotone functions have rational degree at least deg(f). We observe that both of these lower bounds are tight. In addition, we show that all
read-once depth-d Boolean formulae have rational degree at least Ω( deg (f )^1/d). Furthermore, we show that almost every Boolean function on n variables has rational degree at least n/2 − O(√n).
In contrast to total functions, we exhibit partial functions that witness unbounded separations
between rational and approximate degree, in both directions. As a consequence, we show that
for quantum computers, post-selection and bounded-error are incomparable resources in the
black-box model.
