Fall 2014

Families of Anticommuting Matrices and the Sum of Squares Problem

Wednesday, October 15th, 2014 4:00 pm4:25 pm

Add to Calendar


Pavel Hrubeš, Academy of Sciences of the Czech Republic


Calvin Lab Auditorium

In the sum of squares problem, we want to express the polynomial (x_1^2+…+x_n^2)(y_1^2+…+y_n^2) as f_1^2+…+f_k^2, with f_i bilinear in x and y. k lies somewhere between n and n^2, and it is an open problem to prove a superlunar lower bound on k. A lower bound of n^{1+\eps} with \eps>0 would imply an exponential lower bound on arithmetic circuit complexity of the permanent, in the non-commutative setting. I will describe an approach to the sum of squares problem, based on families of anticommuting matrices. Essentially, one needs to show that it is impossible to have many pairwise anticommuting matrices with high rank. I will prove some partial results in this direction.