The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Arithmetic complexity and the sum of squares problem (II)

Wigderson, A (IAS Princeton)
Thursday 07 April 2011, 15:15-16:15

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.


The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