| 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 |
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.