Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-026 | 15th May 2024 17:12

A subquadratic upper bound on sum-of-squares composition formulas

RSS-Feed




Revision #1
Authors: Pavel Hrubes
Accepted on: 15th May 2024 17:12
Downloads: 175
Keywords: 


Abstract:

For every $n$, we construct a sum-of-squares identitity
\[ (\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.


Paper:

TR24-026 | 15th February 2024 12:47

A subquadratic upper bound on sum-of-squares compostion formulas





TR24-026
Authors: Pavel Hrubes
Publication: 15th February 2024 14:10
Downloads: 436
Keywords: 


Abstract:

For every $n$, we construct a sum-of-squares identitity
\[ (\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.



ISSN 1433-8092 | Imprint