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.