BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1586
DTSTAMP:20250901T061028Z
SUMMARY:$n^{1.62}$ upper bound of the Hurwitz Problem
DESCRIPTION:Speaker: Soham Chatterjee (TIFR)\n\nAbstract: \nIn 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 b
 ilinear forms. Previously a $O(n^2/\\log n)$ upper bound was shown using H
 urwitz-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 circu
 it complexity. Wigderson\, Yehudayoff and Hrubesh have shown that a superl
 inear lower bound on $s$ of the form $\\Omega(n^{1+\\epsilon})$\, $\\epsil
 on > 0$\, translates to an exponential circuit lower bound in the non-comm
 utative setting for the degree four polynomial $ID_n=\\sum_{i\,j\\in [n]}x
 _iy_jx_iy_j$.\n
URL:https://www.tcs.tifr.res.in/web/events/1586
DTSTART;TZID=Asia/Kolkata:20250711T160000
DTEND;TZID=Asia/Kolkata:20250711T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR