A Subquadratic Upper Bound on Hurwitz’s Problem and Related Noncommutative Polynomials
SIAM Journal on Computing · 30.04.2026 · 55 (2) · 451-467
DOI: 10.1137/24m1666884 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 30.04.2026. Verfasst von Pavel Hrubeš. Die Arbeit nennt 22 Literaturangaben. Gefördert von: Grantová Agentura České Republiky.
Abstract (Originalsprache)
For every [Formula: see text], we construct a sum-of-squares identity [Formula: see text], where [Formula: see text] are bilinear forms with complex coefficients and [Formula: see text]. Previously, such a construction was known with [Formula: see text]. The same bound holds over any field of positive characteristic. As an application to complexity of noncommutative computation, we show that the polynomial [Formula: see text] in [Formula: see text] noncommuting variables can be computed by a noncommutative arithmetic circuit of size [Formula: see text]. This holds over any field of characteristic different from two. The same bound applies to noncommutative versions of the elementary symmetric polynomial of degree four and the rectangular permanent of a [Formula: see text] matrix.
Förderung
- Grantová Agentura České Republiky
Zitieren
APA
Hrubeš, P. (2026). A Subquadratic Upper Bound on Hurwitz’s Problem and Related Noncommutative Polynomials. SIAM Journal on Computing, 55(2), 451-467. https://doi.org/10.1137/24m1666884
Vancouver
Hrubeš P. A Subquadratic Upper Bound on Hurwitz’s Problem and Related Noncommutative Polynomials. SIAM Journal on Computing. 2026;55(2):451-467. doi:10.1137/24m1666884
BibTeX
@article{Hrube2026,
author = {Hrubeš, Pavel},
title = {A Subquadratic Upper Bound on Hurwitz’s Problem and Related Noncommutative Polynomials},
journal = {SIAM Journal on Computing},
year = {2026},
volume = {55},
number = {2},
pages = {451--467},
doi = {10.1137/24m1666884}
}
EUVIMED