Lecture Series on Geometric Complexity Theory, March 14-18, 2016
Jesko Hüttenhain from TU Berlin will give an introduction to the field of geometric/algebraic complexity theory, an approach to solve problems in theoretical computer science by studying actions of linear groups on algebraic varieties.
| What |
|
|---|---|
| When |
Mar 14, 2016 10:00 AM
to Mar 18, 2016 12:00 PM |
| Where | SR 404, Eckerstr. 1 |
| Contact Name | Konrad Voelkel |
| Add event to calendar |
vCal
iCal
|
Each day of the week, we have a talk in SR 404 on 10:15 -- 11:45.
The first talk, on Monday, will be an introduction aimed at a broad audience.
The topics covered in the 5 talks are
- Algebraic Complexity Theory
- Actions and Representation Theory of Affine Reductive Groups
- Geometric Complexity Theory
- The Boundary of Orbit Closures of Homogeneous Forms
Algebraic Complexity Theory
Complexity theory studies how fast computational problems can be solved.
In algebraic complexity theory, the study is limited to the problem of
evaluating polynomials and the complexity is measured by counting
arithmetic operations. We give an introduction that leads up to the
central "Determinant versus Permanent" problem, which can be seen as an
algebraic analogue of P versus NP.
Actions and Representation Theory of Affine Reductive Groups
We will recall several classical results about actions of algebraic
groups on varieties and the representation theory of reductive groups.
We restrict ourselves to the case of an algebraically closed field of
characteristic zero, because the theory is most tame in this case.
Geometric Complexity Theory
The GCT program rephrases rephrases the Determinant versus Permanent
problem as a geometric question: To a homogeneous polynomial of degree
d, we associate its orbit under linear substitution of the variables and
take the closure of this orbit in the space of all homogeneous d-forms.
For certain d-forms (i.e. the determinant and the permanent) the
question becomes whether one such orbit closure is contained in the
other. We focus on how the representation theory of the general linear
group might help to answer this question. For the most part, however, we
present problems and questions that are still open.
The Boundary of Orbit Closures of Homogeneous Forms
Arguably, the boundary of an orbit closure (i.e. the complement of the
orbit in its closure) presents the greatest challenge in understanding
its geometry. This boundary is always a divisor of the orbit closure and
a modest goal is to determine its number of irreducible components. We
present an approach to this problem using geometric invariant theory
which led to some recent work characterizing the boundary of the 3 by 3
determinant. We explain the problems that arise already in the 4 by 4
case and hope for fruitful comments from the audience.