# On Bilinear Complexity

 Computer Science/Discrete Mathematics Seminar I Topic: On Bilinear Complexity Speaker: Pavel Hrubes Affiliation: University of Washington Date: Monday, January 14 Time/Room: 11:15am - 12:15pm/S-101 Video Link: https://video.ias.edu/1213/csdm/PavelHrubes-0114

For a set of polynomials F, we define their bilinear complexity as the smallest k so that F lies in an ideal generated by k bilinear polynomials. The main open problem is to estimate the bilinear complexity of the single polynomial $\sum_{i,j}x_i^2 y_j^2$. This question is related to the classical sum-of-squares problem as well as to problems in arithmetic circuit complexity. We will focus on related sets of polynomials and prove some lower and upper bounds on their bilinear complexity.