DAN

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.