skip to content
 

Arithmetic complexity and the sum of squares problem (II)

Presented by: 
A Wigderson [IAS Princeton]
Date: 
Thursday 7th April 2011 - 15:15 to 16:15
Venue: 
INI Seminar Room 1
Abstract: 
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.
University of Cambridge Research Councils UK
    Clay Mathematics Institute The Leverhulme Trust London Mathematical Society Microsoft Research NM Rothschild and Sons