تقرير
On the Rational Degree of Boolean Functions and Applications
| العنوان: | On the Rational Degree of Boolean Functions and Applications |
|---|---|
| المؤلفون: | Iyer, Vishnu, Jain, Siddhartha, Kovacs-Deak, Matt, Kumar, Vinayak M., Schaeffer, Luke, Wang, Daochen, Whitmeyer, Michael |
| سنة النشر: | 2023 |
| المجموعة: | Computer Science Quantum Physics |
| مصطلحات موضوعية: | Computer Science - Computational Complexity, Quantum Physics |
| الوصف: | 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 monotone functions have rational degree at least $\sqrt{\mathrm{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 $\Omega(\mathrm{deg}(f)^{1/d})$. Furthermore, we show that almost every Boolean function on $n$ variables has rational degree at least $n/2 - O(\sqrt{n})$. In contrast to total functions, 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. Comment: 17 pages, 3 figures |
| نوع الوثيقة: | Working Paper |
| URL الوصول: | http://arxiv.org/abs/2310.08004 |
| رقم الأكسشن: | edsarx.2310.08004 |
| قاعدة البيانات: | arXiv |
| الوصف غير متاح. |