Monday, September 15th, 2014

9:00 am10:20 am

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 second session of this talk will take place on Tuesday, September 16 from 10:20 am – 11:40 am.

10:50 am12:10 pm

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.

3:30 pm4:50 pm

Mulmuley and Sohoni observed that the permanent versus determinant problem can be interpreted as a specific orbit closure problem in the space of homogeneous forms, and they proposed to attack it by methods from geometric invariant and representation theory.

In the lecture, I will explain how these ideas apply in the related, but simpler setting of trilinear forms. This setting is of considerable interest by itself, since it captures the tensor rank problem, and in particular the complexity of matrix multiplication.

The analysis of the symmetries via representions leads to a bunch of challenging mathematical questions. A main idea is to understand, which irreducible representations occur in the coordinate rings of the orbit closures under question. We explain some of the known mathematical tools to adress these questions and the current limitations for advancing further.

Tuesday, September 16th, 2014

9:00 am9:50 am

Let G be a connected linear algebraic group, let V be a finite dimensional algebraic G-module, and let O_1 and O_2 be two G-orbits in V. The talk is aimed at a discussion of the constructive ways of finding out whether or not O_1 lies in the Zariski closure of O_2. This yields the constructive ways of finding out whether given two points of V lie in the same orbit or not. Several classical problems in algebra and algebraic geometry are reduced to this problem.

10:20 am11:40 am

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.

1:20 pm2:10 pm

The Kronecker coefficients $g_{\alpha\beta\gamma}$ and the Littlewood-Richardson coefficients $c_{\alpha\beta}^\gamma$ are nonnegative integers depending on three partitions $\alpha$, $\beta$, and $\gamma$. By definition, $g_{\alpha\beta\gamma}$ (resp. $c_{\alpha\beta}^\gamma$) are the multiplicities of the tensor product decomposition of two irreducible representations of symmetric groups (resp. linear groups). By a classical Littlewood-Murnaghan's result the Kronecker coefficients extend the Littlewood-Richardson ones.

The nonvanishing of the Littlewood-Richardson coefficient $c_{\alpha\beta}^\gamma$ implies that $(\alpha, \beta, \gamma)$ satisfies some linear inequalities called Horn inequalities. We extend some Horn inequalities to the triples of partitions corresponding to a nonzero Kronecker coefficient.

2:40 pm3:30 pm

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

4:00 pm4:50 pm

Geometric complexity theory suggests intriguing connections between positivity problems in algebraic combinatorics and complexity theory. I will discuss a general algebraic technique for finding positive combinatorial formula for the Schur expansion of symmetric functions. This technique has its origins in the \emph{plactic algebra}, the free associative algebra in the alphabet of positive integers modulo Knuth equivalence. It has been known since the work of Sch\""utzenberger and Lascoux from the 1980's that the plactic algebra contains a subalgebra isomorphic to the ring of symmetric functions, equipped with a basis of noncommutative versions of Schur functions.

More recently, Fomin and Greene showed that the plactic algebra can be modified by replacing certain pairs of Knuth relations by weaker four-term relations. By studying the noncommutative Schur functions in this algebra, they obtain Schur expansions for a large class of symmetric functions including Stanley symmetric functions and stable Grothendieck polynomials.

Several years ago, Assaf defined variants of Knuth equivalence to prove Schur positivity of Macdonald polynomials. Using this work as a starting point, Sergey Fomin and I extend the Fomin-Greene setup to give Assaf's equivalences an algebraic framework and thereby obtain an approach to finding positive combinatorial formulae for the Schur expansions of an even larger class of symmetric functions. One application is a positive combinatorial formula for the Schur expansion of 3-column Macdonald polynomials.

Wednesday, September 17th, 2014

9:00 am9:50 am

In this lecture I plan to survey some of my favorite ways (of the huge variety) in which matrix rank and its extensions play a crucial role in understanding basic problems in computation, geometry, algebra and combinatorics. Some of these extensions and connections are classical and others quite new – they all lead to many interesting open questions.

10:20 am11:10 am

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.)

11:40 am12:20 pm

In this talk, I will survey some recent development of approximate counting algorithms based on correlation decay technique. Unlike the previous major approximate counting approach based on sampling such as Markov Chain Monte Carlo (MCMC), correlation decay based approach can give deterministic fully polynomial-time approximation scheme (FPTAS) for a number of counting problems. At the heart of this approach is to prove that certain mapping derived from a local recursion is contractive under some local Riemann metric.

2:00 pm2:50 pm

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

3:20 pm4:10 pm

We begin by describing the ideas behind the state-of-the-art bounds on omega, the exponent of matrix multiplication.

We then present the "group-theoretic" approach of Cohn and Umans as an alternative to these methods, and we generalize this approach from group algebras to general algebras. We identify adjacency algebras of coherent configurations as a promising family of algebras in the generalized framework. We prove a closure property involving symmetric powers of adjacency algebras, which enables us to prove nontrivial bounds on omega using commutative coherent configurations, and suggests that commutative coherent configurations may be sufficient to prove omega = 2.

Along the way, we introduce a relaxation of the notion of tensor rank, called s-rank, and show that upper bounds on the s-rank of the matrix multiplication tensor imply upper bounds on the ordinary rank. In particular, if the "s-rank exponent of matrix multiplication" equals 2, then the (ordinary) exponent of matrix multiplication, omega, equals 2.

