On the Rational Degree of Boolean Functions and Applications
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913793585446912 |
|---|---|
| author | Iyer, Vishnu Jain, Siddhartha Kothari, Robin Kovacs-Deak, Matt Kumar, Vinayak M. Schaeffer, Luke Wang, Daochen Whitmeyer, Michael |
| author_facet | Iyer, Vishnu Jain, Siddhartha Kothari, Robin Kovacs-Deak, Matt Kumar, Vinayak M. Schaeffer, Luke Wang, Daochen Whitmeyer, Michael |
| contents | We study a natural complexity measure of Boolean functions known as the rational degree. Denoted $\textrm{rdeg}(f)$, it is the minimal degree of a rational function that is equal to $f$ on the Boolean hypercube. For total functions $f$, it is conjectured that $\textrm{rdeg}(f)$ is polynomially related to the Fourier degree of $f$, $\textrm{deg}(f)$. Towards this conjecture, we show that:
- Symmetric functions have rational degree at least $Ω(\textrm{deg}(f))$ and unate functions have rational degree at least $\sqrt{\textrm{deg}(f)}$. We observe that both of these lower bounds are asymptotically tight.
- Read-once AC and TC formulae have rational degree at least $Ω(\sqrt{\textrm{deg}(f)})$. If these formulae contain parity gates, we show a lower bound of $Ω(\textrm{deg}(f)^{1/2d})$, where $d$ is the depth.
- Almost every Boolean function on $n$ variables has rational degree at least $n/2 - O(\sqrt{n})$.
In contrast, 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.
In addition, we show AND and OR composition lemmas for the rational degree and exhibit new polynomial separations between the rational degree and other well-studied complexity measures, such as sensitivity and spectral sensitivity. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_08004 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Rational Degree of Boolean Functions and Applications Iyer, Vishnu Jain, Siddhartha Kothari, Robin Kovacs-Deak, Matt Kumar, Vinayak M. Schaeffer, Luke Wang, Daochen Whitmeyer, Michael Computational Complexity Quantum Physics We study a natural complexity measure of Boolean functions known as the rational degree. Denoted $\textrm{rdeg}(f)$, it is the minimal degree of a rational function that is equal to $f$ on the Boolean hypercube. For total functions $f$, it is conjectured that $\textrm{rdeg}(f)$ is polynomially related to the Fourier degree of $f$, $\textrm{deg}(f)$. Towards this conjecture, we show that: - Symmetric functions have rational degree at least $Ω(\textrm{deg}(f))$ and unate functions have rational degree at least $\sqrt{\textrm{deg}(f)}$. We observe that both of these lower bounds are asymptotically tight. - Read-once AC and TC formulae have rational degree at least $Ω(\sqrt{\textrm{deg}(f)})$. If these formulae contain parity gates, we show a lower bound of $Ω(\textrm{deg}(f)^{1/2d})$, where $d$ is the depth. - Almost every Boolean function on $n$ variables has rational degree at least $n/2 - O(\sqrt{n})$. In contrast, 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. In addition, we show AND and OR composition lemmas for the rational degree and exhibit new polynomial separations between the rational degree and other well-studied complexity measures, such as sensitivity and spectral sensitivity. |
| title | On the Rational Degree of Boolean Functions and Applications |
| topic | Computational Complexity Quantum Physics |
| url | https://arxiv.org/abs/2310.08004 |