EUVIMEDEUVIMED entdecken
Crossref

Constant-Depth Arithmetic Circuits for Linear Algebra Problems

Robert Andrews, Avi Wigderson

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →