Plenary Talk Abstracts

Noga Alon Tel Aviv University   Title: The structure of large graphs and its algorithmic aspects Abstract: A property of graphs is hereditary if it is closed under deleting vertices, and is monotone if it is closed under deleting vertices and edges. Many interesting properties of graphs are monotone or hereditary, and their study reveals some unexpected phenomena. This study combines combinatorial, probabilistic, geometric and analytic tools, including Szemeredi's Regularity Lemma and Grothendieck's Inequality, and leads to interesting extremal and algorithmic applications. In particular, it provides an efficient algorithm to approximate the distance of a given input graph from any prescribed monotone graph property P. For any such P and any fixed positive real epsilon, the algorithm computes the minimum number of edges that have to be deleted from a graph G on n vertices to get a graph that satisfies P, up to an additive error of epsilon n^2. I will survey the topic, mentioning the main questions, describing several recent and less recent results and giving a brief description of the relevant proof techniques. Talk slides

Carlos Beltrán Universidad de Cantabria, Santander Title: Distributing many points in the two-dimensional sphere Abstract: How can N points be chosen in the two-dimensional sphere in such a way that they are "well distributed"? This is an old question originally posed by physicists (Thomson problem) in an attempt to understand the way electrons behave when confined to a spherical surface, and by biologists (Tammes problem) who found very regular patterns in microscopical spherical particles of pollen. Among the many different ways that one can define "well distributed" spherical points, a particularly interesting one is the following: a set of N points is optimally distributed if the product of their mutual distances is maximal. N-tuples satisfying that property are called elliptic Fekete points. Smale's 7th problem asks to locate these points efficiently. In this talk I will present some recent and not-so-recent progress in the study of this question. Talk abstract

Gunnar Carlsson Stanford University   Title: Topological Methods for Analysis of Large and Complex Data Abstract: During the last few years, there has been a recognition that the study of the "shape" of data sets is an important problem in data analysis, which frequently is not sufficiently well addressed by cluster analysis on the one hand and scatterplot methods such as PCA or MDS. The mathematical discipline which studies shape in the setting of pure mathematics is called topology, and there has been substantial effort expended on adapting topological methods to the study of data sets. The methods provide tools both for representing data sets in a way which is both compressed and yet faithful to the rough geometric features, as well as for measuring the shape of a data set in a suitable sense. I will discuss both directions, with examples.

Snorre H. Christiansen University of Oslo   Title: Upwinding in finite element spaces of differential forms Abstract: In recent years, a number of finite element spaces compatible with the differential operators grad, curl and div, have been given a unified presentation in the language of differential forms, enabling a likewise unified analysis of discretizations of partial differential equations related to the Hodge Laplacian. I will present a general framework for the construction of finite element spaces of differential forms, allowing for polyhedral meshes and non-polynomial basis functions. We apply it to get a variant of finite element exterior calculus, incorporating a form of upwinding adapted to convection dominated flows.

David Donoho Stanford University   Title: Precise asymptotics in compressed sensing Abstract: I will describe recent work giving precise asymptotic results on mean squared error and other characteristics, in a range of problems in compressed sensing; these include results for LASSO, group LASSO, and nonconvex sparsity penalty methods. A key applicaton of such precise formulas is their use in deriving precise optimality results which were not known previously, and to our knowledgenot available by other methods.

Robert Ghrist University of Pennsylvania   Title: Euler Calculus for Data Abstract: This talk describes an ingenious integral calculus based on Euler characteristic, stemming from work on constructible sheaves due to MacPherson and Kashiwara in the 1970s, and connecting back further to classical integral geometry. I will emphasize (1) its novel utility in data management, particularly in aggregation of redundant data and inverse problems over sensor networks; and (2) how issues of numerical computation, inspired by applications, leads to fascinating connections with Morse theory and computational topology. Talk slides

Alberto Grünbaum UC Berkeley   Title: Three hungarian walks Abstract: The classical random walks of George Polya (1921) are well known, in particular his results about recurrence depending on the dimension of the lattice. In this talk I will show that Gábor Szegő (1920) gave us the tools to study quantum walks in dimension one. I will look at the question of recurrence for quantum walks by going back to a seminal paper by Frigyes Riesz (1918). Quantum walks have attracted the attention of workers in areas ranging from computer science to physics. They have been recently implemented in laboratory situations and they have been used as models to study phothosynthesis in plants.

Olga Holtz UC Berkeley   Title: Group-theoretic methods in linear algebra and signal processing Abstract: This talk will offer an overview of recent developments in numerical linear algebra, compressive sensing and signal processing based on group algebras and group representations. Both theoretical and practical aspects of these new techniques will be discussed.

