analiza aiqbench
This paper establishes a polynomial relationship between the degree and rational degree of Boolean functions, resolving a long-standing open problem from 1994 regarding query complexity lower bounds. The result has direct implications for understanding the theoretical limits of quantum algorithms and classical communication complexity, where these degree measures often serve as proxies for computational difficulty. By closing this specific gap in complexity theory, the work advances our fundamental understanding of what problems are efficiently solvable within quantum frameworks.
Rational degree is polynomially related to degree
arXiv:2601.08727v3 Announce Type: replace-cross Abstract: 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.
Abstract: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.
Computational Complexity (cs.CC); Discrete Mathematics (cs.DM); Quantum Physics (quant-ph)
arXiv:2601.08727 [cs.CC]
(or arXiv:2601.08727v3 [cs.CC] for this version)
https://doi.org/10.48550/arXiv.2601.08727 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Text integral sub licența deschisă a publicației · 144 cuvinte
Subiecte conexe
Researchers Find New Invariants for Complex Hamiltonian Systems
Quantum Zeitgeist · 4 oct. 2026
Lattice-Based Cryptography Explained
Quantum Zeitgeist · 15 aug. 2026
Superintegrability of a resonant ghostly tri-Hamiltonian model: polynomial first integrals and transcendental completion
arXiv · 2 oct. 2026
Toward a Kantian refutation of Agent Foundations
LessWrong · 17 iun. 2026