Metraipolis › archive › dc_8f2286ff2ad5
PIT and Reconstruction for Sums of Powers — arXiv:2611.07106
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.07106
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-06T14:54:30.690Z
- SHA-256 of the archived text
718fcb66ff65327fce62d41b32294a419b39d228c498ea56e957018927f46487- Stable URL of this page
https://metraipolis.com/documento/dc_8f2286ff2ad5
How to cite
PIT and Reconstruction for Sums of Powers — arXiv:2611.07106 — arXiv (en), https://arxiv.org/abs/2611.07106 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8f2286ff2ad5 (Metraipolis archive dc_8f2286ff2ad5, sha256 718fcb66ff65327fce62d41b32294a419b39d228c498ea56e957018927f46487)
BibTeX
@misc{dc8f2286ff2ad5,
title = {PIT and Reconstruction for Sums of Powers — arXiv:2611.07106},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.07106},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8f2286ff2ad5; sha256 718fcb66ff65327fce62d41b32294a419b39d228c498ea56e957018927f46487},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.07106. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study deterministic black-box polynomial identity testing (PIT) and reconstruction for polynomials of the form \[ f(x)=\sum_{i=1}^r \alpha_i f_i(x)^d, \] where each $f_i$ belongs to some underlying polynomial class $\mathcal{C}$. This representation generalizes Waring decomposition, several natural small-depth circuit models, and polynomial decompositions arising in moment-based learning problems. Our main results are three lifting theorems showing that, when the outer power is sufficiently large, PIT and reconstruction for the inner class can be lifted to sums of powers. When the power degree is small, we can perform these tasks directly in some of the cases using closure properties of the underlying models. In particular we obtain the following results: \begin{itemize} \item When the inner polynomials have bounded-individual-degrees and are sparse, we obtain deterministic reconstruction for every d: the original power-sum decomposition is recovered at high degree, while at low degree the polynomial is reconstructed nonproperly by sparse interpolation. \item For sums of powers of same-order and any-order read-once oblivious algebraic branching programs, the same proper/nonproper dichotomy gives deterministic reconstruction for every powering degree. \item Explicit quasipolynomial-size hitting sets for every powering degree for several depth-5 and depth-6 circuit families, as well for the models mentioned above. Our results for high powering degree rely on the polynomial ABC theorem, which to the best of our knowledge is the first application of this theorem in the context of PIT.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.07106 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-06T14:27:27.632Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).