Titles and abstracts for IMA workshop talks
click here to return to main page

All talks in Blocker 628

Henry Cohn (Microsoft)
Solving equations under constraints


In this talk, I'll survey some key applications within
coding theory and cryptography for solving polynomial
equations with side constraints on the solutions.
In the single-variable case this is relatively well
understood, thanks to important work in the late 1990's
by Sudan and by Coppersmith, but higher dimensions
hold many mysteries. I'll highlight some problems
we really ought to be able to make progress on.


Harm Derksen (U. Michigan)
Polymatroids



Polymatroids encode the combinatorial properties of subspace arrangements. But they also appear
in other areas such as combinatorial optimization, information theory, graph theory and studying principal
minors of symmetric matrices. I will give an overview of the various areas in which polymatroids appear
and how they are interrelated. A central problem is to find necessary inequalities for
polymatroids to be realizable as subspace arrangements or as information entropy measures.


Jack Huizenga (Harvard)
Problems in tensor decomposition




Any tensor can be expressed as a minimal sum of rank-one terms; the
length of such an expression is the rank.  In applications, the rank of
a tensor often has important physical significance.  Often of equal
importance are the individual terms occurring in such an expression.  It
is then important to be able to determine such minimal representations
and describe when such expressions are unique (or determine in what way
uniqueness fails).  Furthermore, applications demand that we understand
this problem over not only the complex numbers, but also over the real
or positive real numbers.  Additional issues can arise when noise is
introduced into the sample, as experimentally obtained tensors will
exhibit generic rank.  We will discuss several results in this area,
with a focus on open problems.



Abhinav Kumar (MIT)
Matrix rigidity and elimination theory


The rigidity of an n by n matrix for target rank r is the minimum
number of changes in its entries required to bring its rank down to at
most r. Rigidity was introduced by Valiant in connection with circuit
complexity. Generic matrices have maximal riditity (i.e. (n-r)2), but
it is an open problem to determine explicit families of matrices with
high rigidity. I will describe the connection with complexity theory,
some open problems and progress, and related interesting questions in
algebraic geometry. This talk is based on joint work wth Satya Lokam,
Vijay Patankar and Jayalal Sarma M.N.



Luke Oeding (UC Berkeley)
Algebraic and Geometric Aspects of Audio Signal Processing


In Audio Signal Processing one problem one would like to efficiently solve might be automatic dictionary learning for
 large audio databases. In this example, as well as many others, rich and interesting algebraic and geometric
 structure arises. For example, one is lead to studying large matrices that have the structure as the sum of
 a low rank matrix and a sparse matrix. One might ask, for a given matrix, what is simpler matrix that is
 low rank plus sparse that is close to the given matrix in the appropriate matrix? Is such an approximation
 unique? What ranks and sparsity conditions lead to good approximations? I will describe these problems
 from a algebra-geometric viewpoint, and suggest what geometric problems, if solved, would be interesting
 for Audio Signal processing.

Claudiu Raicu (Princeton)
Evasive sets, elusive mappings, and geometry



A rational normal curve is never contained in a hyperplane, that is it
eludes the image of any polynomial mapping of degree 1 from a lower
dimensional (affine or projective) space. It is then natural to ask for
other explicit curves that elude the image of degree 2 (or higher)
polynomial mappings from lower dimensional spaces. Such curves would
provide, for instance, lower bounds for computing the permanent. Of a
similar flavor is the problem of finding explicit evasive sets, which
are sets that have small intersection with linear spaces (or more
generally with bounded degree subvarieties) of a given dimension. Such
sets have been studied in connection to error correcting codes. I will
discuss evasive sets and elusive mappings in the context of
computational complexity, and describe some geometric problems they give
rise to.



Rekha Thomas (U. Washington)
The Triangulation Problem in Computer Vision


A fundamental problem in computer vision is to reconstruct the 3D
coordinates of a scene from noisy images of it in a set of cameras. This
problem can be modeled as a polynomial optimization problem with
determinantal constraints. These determinants define the multi-view ideal
which is endowed with rich combinatorics. In joint work with Chris Aholt
and Bernd Sturmfels we determine a universal Groebner basis for this ideal.
We show that the Hilbert scheme of this ideal is connected and that it has
a distinguished component that carries all multi-view ideals when there are
at least three cameras. In joint work with Sameer Agarwal and Chris Aholt,
we then solve the polynomial optimization problem using convex relaxation
methods that rely on semidefinite programming and apply the methods to
reconstructing well known point sets in the computer vision literature.