Constant-Depth Arithmetic Circuits for Linear Algebra Problems
SIAM Journal on Computing · 31.10.2026 · 55 (5) · FOCS24-236-FOCS24-295
DOI: 10.1137/24m1708085 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 26.01.2026. Verfasst von Robert Andrews und 1 weiteren Autor:innen. Die Arbeit nennt 43 Literaturangaben. Gefördert von: Erin Ellentuck Endowed Fellowship Fund, National Science Foundation.
Abstract (Originalsprache)
We design polynomial-size, constant-depth (namely, [Formula: see text]) arithmetic formulae for the greatest common divisor (GCD) of two polynomials as well as the related problems of the discriminant, resultant, and Bézout coefficients; squarefree decomposition; and the inversion of structured matrices, such as Sylvester and Bézout matrices. Our GCD algorithm extends to any number of polynomials. Previously, the best-known arithmetic formulae for these problems required superpolynomial size regardless of depth. These results are based on new algorithmic techniques to compute various symmetric functions in the roots of polynomials and to manipulate the multiplicities of these roots without having access to them. These techniques allow [Formula: see text] computation of a large class of linear and polynomial algebra problems, which include the above as special cases. We extend these techniques to problems whose inputs are multivariate polynomials, which are represented by constant-depth arithmetic circuits. Here, too, we solve problems such as computing the GCD and squarefree decomposition in [Formula: see text].
Förderung
- Erin Ellentuck Endowed Fellowship Fund
- National Science Foundation
Zitieren
APA
Andrews, R., & Wigderson, A. (2026). Constant-Depth Arithmetic Circuits for Linear Algebra Problems. SIAM Journal on Computing, 55(5), FOCS24-236-FOCS24-295. https://doi.org/10.1137/24m1708085
Vancouver
Andrews R, Wigderson A. Constant-Depth Arithmetic Circuits for Linear Algebra Problems. SIAM Journal on Computing. 2026;55(5):FOCS24-236-FOCS24-295. doi:10.1137/24m1708085
BibTeX
@article{Andrews2026,
author = {Andrews, Robert and Wigderson, Avi},
title = {Constant-Depth Arithmetic Circuits for Linear Algebra Problems},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {5},
pages = {FOCS24--236--FOCS24--295},
doi = {10.1137/24m1708085}
}
EUVIMED