Arithmetic complexity and the sum of squares problem (II)
Seminar Room 1, Newton Institute
This lecture will be largely independent from the first.
I will explain the completeness of the determinant and permanent in respective classes of polynomials, and its importance to the P vs. NP problem.
I will discuss the non commutative versions of their complexity, and show how these relate to the famous sum-of-squares problem. Then I'll mention some recent small progress on that problem and some of its variants.