Speaker: | Soham Chatterjee (TIFR) |
Organiser: | Varun Ramanathan |
Date: | Friday, 11 Jul 2025, 16:00 to 17:00 |
Venue: | A-201 (STCS Seminar Room) |
In this talk we will discuss the Hurwitz problem which asks: Given $n$, upper bound the number $s$ such that $\left(\sum_{i=1}^nx_i^2\right)\left(\sum_{i=1}^ny_i^2\right)=\sum_{k=1}^s f_k^2$ where $x_i,y_i$'s are variables and $f_k=\bar{x}^TH_k\bar{y}$, $H_k\in\mathbb{C}^{n\times n}$. There is a trivial upper bound of $s=n^2$ by treating all possible $x_i^2y_j^2$ as bilinear forms. Previously a $O(n^2/\log n)$ upper bound was shown using Hurwitz-Radon theorem. In this paper we will show a better bound of $O(n^{1.62})$. A specific motivation for this problem comes from arithmetic circuit complexity. Wigderson, Yehudayoff and Hrubesh have shown that a superlinear lower bound on $s$ of the form $\Omega(n^{1+\epsilon})$, $\epsilon > 0$, translates to an exponential circuit lower bound in the non-commutative setting for the degree four polynomial $ID_n=\sum_{i,j\in [n]}x_iy_jx_iy_j$.