Invariant theory is concerned with the ring of polynomial functions that are left unchanged under the linear coordinate changes given by a group of invertible matrices. Hilbert showed in 1890 that this invariant ring is finitely generated for many matrix groups, including finite groups and polynomial representations of the special linear group. On the other hand, in 1959 Nagata exhibited group actions where this Noetherian property does not hold. In this tutorial we discuss these classical examples, with emphasis on their geometric meaning, and we present computer algebra tools for computing invariants.

The basis of geometric complexity theory is the essential equivalence between the foundational problems of Geometry (derandomization of Noether's Normalization Lemma for explicit varieties) and Complexity Theory (sub-exponential lower bounds for infinitesimally close approximation of exponential-time-computable multilinear polynomials by algebraic circuits). In view of this equivalence, the existing EXPSPACE vs. P gap, called the GCT chasm, in the complexity of derandomization of Noether's Normalization Lemma (NNL) for explicit varieties may be viewed as the common cause and measure of the difficulty of these problems.

This series of two tutorials will give an overview of these developments and of unconditional quasi-derandomization of NNL for some special cases of explicit varieties, including the one that was the focus of Hilbert's foundational paper in which Noether's Normalization Lemma was proved.

The first session of this talk will take place on Monday, September 15 from 9:00 am – 10:20 am.

For fixed compact connected Lie groups H \subseteq G, we provide a polynomial time algorithm to compute the multiplicity of a given irreducible representation of H in the restriction of an irreducible representation of G. Our algorithm is based on a finite difference formula which makes the multiplicities amenable to Barvinok's algorithm for counting integral points in polytopes.

The Kronecker coefficients of the symmetric group, which can be seen to be a special case of such multiplicities, play an important role in the geometric complexity theory approach to the P vs. NP problem. Whereas their computation is known to be #P-hard for Young diagrams with an arbitrary number of rows, our algorithm computes them in polynomial time if the number of rows is bounded. We complement our work by showing that information on the asymptotic growth rates of multiplicities in the coordinate rings of orbit closures does not directly lead to new complexity-theoretic obstructions beyond what can be obtained from the moment polytopes of the orbit closures. Non-asymptotic information on the multiplicities, such as provided by our algorithm, may therefore be essential in order to find obstructions in geometric complexity theory. This is joint work with Michael Walter and Brent Doran and available at arXiv:1204.4379

I will describe a number of recent dichotomy theorems in counting complexity. These include dichotomies for graph homomorphisms (spin systems), for constraint satisfactions, and for holant problems. I will describe the role holographic reductions play both in holographic algorithms and holographic reductions for hardness. I will present the thesis that for a very wide class of counting problems expressible as a sum-of-product computation (also known as partition functions), the entire class is divided into exactly three categories: (A) those that are solvable in polynomial time (B) those that are solvable in polynomial time for planar structures, but #P-hard in general, and (C) those that remain #P-hard even for planar structures. Furthermore, type (B) problems are solvable in P for planar structures precisely by Valiant's holographic algorithm based on matchgates, followed by Kasteleyn's algorithm for perfect matchings, making this a universal algorithm for this type of problems. This thesis is only partially proved (for symmetric constraint functions on Boolean variables, and for some asymmetric constraint functions.)

Asymtotic spectra of tensors were studied by Strassen to unterstand the exponent of matrix multiplication. We introduce this concept and present some new insights.

In this talk I explain the techniques needed to deal with the orbit closures in representations with finitely many orbits. These representations were classified by Kac in 1980.

The goals are to decide the normality and Cohen-Macaulay property of the orbit closure, the Hilbert function of the coordinate ring, the defining equations and even in some cases the free resolution of the polynomial ring.

I will discuss the techniques and will give examples of orbit closures in the space of skew symmetric 3-tensors in 7 variables.

This is based on the joint work with Kraskiewicz (on the arxive, arXiv:1201.1102 and arXiv:1301.0720) and on the work of Federico Galetto (arXiv:1210.6410).

Certificates to a linear algebra computation are additional data structures for each output, which can be used by a---possibly randomized---verification algorithm that proves the correctness of each output. The certificates are essentially optimal if the time (and space) complexity of verification is essentially linear in the input size N, meaning N times a factor N^{o(1)}, that is, a factor N^{\eta(N)} with \lim_{N\to \infty} \eta(N) = 0.

We give algorithms that compute essentially optimal certificates for the positive semidefiniteness, Frobenius form, characteristic and minimal polynomial of an n\times n dense integer matrix A. Our certificates can be verified in Monte-Carlo bit complexity (n^2 \log ||A||)^{1+o(1)}, where \log ||A|| is the bit size of the integer entries, solving an open problem in [Kaltofen, Nehring, Saunders, Proc. ISSAC 2011] subject to computational hardness assumptions.

Second, we give algorithms that compute certificates for the rank of sparse or structured n\times n matrices over an abstract field, whose Monte Carlo verification complexity is 2 matrix-times-vector products + n^{1+o(1)} arithmetic operations in the field. For example, if the n\times n input matrix is sparse with n^{1+o(1)} non-zero entries, our rank certificate can be verified in n^{1+o(1)} field operations. This extends also to integer matrices with only an extra \log||A||^{1+o(1)} factor.

All our certificates are based on interactive verification protocols with the interaction removed by a Fiat-Shamir identification heuristic. The validity of our verification procedure is subject to standard computational hardness assumptions from cryptography. Our certificates improve on those by Goldwasser, Kalai and Rothblum 2008 and Thaler 2012 for our problems in the prover complexity, and are independent of the circuits that compute them thus detecting programming errors in them.

This is joint work with Jean-Guillaume Dumas at the University of Grenoble.

The Kronecker coefficients of the Symmetric group S_n count the multiplicities of one irreducible representation of S_n in the tensor product of two other irreducibles. It has been a 76-year long standing question to find a combinatorial interpretation for these nonnegative integers, in the sense of enumerating some discrete feasible objects. Recently, the Kronecker coefficients found a new role in the Geometric complexity Theory with the conjectures (Mulmuley) that deciding their positivity is in P, and computing them in NP.

In this talk we will elaborate on this topic, explain certain methods from algebraic combinatorics used to handle the problems and discuss some recent results on both the combinatorial/algebraic aspect and the issues on complexity.