Georgia Institute of Technology College of Sciences

Numerical linear algebra is often regarded as a workhorse of scientific and engineering computing. Computational problems arising from optimization, partial differential equation, statistical estimation, etc, are usually reduced to one or more standard problems involving matrices: linear systems, least squares, eigenvectors/singular vectors, low-rank approximation, matrix nearness, etc. The idea of developing numerical algorithms for multilinear algebra is naturally appealing -- if similar problems for tensors of higher order (represented as hypermatrices) may be solved effectively, then one would have substantially enlarged the arsenal of fundamental tools in numerical computations. We will see that higher order tensors are indeed ubiquitous in applications; for multivariate or non-Gaussian phenomena, they are usually inevitable. However the path from linear to multilinear is not straightforward. We will discuss the theoretical and computational difficulties as well as ways to avoid these, drawing insights from a variety of subjects ranging from algebraic geometry to compressed sensing. We will illustrate the utility of such techniques with our work in cancer metabolomics, EEG and fMRI neuroimaging, financial modeling, and multiarray signal processing.

After, briefly, recalling the definition of contact homology, a powerful but somewhat intractable and still largely unexplored invariant of Legendrian knots in contact structures, I will discuss various ways of constructing more tractable and computable invariants from it. In particular I will discuss linearizations, products, massy products, A_\infty structures and terms in a spectral sequence. I will also show examples that demonstrate some of these invariants are quite powerful. I will also discuss what is known and not known about the relations between all of these invariants.

The analysis of Chvatal Gomory (CG) cuts and their associated closure for polyhedra was initiated long ago in the study of integer programming. The classical results of Chvatal (73) and Schrijver (80) show that the Chvatal closure of a rational polyhedron is again itself a rational polyhedron. In this work, we show that for the class of strictly convex bodies the above result still holds, i.e. that the Chvatal closure of a strictly convex body is a rational polytope.This is joint work with Santanu Dey (ISyE) and Juan Pablo Vielma (IBM).

The Subset Sum and Knapsack problems are fundamental NP-complete problems and the pseudo-polynomial time dynamic programming algorithms for them appear in every algorithms textbook. The algorithms require pseudo-polynomial time and space. Since we do not expect polynomial time algorithms for Subset Sum and Knapsack to exist, a very natural question is whether they can be solved in pseudo-polynomial time and polynomial space. In this paper we answer this question affrmatively, and give the first pseudo-polynomial time, polynomial space algorithms for these problems. Our approach is based on algebraic methods and turns out to be useful for several other problems as well. If there is time i will also show how our method can be applied to give polynomial space exact algorithms for the classical Traveling Salesman, Weighted Set Cover and Weighted Steiner Tree problems. Joint work with Jesper Nederlof.