Seminars and Colloquia by Series

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.

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.

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.

Morphing planar triangulations

Series
Combinatorics Seminar
Time
Friday, October 2, 2015 - 15:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Fidel Barrera Cruz – Georgia Tech –
A morph between two drawings of the same graph can be thought of as a continuous deformation between the two given drawings. In this talk we consider the algorithmic problem of morphing between any two planar drawings of a planar triangulation while preserving planarity during the morph. We outline two different solutions to the morphing problem. The first solution gives a strengthening of the result of Alamdari et al. where each step is a unidirectional morph. The second morphing algorithm finds a planar morph consisting of O(n²) steps between any two Schnyder drawings while remaining in an O(n)×O(n) grid, here n is the number of vertices of the graph. However, there are drawings of planar triangulations which are not Schnyder drawings, and for these drawings we show that a unidirectional morph consisting of O(n) steps that ends at a Schnyder drawing can be found. (Joint work with Penny Haxell and Anna Lubiw)

Gaussian fluctuations for linear statistics of Wigner matrices

Series
Stochastics Seminar
Time
Thursday, October 1, 2015 - 15:05 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Philippe Sosoe – Harvard University
In the 1970s, Girko made the striking observation that, after centering, traces of functions of large random matrices have approximately Gaussian distribution. This convergence is true without any further normalization provided f is smooth enough, even though the trace involves a number of terms equal to the dimension of the matrix. This is particularly interesting, because for some rougher, but still natural observables, like the number of eigenvalues in an interval, the fluctuations diverge. I will explain how such results can be obtained, focusing in particular on controlling the fluctuations when the function is not very regular.

Cycles lengths in graphs with large minimum degree

Series
Graph Theory Seminar
Time
Thursday, October 1, 2015 - 13:30 for 1 hour (actually 50 minutes)
Location
Skiles 006
Speaker
Jie Ma – University of Science and Technology of China
There has been extensive research on cycle lengths in graphs with large minimum degree. In this talk, we will present several new and tight results in this area. Let G be a graph with minimum degree at least k+1. We prove that if G is bipartite, then there are k cycles in G whose lengths form an arithmetic progression with common difference two. For general graph G, we show that G contains \lfloor k/2\rfloor cycles with consecutive even lengths, and in addition, if G is 2-connected and non-bipartite, then G contains \lfloor k/2\rfloor cycles with consecutive odd lengths. Thomassen (1983) made two conjectures on cycle lengths modulo a fixed integer k: (1) every graph with minimum degree at least k+1 contains cycles of all even lengths modulo k; (2) every 2-connected non-bipartite graph with minimum degree at least $k+1$ contains cycles of all lengths modulo k. These two conjectures, if true, are best possible. Our results confirm both conjectures! when k is even. And when k is odd, we show that minimum degree at least $+4 suffices. Moreover, our results derive new upper bounds of the chromatic number in terms of the longest sequence of cycles with consecutive (even or odd) lengths. This is a joint work with Chun-Hung Liu.

Pages