Monday, December 14th, 2015

9:00 am9:45 am

L. Valiant conjectured that a polynomial that is "easy" to write down, is not necessarily "easy" to evaluate. More precisely,  he conjectured that the permanent polynomial of an mxm matrix cannot be written as the determinant of an nxn matrix whose entries are affine linear forms in the entries of the mxm matrix when n is a polynomial in m.  I will explain how one can prove Valiant's conjecture under a symmetry hypothesis and how this result reveals new approaches to the conjecture. This is joint work with N. Ressayre.

10:15 am11:00 am

We show that the problem of deciding positivity of Kronecker coefficients is NP-hard. We do so by providing a positive #P-formula for a subclass of Kronecker coefficients whose positivity is NP-hard to decide. We use this insight to construct many partition triples with few rows inside the Kronecker cone that have a vanishing Kronecker coefficient. This result takes a step towards proving the existence of occurrence-based representation-theoretic obstructions in the context of the geometric complexity theory approach to the permanent vs. determinant problem. Its proof also illustrates the effectiveness of the explicit proof strategy of geometric complexity theory.

11:30 am12:15 pm
We show that the problem of deciding membership in the moment polytope associated with a representation of a compact connected Lie group is in NP and coNP. These polytopes characterize the asymptotic non-vanishing of representation-theoretic multiplicities, including the stretched Kronecker coefficients. In contrast, it has recently been shown that deciding positivity of a single Kronecker coefficient is NP-hard in general [Ikenmeyer, Mulmuley and Walter, arXiv:1507.02955]. Thus our result suggests that representation theory can be easier in the asymptotic regime. It also has implications on the complexity of the marginal problem in quantum physics. This is joint work with P. Buergisser, M. Christandl and K. Mulmuley.
 
2:00 pm2:45 pm
One fundamental question in the geometric complexity theory approach to the VPws vs.
VNP conjecture is whether \bar{VPws}=VPws, where VPws is the class of families of polynomials that computed by symbolic determinants of polynomial size, and \bar{VPws} denotes the class of families of polynomials that can be approximated infinitesimally closely by symbolic determinants of polynomial size. We demonstrate nontriviality of this question by constructing an explicit family of polynomials that can be approximated infinitesimally closely by symbolic determinants of O(n) size but conjecturally cannot be computed exactly by symbolic determinants of (n^{2+δ}) size, for a small enough positive constant δ.
 
To study the question further, we introduce three degenerations of VPws, within \bar{VPws},
namely the stable degeneration Stable-VPws, the Newton degeneration Newton-VPws and the
p-definable one parameter degenerations VP*ws. The degenerations of VP and VNP are similar.
 
We show that (1) Stable-VPws ⊆ Newton-VPws ⊆ VP*ws ⊆ VNP, (2) Stable-VP ⊆ Newton-VP ⊆
VP* ⊆ VNP, and (3) Stable-VNP = Newton-VNP = VNP* = VNP.
 
This investigation supports the conjecture in GCT V that \bar{VPws} and \bar{VP} are not contained in VP (or even VNP). In fact, we are led to a refined conjecture that VPws ⊂ Newton-VPws ⊂
VP*ws ⊂ \bar{VPws}, and an analogous conjecture for VP.
 
Finally, we demonstrate that the families in Newton-VPws \ VPws would have to be very
special by showing that, for any finite quiver, Newton degeneration of any generic semi-invariant
has a small circuit.
 
Joint work with Ketan Mulmuley and Joshua A. Grochow.
3:15 pm4:00 pm

In this talk we consider the polynomial identity testing (PIT) problem: given an algebraic computation which computes a low-degree multivariate polynomial f, is f identically zero as a polynomial? This problem is of fundamental importance in computer algebra and also captures problems such as computing matchings in graphs. While this problem has a simple randomized algorithm (test whether f is zero at a random evaluation point), it is an active line of pseudorandomness research to develop efficient deterministic PIT algorithms for interesting models of algebraic computation.

