Arithmetic complexity and the sum of squares problem (II)
Seminar Room 1, Newton Institute
AbstractThis 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.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.