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.