A related problem is to develop lower bounds: given a model of algebraic computation, find an explicit polynomial f which is expensive to compute in this model. As efficient deterministic PIT algorithms for a model of algebraic computation can be shown to imply lower bounds for that model, developing lower bounds is often a precursor to developing such PIT algorithms. Recently, a new lower bounds technique called "the method of shifted partial derivatives" has been introduced and has been used to obtain a number of new lower bounds for various models, however its potential for yielding PIT algorithms is largely unexplored.

In this work, we use the method of shifted partial derivatives to develop PIT algorithms. In particular, we use these PIT algorithms to give deterministic algorithms for divisibility testing, that is, testing whether a given multivariate polynomial f divides another given multivariate polynomial g.

Tuesday, December 15th, 2015

9:00 am9:35 am

I will consider the symmetrization of the matrix multiplication tensor. This is the cubic polynomial trace(A^3), where A is a n*n matrix. Its interest relies on the fact that the asymptotic exponent for its rank (when n goes to infinity) is the same than the constant omega which measures the complexity of matrix multiplication. On the other hand, a cubic polynomial is more tractable and allows more algebraic geometry tools.

9:35 am10:10 am

In this talk we will focus on geometric and algebraic properties of tensors relating to their rank and border rank. In particular, we will:

1) present geometric properties of Coppersmith-Winograd tensor (that characterize it),
2) provide tensors with a large ratio of rank to border rank (previously conjectured to be bounded by two),
3) introduce a new method to bound border rank from below (slightly improving the known lower bounds for matrix multiplication),
4) introduce local variants of secant varieties (relating the study of border rank to geometric properties of the Hilbert scheme),
5) show that optimal border rank algorithms for matrix multiplication can be assumed to have a very special form,
6) present new necessary conditions for small border rank and compute border ranks of flag tensors (answering questions of Iliev, Manivel and Leitner).  

All results are based on a joint work with Joseph Landsberg.

10:40 am11:15 am
It was known classically that $2 \times 2 \times 2 \times 2 $ tensors are defective in rank 3 -- the generic tensor of that format and rank has infinitely many decompositions. 
 
Catalisano, Geramita and Gimigliano showed that binary tensors for $5$ or more factors are not defective, so tensors of rank less than the generic rank have finitely many decompositions. 
 
Bocci and Chiantini showed that $2 \times 2 \times 2 \times 2 \times 2$ tensors are not identifiable in rank 5 ---  the generic tensor of that format has exactly 2 decompositions up to symmetry.   
 
Bocci, Chiantini and Ottaviani showed that for $n \geq 6$ factors, binary $n$-factor tensors are almost always $k$-identifiable.
 
Bernd Sturmfels asked in his ``algebraic fitness session'' at the Simon's Institute (Fall 2014) to study the boundary case of binary 5 factor tensors of rank 5 and to find its minimal defining equations. 
 
In this talk I will describe a computational proof that the fifth secant variety of the Segre product of five copies of the projective line is a codimension 2 complete intersection of equations of degree 6 and 16. Our computations rely on pseudo-randomness, and numerical accuracy, so parts of our proof are only valid “with high probability”.
 
This is joint work with Steven Sam.
11:15 am11:50 am

Let n,d>0 and f be a system of n complex homogeneous polynomials of degree d in n variables. We call a point (v,l) in C^n\{0} x C an eigenpair of f, if f(v)=l*v. In this case we call v an eigenvector and l an eigenvalue of f. 

This talk consists of two parts. In the first part  I want to present the probability distribution of l, when the  coefficients of f in the Bombieri-Weyl basis are iid complex centered gaussian random variables and |v|=1 is chosen uniform at random from all eigenvectors of f (I will also explain why this is possible). It turns out that the distribution of 2l is mixed from chi-square-distributions with weights from the truncated geometric distribution.

