Seminars and Colloquia Schedule

Extremal Cuts of Sparse Random Graphs

Series
ACO Seminar
Time
Monday, October 5, 2015 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Amir Dembo – Stanford University
The Max-Cut problem seeks to determine the maximal cut size in a given graph. With no polynomial-time efficient approximation for Max-Cut (unless P=NP), its asymptotic for a typical large sparse graph is of considerable interest. We prove that for uniformly random d-regular graph of N vertices, and for the uniformly chosen Erdos-Renyi graph of M=N d/2 edges, the leading correction to M/2 (the typical cut size), is P_* sqrt(N M/2). Here P_* is the ground state energy of the Sherrington-Kirkpatrick model, expressed analytically via Parisi's formula. This talk is based on a joint work with Subhabrata Sen and Andrea Montanari.

On killing the affine line

Series
Geometry Topology Seminar
Time
Monday, October 5, 2015 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Inna Zakharevich – University of Chicago
The Grothendieck ring of varieties is defined to be the free abelian group generated by k-varieties, modulo the relation that for any closed subvariety Y of a variety X, we impose the relation that [X] = [Y] + [X \ Y]; the ring structure is defined by [X][Y] = [X x Y]. Last December two longstanding questions about the Grothendieck ring of varieties were answered: 1. If two varieties X and Y are piecewise isomorphic then they are equal in the Grothendieck ring; does the converse hold? 2. Is the class of the affine line a zero divisor? Both questions were answered by Borisov, who constructed an element in the kernel of multiplication by the affine line; coincidentally, the proof also constructed two varieties whose classes in the Grothendieck ring are the same but which are not piecewise isomorphic. In this talk we will investigate these questions further by constructing a topological analog of the Grothendieck ring and analyzing its higher homotopy groups. Using this extra structure we will sketch a proof that Borisov's coincidence is not a coincidence at all: that any element in the annihilator of the Lefschetz motive can be represented by a difference of varieties which are equal in the Grothendieck ring but not piecewise isomorphic.

Survival of the Smartest: Sparse Recovery in Biology

Series
Applied and Computational Mathematics Seminar
Time
Monday, October 5, 2015 - 14:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Felix Lieder – Mathematisches Institut Lehrstuhl für Mathematische Optimierung –
Survival can be tough: Exposing a bacterial strain to new environments will typically lead to one of two possible outcomes. First, not surprisingly, the strain simply dies; second the strain adapts in order to survive. In this talk we are concerned with the hardness of survival, i.e. what is the most efficient (smartest) way to adapt to new environments? How many new abilities does a bacterium need in order to survive? Here we restrict our focus on two specific bacteria, namely E.coli and Buchnera. In order to answer the questions raised, we first model the underlying problem as an NP-hard decision problem. Using a re-weighted l1-regularization approach, well known from image reconstruction, we then approximate ”good” solutions. A numerical comparison between these ”good” solutions and the ”exact” solutions concludes the talk.

Amoebas, Nonnegative Polynomials and Sums of Squares Supported on Circuits

Series
Algebra Seminar
Time
Monday, October 5, 2015 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Timo de Wolff – Texas A&M University
Deciding nonnegativity of real polynomials is a key question in real algebraic geometry with crucial importance in polynomial optimization. Since this problem is NP-hard, one is interested in finding sufficient conditions (certificates) for nonnegativity, which are easier to check. The standard certificates are sums of squares (SOS), which trace back to Hilbert (see Hilbert’s 17th problem). In this talk we completely characterize sections of the cones of nonnegative polynomials and sums of squares with polynomials supported on circuits, a genuine class of sparse polynomials. In particular, nonnegativity is characterized by an invariant, which can be immediately derived from the initial polynomial. Based on these results, we obtain a completely new class of nonnegativity certificates independent from SOS certificates. Furthermore, nonnegativity of such circuit polynomials f coincides with solidness of the amoeba of f , i.e., the Log-absolute-value image of the algebraic variety V(f) in C^n of f. These results establish a first direct connection between amoeba theory and nonnegativity of polynomials. These results generalize earlier works by Fidalgo, Ghasemi, Kovacec, Marshall and Reznick. The talk is based on joint work with Sadik Iliman.

Frontiers in Science lecture - Physics, Information and Computation

Series
Other Talks
Time
Monday, October 5, 2015 - 19:00 for 1 hour (actually 50 minutes)
Location
President's Suites C&D (Bill Moore Student Success Center First Level)
Speaker
Amir Dembo – Stanford University

Light refreshments at 6:30pm

