EUVIMEDEUVIMED entdecken
Crossref

A Subquadratic Upper Bound on Hurwitz’s Problem and Related Noncommutative Polynomials

Pavel Hrubeš

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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