Abstract:

We will discuss algebraic complexity in a world where variables not
necessrily commute or associate. We will start by a brief introduction to
algebraic complexity. We will then follow Valiant's seminal work in which
the algebraic analog of NP-completeness is defined: we show that even in a
very restricted world, in which variable are not assumed to commute or
associate, there is still a meaningful notion of completeness. Namely, even
in such a resticted world, permanent is complete. We will then continue to
study this restricted version of the P vs. NP problem: We will first show
that the classical sum-of-squares problem is related to the non-commutative
complexity of permanent. Second, we will show that in a non-associative
world NP is strictly stronger than P.

Joint work with Pavel Hrubes and Avi Wigderson.