On Polynomial Approximations to ${AC}^0$
We make progress on some questions related to polynomial approximations of ${\rm AC}^0$. It is known, by works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. $6$th CCC, 1991), that any ${\rm AC}^0$ circuit of size $s$ and depth $d$ has an $\varepsilon$-error probabil...
Guardat en:
| Autors principals: | , |
|---|---|
| Format: | Article |
| Publicat: |
2016
|
| Matèries: | |
| Accés en línia: | https://arxiv.org/abs/1604.08121 http://arxiv.org/abs/1604.08121 |
| Etiquetes: |
Sense etiquetes, Sigues el primer a etiquetar aquest registre!
|