ECCC-Report TR24-099https://eccc.weizmann.ac.il/report/2024/099Comments and Revisions published for TR24-099en-usWed, 05 Jun 2024 16:40:23 +0300
Paper TR24-099
| A subquadratic upper bound on Hurwitz's problem and related non-commutative polynomials |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2024/099For every $n$, we construct a sum-of-squares identity
$ (\sum_{i=1}^n x_i^2) (\sum_{j=1}^n y_j^2)= \sum_{k=1}^s f_k^2$,
where $f_k$ are bilinear forms with complex coefficients and $s= O(n^{1.62})$. Previously, such a construction was known with $s=O(n^2/\log n)$.
The same bound holds over any field of positive characteristic.
As an application to complexity of non-commutative computation, we show that the polynomial $ID_n=\sum_{i,j\in [n]}x_iy_jx_iy_j$ in $2n$ non-commuting variables can be computed by a non-commutative arithmetic circuit of size $O(n^{1.96})$. This holds over any field of characteristic different from two. The same bound applies to non-commutative versions of the elementary symmetric polynomial of degree four and the rectangular permanent of a $4\times n$ matrix.Wed, 05 Jun 2024 16:40:23 +0300https://eccc.weizmann.ac.il/report/2024/099