The lectures will focus on the problem of comparing the determinant and the permanent. I will explain possible approaches involving algebraic geometry and representation theory, and explain how the problem is related, somewhat unexpectedly, to several important classical questions in these fields.
The second session of this talk will take place on Thursday, September 4 from 9:00 am – 10:00 am.
In this talk we are going to consider two questions:
The first one is depth reduction i.e. assume that we arithmetic circuit computing some function f(x_1,x_2,...,x_n) of size s. What upper bounds can we show on the size of the circuit of bounded depth computing f.
Second, we are going to show techniques to show lower bounds for depth 3 and 4 arithmetic circuits. We are going to show the following results:
If f is a polynomial of degree d that could be computed by circuit of size s then
Polynomial system solving can be viewed with either an algebraic or a geometric focus. The algebraic side typically uses Grobner basis computations while the geometric side uses witness sets and homotopy continuation. This talk will first provide a brief review of solving polynomial system using algebraic methods followed by an introduction to geometric methods via numerical algebraic geometry.
The second session of this talk will take place on Thursday, September 4 from 10:45 am – 11:45 am.
Starting with Schur-Weyl duality, we explain how polynomials can be written down as symmetrizations of highest weight vectors in a tensor power of C^n. Studying these polynomials leads to interesting questions in combinatorics, for example a famous conjecture about Latin Squares by Alon and Tarsi. Our goal is to explain the results of the three recent papers by Kadish and Landsberg, Bürgisser and Ikenmeyer, and Kumar, which all can be treated nicely in this framework.
The second session of this talk will take place on Friday, September 5 from 2:00 pm – 3:00 pm.
I will introduce tensors and tensor rank from an algebraic perspective. I will introduce multilinear rank and tensor rank, and I will discuss the related classical algebraic varieties — subspace varieties and secant varieties. I will give basic tools for computing dimensions, Terracini's lemma and the notion of the abstract secant variety. This will lead to the notion of generic rank. I will briefly disucss implicit equations, which lead to rank tests.
The second session of this talk will take place on Friday, September 5 from 9:00 am – 10:00 am.
Using algebra to approach real world problems often requires understanding solutions to equations and inequalities over the real numbers. Since real polynomials do not always have real roots, special theoretical and computational tools are needed to study real algebraic sets. I will give an introduction to these techniques and present some interesting applications.
I will give an introduction to quantum information theory with a focus on the concept of entanglement. The introduction will reveal close mathematical connections between key players in algebraic complexity (tensors, their rank, multiplicities etc. ) with concepts in quantum information theory (quantum states, entanglement, communication complexity, etc) which will allow us to transfer intuition and mathematical tools from one area to the other.
The lectures will focus on the problem of comparing the determinant and the permanent. I will explain possible approaches involving algebraic geometry and representation theory, and explain how the problem is related, somewhat unexpectedly, to several important classical questions in these fields.
The first session of this talk will take place on Tuesday, September 2 from 9:00 am – 10:00 am.
Polynomial system solving can be viewed with either an algebraic or a geometric focus. The algebraic side typically uses Grobner basis computations while the geometric side uses witness sets and homotopy continuation. This talk will first provide a brief review of solving polynomial system using algebraic methods followed by an introduction to geometric methods via numerical algebraic geometry.
The first session of this talk will take place on Thursday, September 2 from 1:45 pm – 2:45 pm.
This lecture will be a survey on Matrix Rigidity. The rigidity of a matrix A for a target rank r is the minimum number of entries of A that must be changed to ensure the altered matrix has rank at most r. The notion of matrix rigidity was introduced by Valiant (1977) as a means to proving lower bounds on the arithmetic complexity of linear transformations. In particular, he showed that if an n × n matrix has rigidity n1+ε for a target rank δn (where ε and δ are positive constants), then the map x → Ax cannot be computed by linear size log-depth circuits whose gates compute linear combinations of their inputs. Proving such a lower bound on explicit families of matrices still remains a challenging open problem. In this lecture, we will
We will outline general approaches to the rigidity problem in the results mentioned above and state several open questions along the way.
I will focus on one special case of tensor decomposition — symmetric tensors and Waring decomposition. I will start by discussing the naive approach, then I will discuss Sylvester's algorithm for binary forms. As a bonus I will show how Sylvester's algorithm for symmetric tensor decomposition also gives a method find the roots of a cubic polynomial in one variable.
I will discuss what to expect regarding generic rank and uniqueness of tensor decomposition. With the remaining time I will discuss the recently defined notion of an eigenvector of a (symmetric) tensor (Lim05, Qi05), which leads to a new method (developed with Ottaviani) for exact Waring decomposition.
The first session of this talk will take place on Wednesday, September 3 from 9:00 am – 10:00 am.
I will talk about some of the computations that algebraic geometers have learned to do to get information sometimes, apparently, infinitely much! with finite computations that a system such as Macaulay2 or Singular or Magma can perform on modest examples. I'll review some basics and then speak about methods that use the exterior algebra to get information about modules over polynomial rings and sheaves on projective spaces.
Starting with Schur-Weyl duality, we explain how polynomials can be written down as symmetrizations of highest weight vectors in a tensor power of C^n. Studying these polynomials leads to interesting questions in combinatorics, for example a famous conjecture about Latin Squares by Alon and Tarsi. Our goal is to explain the results of the three recent papers by Kadish and Landsberg, Bürgisser and Ikenmeyer, and Kumar, which all can be treated nicely in this framework.
The first session of this talk will take place on Tuesday, September 2 from 3:30 pm – 4:30 pm.
Condition is the main aspect in the understanding of the performance — regarding both stability and complexity — of numerical algorithms. Global insights into the quality of such algorithms can be obtained by a probabilistic analysis, assuming the data is random (e.g., subject to random perturbations). Often, a clean analysis can be obtained via a probabilistic analysis of the corresponding condition. This methodology can be applied in a wide variety of contexts, including linear algebra, convex optimization, and solving polynomial equations.
