Seminars and Colloquia by Series

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.

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.

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 –

Please Note: 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.

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.

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.

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

Please Note: 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.

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.

Pages