All reports by Author Matt Kovacs-Deak:

__
TR23-154
| 12th October 2023
__

Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer#### On the Rational Degree of Boolean Functions and Applications

Vishnu Iyer, Siddhartha Jain, Matt Kovacs-Deak, Vinayak Kumar, Luke Schaeffer, Daochen Wang, Michael Whitmeyer

We study a natural complexity measure of Boolean functions known as the (exact) rational degree. For total functions $f$, it is conjectured that $\mathrm{rdeg}(f)$ is polynomially related to $\mathrm{deg}(f)$, where $\mathrm{deg}(f)$ is the Fourier degree. Towards this conjecture, we show that symmetric functions have rational degree at least $\mathrm{deg}(f)/2$ and ... more >>>