### 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

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

#### Video

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

## Comments

Start the discussion!