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