[Colloq] K V Subrahmanyam TOMORROW

[Patricia Freeman]

CCIS Colloquium Spring 2008

An introduction to Geometric Complexity Theory

Speaker: K V Subrahmanyam

Date: Friday, April 25, 2008

Talk: 10:00 a.m. - 11:00 a.m., 366 WVH

Abstract

In this talk I will give an introduction to Geometric Complexity theory as an approach to separating computational complexity classes. GCT was first proposed in a series of papers by Ketan Mulmuley and Milind Sohoni in which they showed that the separation of complexity classes is intimately related to a solution of the plethysm problem in representation theory. I will talk about the algorithmic representation theory problems which arise in this approach. I will assume no background, and begin by introducing the important notions of completeness in complexity theory and class varieties defined in GCT. I will illustrate the approach by considering the example of separating the permanent class from the determinant class.

Brief Biography

K V Subrahmanyam completed his PhD in Computer Science from the Tata Institute of Fundamental Sciences, Mumbai in 1994. He has been at the Chennai Mathematical Institute, Chennai since then. His research interests are in Complexity theory, Randomization, Representation theory and Algebraic Geometry.