



01560nas a2200181   4500008004100000245006500041210005800106260001500164520103400179100001701213700002101230700002201251700002301273700002001296700001801316700002301334856002101357       2023                        eng d00aOn the Rational Degree of Boolean Functions and Applications0 aRational Degree of Boolean Functions and Applications  c10/12/20233 a<p>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)&minus;&minus;&minus;&minus;&minus;&radic;. 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&minus;O(n&minus;&minus;&radic;).<br />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.</p>1 aIyer, Vishnu1 aJain, Siddhartha1 aKovacs-Deak, Matt1 aKumar, Vinayak, M.1 aSchaeffer, Luke1 aWang, Daochen1 aWhitmeyer, Michael  uarXiv:2310.08004