Title | On the Rational Degree of Boolean Functions and Applications |

Publication Type | Journal Article |

Year of Publication | 2023 |

Authors | Iyer, V, Jain, SP, Kovacs-Deak, M, Kumar, VM, Schaeffer, L, Wang, D, Whitmeyer, M |

Date Published | 10/12/2023 |

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−−√). |

URL | arXiv:2310.08004 |