Rational degree is polynomially related to degree
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915922931875840 |
|---|---|
| author | Kothari, Robin Kovacs-Deak, Matt Wang, Daochen Yang, Rain Zimin |
| author_facet | Kothari, Robin Kovacs-Deak, Matt Wang, Daochen Yang, Rain Zimin |
| contents | We prove that $\mathrm{deg}(f) \leq \widetilde{O}(\mathrm{rdeg}(f)^3)$ for every Boolean function $f$, where $\mathrm{deg}(f)$ is the degree of $f$ and $\mathrm{rdeg}(f)$ is the rational degree of $f$. This resolves the second of the three open problems stated by Nisan and Szegedy, and attributed to Fortnow, in 1994. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_08727 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Rational degree is polynomially related to degree Kothari, Robin Kovacs-Deak, Matt Wang, Daochen Yang, Rain Zimin Computational Complexity Discrete Mathematics Quantum Physics We prove that $\mathrm{deg}(f) \leq \widetilde{O}(\mathrm{rdeg}(f)^3)$ for every Boolean function $f$, where $\mathrm{deg}(f)$ is the degree of $f$ and $\mathrm{rdeg}(f)$ is the rational degree of $f$. This resolves the second of the three open problems stated by Nisan and Szegedy, and attributed to Fortnow, in 1994. |
| title | Rational degree is polynomially related to degree |
| topic | Computational Complexity Discrete Mathematics Quantum Physics |
| url | https://arxiv.org/abs/2601.08727 |