Finally, we will mention connections between several conjectures implying omega=2, and variants of the classical sunflower conjecture of Erdos and Rado.

No special background is assumed.

Based on joint works with Noga Alon, Henry Cohn, Bobby Kleinberg, Amir Shpilka, and Balazs Szegedy.

4:40 pm5:20 pm

Mulmuley and Sohoni conjectured that the permanent vs determinant problem can be resolved using explicit so-called representation theoretic occurence obstructions. It is still unknown whether these objects exist or not, even for small examples. We show that in the simpler (but still highly interesting) setting of matrix multiplication these obstructions indeed exist! We prove the lower bound R(M_m) >= 3/2 m^2 ? 2 on the border rank of m x m matrix multiplication by exhibiting explicit representation theoretic occurence obstructions. While this bound is weaker than the one recently obtained by Landsberg and Ottaviani, these are the first significant lower bounds obtained within the GCT program. Behind the proof is basically Schur-Weyl duality and an explicit description of highest weight vectors in terms of combinatorial objects.

Thursday, September 18th, 2014

9:00 am9:50 am

We show the existence of a large family of representations supported by the orbit closure of the determinant. However, the validity of our result is based on the validity of the celebrated 'Latin Square Conjecture' due to Alon-Tarsi or more precisely on the validity of an equivalent 'Column Latin Square Conjecture' due to Huang-Rota.

10:20 am11:10 am

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).

11:40 am12:20 pm

Simple questions in linear algebra often give rise to interesting objects in algebraic geometry. For example, the space of singular $n \times n$ matrices is the classical hypersurface given by the vanishing of the $n\times n$ determinant. This hypersurface has interesting geometric properties. In particular, it contains many linear subspaces, whose study is related to (among other things) geometric complexity theory.

In this talk, I will introduce a geometric object, called a Fano scheme, parameterizing these linear subspaces. We'll look at some basic examples of Fano schemes, and then see a characterization of exactly when our Fano schemes are connected. Motivated by complexity theory, we'll also compare linear spaces contained in the hypersurface cut out by the determinant to those contained in the hypersurface cut out by the permanent. This is joint work with Melody Chan.

2:00 pm2:50 pm

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.

3:00 pm3:50 pm

Can arithmetic computation be efficiently parallelized? Specifically, if a multivariate polynomial f is computed by an arithmetic circuit of size s, what is the size of the smallest circuit of depth d computing f? Building on the seminal work of Valiant, Skyum, Berkowitz and Rackoff in 1983, recent results on depth reduction have shown that nontrivial depth reduction is possible even for target depth being d=3 and d=4. The resulting circuit has size roughly s^sqrt(deg(f)). Is this optimal?

The results on depth reduction also yield a potential route to prove lower bounds for arithmetic circuits - via proving strong enough lower bounds for low depth circuits. We will also see recent lower bounds for such low depth circuits which yield optimality of depth reduction in some of these settings (and come tantalizingly close to the threshold required to prove superpolynomial lower bounds for general circuits).

Friday, September 19th, 2014

9:00 am9:50 am

I will explain how work of Gupta, Kamath, Kayal and Saptharishi on shallow circuits leads to exciting questions in algebraic geometry. While their work was focused on separating complexity classes via shallow circuits, I will address the more modest goal of using the methods they introduce to improve the state of the art in separating the determinant from the permanent. This leads to the study of several longstanding conjectures in representation theory (Hadamard-Foulkes-Howe conjecture) combinatorics (Alon-Tarsi) conjecture, and commutative algebra. This is joint work with several co-authors, I will focus on the most recent work with Hal Schenck regarding Hilbert functions of the ideal generated by sub-permanents.

10:20 am11:10 am

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.

11:40 am12:20 pm

The composition of two Schur functors, so called plethysm, in general is a reducible representation. The problem of decomposing it into irreducible components is well-known and hard.

We will present the results of a joint work with Thomas Kahle, where we provide formulas for certain plethysms by relating them to convex polyhedral geometry. Our algorithmic approach relies on the Barvinok software used to obtain quasipolynomials counting lattice points in fibers of a projection of a polyhedral cone.

In particular, we provide explicit formulas for $S^\mu(S^k)$ where $\mu$ is any partition of 4 or 5 and k is a parameter. We also prove asymptotic formulas conjectured by Howe in case when $\mu$ is any partition.

2:00 pm3:30 pm

This session will have a talk by Jerzy Weyman on "Quiver Theory" followed by a talk by Ketan Mulmuley giving a brief sketch of the systematic GCT program to cross the GCT chasm (the subject of the two tutorials on the first two days of the workshop) along with a discussion on the broader issues in the context GCT (including the more philosophical issues concerning the basic strategy of GCT and also concerning possible alternatives to GCT or alternative approaches to GCT).

Since the schedule of this workshop is very tight, it is requested that the questions during all earlier talks and tutorials in the workshop be confined to the specific technical issues in those talks and tutorials, and all questions concerning the broader/philosophical issues be reserved for the Friday wrap-up session. This session is very important, and so all the participants (and especially the ones who have broader questions concerning GCT) are encouraged to attend it.