Speaker: 

Umut Isik

Institution: 

UCI

Time: 

Monday, March 2, 2015 - 3:00pm

Host: 

Location: 

RH 306

Algebraic complexity theory is the study of the computational difficulty of infinite families of polynomials -- a generalization of the computational complexity of decision problems. In this theory, there are analogues of the usual complexity classes P and NP, as well as different NP-complete problems. The main aim is to find complexity lower bounds for certain specific families, such as the families for matrix multiplication and the permanent family. There are different approaches using algebraic geometry and representation theory to attack such lower bound problems. This talk will be a brief introduction to this area and its central problems.