Thomas Y. Hou Caltech   Title: The interplay between computation and analysis in the study of 3D incompressible Euler and Navier-Stokes equations. Abstract: Whether the 3D incompressible Navier-Stokes equations can develop a finite time singularity from smooth initial data with finite energy is one of the Seven Millennium Problems posted by the Clay Mathematical Institute. We review some recent theoretical and computational studies of the 3D Euler equations which show that there is a subtle dynamic depletion of nonlinear vortex stretching due to local geometric regularity of vortex filaments. Our study reveals a surprising nonlinear stabilizing effect that the convection term plays in stabilizing the solution. This is demonstrated through two reduced models of the 3D incompressible Navier-Stokes equations which shows that local flattening of the vortex structure and the effect of convection could lead to dynamic depletion of the vortex stretching term. Finally we present a new class of solutions to the 3D Euler and Navier-Stokes equations which could lead to a strong nonlinear alignment in the vortex stretching term and have the potential to develop a finite time vortex sheet singularity. However, the Kelvin-Helmholtz instability of the fluid flow eventually destroys such nonlinear alignment and lead to the development of turbulence instead of forming a finite time singularity.

Evelyne Hubert INRIA Méditerranée   Title: Algebraic and Differential Invariants Abstract: The discriminant of a quadratic or the curvature of a plane curve are notorious invariants for the linear or Euclidean group. They unveil intrinsic geometrical properties independent of the coordinates in which the polynomial or the curve is given. In those two cases, the underlying group actions and their invariants are well studied in the context of algebraic and differential geometry respectively. A rich variety of other group actions arise in science and engineering. Based on work of collaborators and myself, I shall focus on algebraic algorithms that allow the construction of invariants and their (differential) relationships for any given group action and shortly discuss some areas where those results are of use. Talk slides*

László Lovász Eötvös Lóránd University, Budapest Title: Algorithmic problems in very large graphs Abstract:Algorithmic questions concerning very large graphs present novel challanges: some of the classical algorithmic problems must be rephrased, and a new kind of complexity theory emerges. By "very large" we mean a graph whose nodes and edges are too numerous to be treated as a single file of data, and often even the number of nodes is not known. We assume that information about such graphs is obtained by an appropriate sampling procedure.   It is clear that every computational result will only be approximate, but this is not the only problem. What should it mean to compute a perfect matching or a maximum cut in such a graph? One possible approach is to give an algorithm that computes the answer locally, from local data. Making this precise connects optimization with techniques in graph theory developed to handle large graphs (like regularity partitions and graph limits).   There are two, in a sense extreme, situations when this issue is best understood: dense graphs (in which a positive fraction of edges are present), and graphs with bounded degree. We survey the similarites and differences between these two theories. Talk slides

Christian Lubich Universitaet Tuebingen Title: Modulated Fourier expansions for highly oscillatory problems Abstract: Modulated Fourier expansions are an analytic technique for understanding the behaviour of weakly nonlinear oscillatory problems over very long times. The technique applies to highly oscillatory ODEs, to particle systems such as the Fermi-Pasta-Ulam lattice, to Hamiltonian PDEs such as nonlinear Schr\"odinger and wave equations, as well as to their numerical discretizations. The approach first came up about a decade ago in the numerical analysis of highly oscillatory ODEs, where it explained remarkable long-time energy conservation properties of numerical integrators, and has since been used to analyse long-time properties of various types of problems as mentioned above, both for the continuous equations and their numerical discretizations. In addition to their role as an analytical tool originating from numerics, modulated Fourier expansions have also been found useful as a numerical approximation method for highly oscillatory problems. Most of the talk is based on joint work with Ernst Hairer, some parts also with David Cohen, Ludwig Gauckler and Daniel Weiss. Talk slides

Hans Munthe-Kaas University of Bergen Title: Multivariate Chebyshev polynomials; from group theory to PDE solvers Abstract: Classical univariate Chebyshev polynomials are fundamental objects in computational mathematics. Their ubiquity in applications is summarized by the quote: "Chebyshev polynomials are everywhere dense in numerical analysis" (perhaps due to George Forsythe). Most of the useful properties of Chebyshev polynomials arise from their tight connections to group theory. From this perspective, multivariate Chebyshev polynomials appear as natural generalizations, constructed by a kaleidoscope of mirrors acting upon R^n (i.e. affine Weyl groups). Multivariate Chebyshev polynomials were first introduced by Koornwinder already in 1974, but they have only very recently been applied in computational mathematics. The fact that the multivariate polynomials are orthogonal on domains related to triangles, tetrahedra and higher dimensional simplexes, rises the important question of their applicability in triangle-based spectral element methods for PDEs. We have developed general software tools with such applications in mind. Finally, we remark upon connections to the representation theory of compact Lie groups, which may lead to applications in very different areas of computational mathematics. Talk slides

