Home   •   Algebraic Complexity Meeting

Algebraic Complexity Meeting

ENS Lyon, June 24-25, 2015

The complexity of an algorithm is the number of basic operations performed on inputs of size n. In algebraic complexity the basic operations are addition and multiplication, instead of boolean operations in the more standard models. Arithmetic circuits provide a natural model of computation for this algebraic setting; they play the same role as boolean circuits in boolean complexity.

The two main open problems in algebraic complexity are:

  • The complexity of the permanent polynomial: can the permanent of a generic n by n matrix be computed in a number of arithmetic operations which is polynomially  bounded in n? Following Valiant, this problem can be viewed as an algebraic version of the P versus NP problem. It is usually known under the name “VP versus VNP”.
  • The complexity of matrix multiplication: since Strassen’s groundbreaking work in the 1960’s, increasingly faster matrix multiplication algorithms were discovered, but it is not clear how much progress is still possible.

While these outstanding problems have been open for decades, significant progress was made in the last few years.

For instance the new lower bounds for arithmetic circuit of small depth come tantalizingly close to separating VP from VNP, and Mulmuley’s Geometric Complexity Theory program is an ongoing attempt to achieve this separation using tools of algebraic geometry and representation theory.

In the last 5 years, new algorithms for matrix multiplication were discovered, improving slightly on the longstanding record by Coppersmith and Winograd from the 1980’s.

It was recently shown that current methods will only yield negligible improvement on the state of the art.
Some progress was also made on the lower bound front: a new lower bound on the “border rank” of matrix multiplication (a standard measure of its complexity) was obtained, improving by a constant factor a result of Lickteig’s (1985).

Goal: This meeting will provide an introduction to algebraic complexity and present some of the recent results with an emphasis on geometric methods.

Audience: The meeting should be of interest to researchers in theoretical computer science and mathematics. An introduction to the relevant mathematical tools from algebraic geometry, representation theory and multilinear algebra will be provided.

Speakers (preliminary list):
Markus Bläser (Saarbrücken).
Guillaume Lagarde (Paris 7).
Joseph Landsberg (Texas A&M).
Laurent Manivel (Institut de Mathématiques de Marseille).
Sylvain Perifel (Paris 7).
Nicolas Ressayre (Lyon 1).


Place: amphitheater I, Ecole Normale Supérieure de Lyon, Monod campus (map).

  • Amphitheater I is on the ground floor of the main building, on the north side of allée d'Italie.
  • The welcome desk of ENS Lyon is on the south side (on your left if you walked from métro Debourg).
  • From the welcome desk, take the elevators or the stairs to the lower level. Walk north underneath allée d'Italie, take the stairs right in front of you to reach the ground floor. Amphi I will be in front of you, behind the green plants and the TV screen.

To attend: Participation is free of charge, but if you would like to attend please send an email to pascal.koiran@ens-lyon.fr before June 16.

Schedule
June 24th:
10:30 am - 11:20 am Permanent versus determinant 1 (Ressayre)
11:30 am lunch
1 pm - 1:50 pm Introduction to representation theory 1 (Manivel)
2 pm - 2:50 pm Complexity of matrix multiplication 1 (Landsberg)
2:50 pm coffee break
3:20 pm - 4:10  Tensors of minimal border rank (Bläser)

June 25th:
9:30 am - 10:20 am Introduction to representation theory 2 (Manivel)
10:20 am - 10:50 am coffee break
10:50 am - 11:40 am Complexity of matrix multiplication 2 (Landsberg)
11:50 am lunch
1:20 pm - 2:10  Permanent versus determinant 2 (Ressayre)
2:20 pm  - 2:50 pm The problem of computing the degree (Lagarde - Perifel)
Abstract: Computing the degree of a polynomial given by an arithmetic circuit is a basic algorithmic problem. Nevertheless, it is not well understood: the gap between the best upper (coRP^PP) and lower bound (P-hard for logspace reduction) is huge. In this talk, after a general presentation, we will focus on the simplest circuits for which we don't know a better algorithm than coRP^PP - namely the depth 3 circuits. It is not clear how to improve the upper bound in the general case, but we can still hope for improvements in this restricted case.
2:50 pm coffee break
3:20 pm - 4:10 pm Isotypic components in coordinate rings of orbit closures (Ikenmeyer)
Abstract: Representation theory plays a central role in Mulmuley and Sohoni's geometric complexity theory program for finding equations vanishing on specific orbit closures. In this talk we discuss results and challenges in understanding the representation theoretic multiplicities involved. The challenges are similar in the determinant vs permanent problem and in the tensor rank problem.


This meeting is organized by Project CompA.

Published on