In the second part I want to present recent results about numerically computing eigenpairs. We call a point (z,t) in C^n\{0} x C an h-eigenpair of f if f(z)=t^(d-1)*z. This equation is homogeneous with n equations and n+1 variables. The main tool to approximate solutions of such systems are homotopy methods. I will explain why the homotopy method for arbitrary systems of n equations in n+1 variables is not a good choice for the h-eigenpair problem.  Further, I will describe a randomized algorithm that for almost all systems approximates h-eigenpairs almost surely. Its average number of arithmetic operations is polynomial in the input size.

2:00 pm2:35 pm

Over a field of characteristic zero, we prove that for each r, there exists a constant C(r) so that the prime ideal of the rth secant variety of any Veronese embedding of any projective space is generated by polynomials of degree at most C(r). The main idea is to consider the coordinate ring of all of the ambient spaces of the Veronese embeddings at once by endowing it with the structure of a Hopf ring, and to show that its ideals are finitely generated. This is based on arXiv:1510.04904.

2:35 pm3:10 pm

Diagonalizing a matrix is very useful in many applications. We discuss how to obtain a similar decomposition of a tensor. We define the notion of an eigenvector of a tensor and describe possible configurations of points in projective space which can occur as the eigenvectors of some tensor. This is based on joint work with Bernd Sturmfels and Hirotachi Abo.

Wednesday, December 16th, 2015

9:00 am9:45 am

I will describe a deterministic algorithm that computes an approximate root of n complex polynomial equations in n unknowns in average polynomial time with respect to the size of the input, in the Blum-Shub-Smale model with square root. It rests upon a derandomization of an algorithm of Beltrán and Pardo and gives a deterministic affirmative answer to Smale’s 17th problem. The main idea is to make use of the randomness contained in the input itself.

10:15 am10:45 am

One way to understand the structure of the solution set of a system of polynomial equations is to decompose the solution set into its irreducible components.  Although such global information can help to solve many problems, local information is often more useful, especially at real points.  This talk will define a local irreducible decomposition, introduce a numerical algebraic geometric technique for computing the local structure, and apply it to several examples.

10:45 am11:15 am

The maximum likelihood degree (ML degree) of a statistical model counts the number of critical points of the likelihood function restricted to the model’s Zariski closure, thereby measuring the difficulty of maximum likelihood estimation.  The ML degree can be determined by solving a structured polynomial system called likelihood equations. On the other hand, the ML degree can also be computed using topological methods.  In this talk, we discuss computing ML degrees of rank 2 matrices using Euler characteristics. Using ML duality we are able to determine the ML degrees of determinants. 

11:30 am12:00 pm
The main goal of this talk is to present a result related to a conjecture suggested by Catalisano, Geramita, and Gimigliano in 2002, which claims that the secant varieties of tangential varieties to Veronese varieties are non-defective modulo a few known exceptions. This is joint work with Nick Vannieuwenhoven. 
 
2:00 pm2:30 pm

A reciprocal linear space is the image of a linear space under coordinate-wise inversion. This nice algebraic variety appears in many contexts and its structure is governed by the combinatorics of the underlying hyperplane arrangement. A reciprocal linear space is also an example of a hyperbolic variety, meaning that there is a family of linear spaces all of whose intersections with it are real. This special real structure is witnessed by a determinantal representation of its Chow form in the Grassmannian. In this talk, I will introduce reciprocal linear spaces and discuss the relation of their algebraic properties to their combinatorial and real structure. This is joint work with Mario Kummer. 

2:30 pm3:00 pm

Positive semidefinite rank is a generalization of regular and nonnegative matrix ranks. We are interested in the semialgebraic set and boundaries of the set of matrices of rank at most r and of psd rank at most k, where r and k are small. In particular, we describe the algebraic boundary of this semialgebraic set for r=3 and k=2 and conjecture a characterization of the boundary for r=k+1. I will also explain a geometric version of our conjecture in terms of polytopes and spectrahedral shadows. This talk is based on joint work with Elina Robeva and Richard Z. Robinson.