Michael L. Overton Courant Institute of Mathematical Sciences, NYU Title: Optimization of Polynomial Roots, Eigenvalues and Pseudospectra Abstract: The root radius and root abscissa of a monic polynomial are respectively the maximum modulus and the maximum real part of its roots; both these functions are nonconvex and are non-Lipschitz near polynomials with multiple roots. We begin the talk by giving constructive methods for efficiently minimizing these nonconvex functions in the case that there is just one affine constraint on the polynomial's coefficients. We then turn to the spectral radius and spectral abscissa functions of a matrix, which are analagously defined in terms of eigenvalues. We explain how to use nonsmooth optimization methods to find local minimizers and how to use nonsmooth analysis to study local optimality conditions for these nonconvex, non-Lipschitz functions. Finally, the pseudospectral radius and abscissa of a matrix A are respectively the maximum modulus or maximum real part of elements of its pseudospectrum (the union of eigenvalues of all matrices within a specified distance of A). These functions are also nonconvex but, it turns out, locally Lipschitz, although the pseudospectrum itself is not a Lipschitz set-valued map. We discuss applications from control and from Markov chain Monte Carlo as examples throughout the talk. Coauthors of relevant papers include Vincent Blondel, Jim Burke, Kranthi Gade, Mert Gurbuzbalaban, Adrian Lewis and Alexandre Megretski. Talk slides

Klaus Ritter Technische Universität Kaiserslautern Title: Quadrature Problems for Stochastic Differential Equations Abstract: By quadrature of SDEs we mean computation of expectations E(f(X)) of functionals f on the path space w.r.t. the distribution of the solution X of the SDE. This differs from classical numerical integration, since typically the distribution is unknown and the domain of integration is infinite-dimensional. Quadrature problems of this kind arise, e.g., for valuation of path-dependent options in mathematical finance. In this talk we discuss and compare deterministic and randomized (i.e. Monte Carlo) algorithms from a complexity point of view on different classes of functionals f. The analysis relies in particular on tractability results for high-dimensional integration and on results for linear and non-linear approximation of stochastic processes. The stochastic multi-level approach plays an important role for the construction of optimal algorithms. Joint work with S. Dereich (Marburg), F. Hickernell (Chicago), T. Müller-Gronbach (Passau), B. Niu (Chicago), L. Yaroslavtseva (Passau). Supported by the DFG within SPP 1324. Talk slides

Steven Smale City University of Hong Kong Title: On the Mathematical Foundations of Data Analysis Abstract: While inspired by Graph Theory and developments in “High Dimensional Data” we will offer an alternate perspective. This viewpoint will focus on a reproducing kernel, with some emphasis on associated geometry and algebraic topology. All this will be illustrated in the special case of the peptide binding problem with the presentation of new accurate algorithms.

William Stein University of Washington   Title: Sage - Creating a viable free open source alternative to Magma, Maple, Mathematica and Matlab Abstract: Sage (http://sagemath.org) is free open source software for doing mathematics that I started in 2005, to which hundreds of people have subsequently contributed as the project has steadily grown in popularity. I will describe my motivation for starting the project, the overall structure of the project today, and give a demo that showcases Sage. Talk slides

Mike Stillmann Cornell University Title: Sheaf cohomology: what it is, how to compute it, and what it's good for. Abstract: Sheaf cohomology is a major tool in algebraic geometry, with a large number of different applications. In this talk, we assume no knowledge of sheaves or other abstract algebraic geometry. Instead, we present a simple way to think about and compute with coherent sheaves on projective varieties. Serre's FAC paper from 1955, combined with Groebner basis methods, give us the first algorithms for computing sheaf cohomology groups. We will survey other more recent methods to compute cohomology as well, especially the method arising from the explicit Bernstein-Gelfand-Gelfand correspondence due to Eisenbud-Floystad-Schreyer. Finally, we will look at some applications of sheaf cohomology: (1) string theory in physics, (2) the recent exciting work in Boij-Soederberg theory in commutative algebra, and (3) some uses in surface theory in algebraic geometry. These methods for computing sheaf cohomology have been implemented in our computer algebra system Macaulay2 (joint with Dan Grayson), and we will show it in action on several of these problems.