Theoretical models of disordered materials yield precise predictions about the efficiency of communication codes and the typical complexity of certain combinatorial optimization problems. The underlying common structure is that of many discrete variables, whose interaction is represented by a random 'tree like' sparse graph. We review recent progress in proving such predictions and the related algorithmic insights gained from it. This talk is based on joint works with Andrea Montanari, Allan Sly and Nike Sun.

Approximation of p-ground states

Series
PDE Seminar
Time
Tuesday, October 6, 2015 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Ryan Hynd – University of Pennsylvania
The smallest eigenvalue of a symmetric matrix A can be expressed through Rayleigh's formula. Moreover, if the smallest eigenvalue is simple, it can be approximated by using the inverse iteration method or by studying the large time behavior of solutions of the ODE x'(t)=-Ax(t). We discuss surprising analogs of these facts for a nonlinear PDE eigenvalue problem involving the p-Laplacian.

Construction of whiskered invariant tori for fibered holomorphic dynamics (I: Reducibility).

Series
Dynamical Systems Working Seminar
Time
Tuesday, October 6, 2015 - 17:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Mikel de Viana – Georgia Tech
We consider fibered holomorphic dynamics, generated by a skew product over an irrational translation of the torus. The invariant object that organizes the dynamics is an invariant torus. Often one can find an approximately invariant torus K_0, and we construct an invariant torus, starting from K_0. The main technique is a KAM iteration in a-posteriori format. The asymptotic properties of the derivative cocycle A_K play a crucial role: In this first talk we will find suitable geometric and number-theoretic conditions for A_K. Later, we will see how to relax these conditions.

Wind-driven Waves and Fluid Instabilities

Series
Research Horizons Seminar
Time
Wednesday, October 7, 2015 - 12:00 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Prof. Chongchun Zeng – School of Mathematics, Georgia Institute of Technology –

Food and Drinks will be provided before the seminar.

In this talk, we start with the mathematical modeling of air-water interaction in the framework of the interface problem between two incompressible inviscid fluids under the influence of gravity/surface tension. This is a nonlinear PDE system involving free boundary. It is generally accepted that wind generates surface waves due to the instability of shear flows in this context. Based on the linearized equations about shear flow solutions, we will discuss the classical Kelvin--Helmholtz instability etc. before we illustrate Miles' critical layer theory.

Convex regularization for low rank tensor estimation

Series
Stochastics Seminar
Time
Thursday, October 8, 2015 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Ming Yuan – University of Wisconsin
Many problems can be formulated as recovering a low-rank tensor. Although an increasingly common task, tensor recovery remains a challenging problem because of the delicacy associated with the decomposition of higher order tensors. We introduce a general framework of convex regularization for low rank tensor estimation.

The matching problem has no small symmetric SDP

Series
ACO Student Seminar
Time
Friday, October 9, 2015 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Arefin Huq – Georgia Tech
Yannakakis showed that the matching problem does not have a small symmetric linear program. Rothvoß recently proved that any (not necessarily symmetric) linear program also has exponential size. It is natural to ask whether the matching problem can be expressed compactly in a framework such as semidefinite programming (SDP) that is more powerful than linear programming but still allows efficient optimization. We answer this question negatively for symmetric SDPs: any symmetric SDP for the matching problem has exponential size. We also show that an O(k)-round Lasserre SDP relaxation for the metric traveling salesperson problem (TSP) yields at least as good an approximation as any symmetric SDP relaxation of size n^k. The key technical ingredient underlying both these results is an upper bound on the degree needed to derive polynomial identities that hold over the space of matchings or traveling salesperson tours. This is joint work with Jonah Brown-Cohen, Prasad Raghavendra and Benjamin Weitz from Berkeley, and Gabor Braun, Sebastian Pokutta, Aurko Roy and Daniel Zink at Georgia Tech.

Multivariate Analytic Combinatorics: Functions with Algebraic Singularities

Series
Combinatorics Seminar
Time
Friday, October 9, 2015 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Torin Greenwood – Georgia Tech –
Flajolet and Odlyzko (1990) derived asymptotic formulae for the coefficients of a class of univariate generating functions with algebraic singularities. These results have been extended to classes of multivariate generating functions by Gao and Richmond (1992) and Hwang (1996, 1998), in both cases by reducing the multivariate case to the univariate case. Pemantle and Wilson (2013) outlined new multivariate analytic techniques and used them to analyze the coefficients of rational generating functions. In this talk, we discuss these multivariate analytic techniques and use them to find asymptotic formulae for the coefficients of a broad class of bivariate generating functions with algebraic singularities. We will also look at how to apply such formulae to practical problems.