- You are here:
- GT Home
- Home
- News & Events

Series: ACO Student Seminar

If A is a set of n integers such that the sumset A+A = {a+b : a,b in A} has size 2n-1, then it turns out to be relatively easy to prove that A is an arithmetic progression {c, c+d, c+2d, c+3d, ..., c+(n-1)d}. But what if you only know something a bit weaker, say |A+A| < 10 n, say? Well, then there is a famous theorem due to G. Freiman that says that A is a "dense subset of a generalized arithmetic progression" (whatever that is -- you'll find out). Recently, this subject has been revolutionized by some remarkable results due to Tom Sanders. In this talk I will discuss what these are.

Series: ACO Student Seminar

Fourier PCA is Principal Component Analysis of the covariance matrix obtained after reweighting a distribution with a random Fourier weighting. It can also be viewed as PCA applied to the Hessian matrix of functions of the characteristic function of the underlying distribution. Extending this technique to higher derivative tensors and developing a general tensor decomposition method, we derive the following results: (1) a polynomial-time algorithm for general independent component analysis (ICA), not requiring the component distributions to be discrete or distinguishable from Gaussian in their fourth moment (unlike in the previous work); (2) the first polynomial-time algorithm for underdetermined ICA, where the number of components can be arbitrarily higher than the dimension; (3) an alternative algorithm for learning mixtures of spherical Gaussians with linearly independent means. These results also hold in the presence of Gaussian noise.

Series: ACO Student Seminar

In 2011, Rothvoß showed that there exists a 0/1 polytope such that any higher-dimensional polytope projecting to it must have a subexponential number of facets, i.e., its linear extension complexity is subexponential. The question as to whether there exists a 0/1 polytope having high PSD extension complexity was left open, i.e. is there a 0/1 polytope such that any spectrahedron projecting to it must be the intersection of a subexponential sized semideﬁnite cone and an aﬃne space? We answer this question in the aﬃrmative using a new technique to rescale semideﬁnite factorizations

Series: ACO Student Seminar

This is a review talk on an infinite dimensional relaxation of mixed integer programs (MIP) that was developed by Gomory and Johnson. We will discuss the relationship between cutting planes for the original MIP and its infinite dimensional relaxation. Time permitting, various structural results about the infinite dimensional problem and some open problems will be presented.

Series: ACO Student Seminar

Information-based complexity is an alternative to Turing complexity that is well-suited for understanding a broad class of convex optimization algorithms. The groundbreaking work of Nemirovski and Yudin provided the basis of the theory, establishing tight lower bounds on the running time of first-order methods in a number of settings. There has been a recent interest on these classical techniques, because of exciting new applications on Machine Learning, Signal Processing, Stochastic Programming, among others. In this talk, we will introduce the rudiments of the theory, some examples, and open problems. Based on joint work with Gábor Braun and Sebastian Pokutta.

Series: ACO Student Seminar

In algorithmic game theory, the price of anarchy framework studies efficiency loss in decentralized environments. In optimization and decision theory, the price of robustness framework explores the tradeoffs between optimality and robustness in the case of single agent decision making under uncertainty. We establish a connection between the two that provides a novel analytic framework for proving tight performance guarantees for distributed systems in uncertain environments.We present applications of this framework to novel variants of atomic congestion games with uncertain costs, for which we provide tight performance bounds under a wide range of risk attitudes. Our results establish that the individual's attitude towards uncertainty has a critical effect on system performance and should therefore be a subject of close and systematic investigation.

Series: ACO Student Seminar

A large variety of Constraint Satisfactoin Problems can be classified as
"computationally hard". In recent years researchers from statistical
mechanics have investigated such problems via non-rigorous methods. The
aim of this talk is to give a brief overview of this work, and of the
extent to which the physics ideas can be turned into rigorous
mathematics. I'm also going to point out various open problems.

Series: ACO Student Seminar

We will begin by formulating the Riemann-Roch theorem for graphs, due to
the speaker and Norine. We will then describe some refinements and
applications.
Refinements include a Riemann-Roch theorem for tropical curves, proved
by Gathmann-Kerber and Mikhalkin-Zharkov, and a Riemann-Roch theorem for
metrized complexes of curves, proved by Amini and the speaker.
Applications include a new proof by Cools-Draisma-Payne-Robeva of the
Brill-Noether theorem in algebraic geometry, a generalization by Amini
and the speaker of the Eisenbud-Harris theory of limit linear series,
and a new Chabauty-Coleman style bound for the number of rational points
on an algebraic curve over the rationals, proved recently by Katz and
Zureick-Brown.

Series: ACO Student Seminar

Understanding how the physiology of organisms arises through the dynamic interaction of the molecular constituents of life is an important goal of molecular systems biology, for which mathematical modeling can be very helpful. Different modeling strategies have been used for this purpose. Dynamic mathematical models can be broadly divided into two classes: continuous, such as systems of differential equations and their stochastic variants and discrete, such as Boolean networks and their generalizations. This talk will focus on the discrete modeling approach. Applications will include the study of stochasticity under this setting. No background in mathematical biology is required, and the talk will be accessible to a broad audience.

Series: ACO Student Seminar

In this talk, we are going to introduce Linearized Proximal Alternating Minimization Algorithm and its variants for total variation based variational model. Since the proposed method does not require any special inner solver (e.g. FFT or DCT), which is quite often required in augmented Lagrangian based approach (ADMM), it shows better performance for large scale problems. In addition, we briefly introduce new regularization method (nonconvex higher order total variation).