[Colloquium] Grochow/Dissertation Defense/Apr 17, 2012

[Margaret Jaffey]

       Department of Computer Science/The University of Chicago

                     *** Dissertation Defense ***


Candidate:  Joshua Grochow

Date:  Tuesday, April 17, 2012

Time:  10:00 AM

Place:  Ryerson 251

Title: Symmetry and equivalence relations in classical and geometry
complexity theory

Abstract:
This thesis studies some of the ways in which symmetries and
equivalence relations arise in classical and Geometric complexity
theory. The Geometric Complexity Theory program is aimed at resolving
central questions in complexity such as P versus NP using techniques
from algebraic geometry and representation theory. The equivalence
relations we study are mostly algebraic in nature and we heavily use
algebraic techniques to reason about the computational properties of
these problems. We first provide a primer on Geometric Complexity
Theory, to provide perspective and motivate the other problems we
study.

We give improved algorithms to test matrix isomorphism of matrix Lie
algebras, which is a problem that arises naturally in Geometric
Complexity Theory. For certain cases of matrix isomorphism of Lie
algebras we provide polynomial-time algorithms, and for other cases we
show that the problem is as hard as graph isomorphism. To our
knowledge, this is the first time graph isomorphism has appeared in
connection with any lower bounds program.

Finally, we study algorithms for equivalence relations more generally
(joint work with Lance Fortnow). Two techniques are often employed for
algorithmically deciding equivalence relations: 1) finding a complete
set of easily computable invariants, or 2) finding an algorithm which
will compute a canonical form for each equivalence class. Some
equivalence relations in the literature have been solved efficiently
by other means as well. We ask whether these three conditions---having
an efficient solution, having an efficiently computable complete
invariant, and having an efficiently computable canonical form---are
equivalent. We show that this question requires non-relativizing
techniques to resolve, and provide new connections between this
question and factoring integers, probabilistic algorithms, and quantum
computation.

Joshua's advisors are Prof. Lance Fortnow and Prof. Ketan Mulmuley

Login to the Computer Science Department website for details,
including a draft copy of the dissertation:

 https://www.cs.uchicago.edu/phd/phd_announcements#joshuag

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=