• Calendar

December 30, Wednesday
11:00 – 12:00

We will discuss complexity in worlds with a weak algebraic structure. We will start with a brief introduction to algebraic complexity, and explain Valiant's definitions of the algebraic analogs of P and NP. We will then explore these notions in weak algebraic structures which are not necessarily commutative or even associative. It turns out that even in such a world, permanent is NP-complete. We also consider hardness in these weak computational worlds: First, we show that the non-commutative complexity of permanent is related to the classical sum-of-squares problem. We also show that in a non-associative world, NP is strictly stronger than P. Joint work with Pavel Hrubes and Avi Wigderson.