Seminars and Colloquia by Series

On the existence of 0/1 polytopes with high semidefinite extension complexity

Series
ACO Student Seminar
Time
Wednesday, August 21, 2013 - 13:00 for 1 hour (actually 50 minutes)
Location
ISyE Executive classroom
Speaker
Daniel Dadush – Courant Institute, NYU
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 semidefinite cone and an affine space? We answer this question in the affirmative using a new technique to rescale semidefinite factorizations

Cutting Planes for mixed integer programs via infinite dimensional relaxations

Series
ACO Student Seminar
Time
Friday, April 26, 2013 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Santanu Dey – ISyE, Georgia Tech
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.

Tutorial: Information-based complexity of convex optimization

Series
ACO Student Seminar
Time
Friday, April 5, 2013 - 13:05 for 1 hour (actually 50 minutes)
Location
ISyE Executive classroom
Speaker
Cristobal Guzman – ISyE, Georgia Tech –
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.

Risk Sensitivity of Price of Anarchy under Uncertainty

Series
ACO Student Seminar
Time
Friday, March 15, 2013 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Georgios Piliouras – ECE, Georgia Tech
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.

Random Constraint Satisfaction Problems

Series
ACO Student Seminar
Time
Friday, March 1, 2013 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Amin Coja-Oghlan – Goethe University Frankfurt/Main
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.

The Riemann-Roch theorem for graphs and applications

Series
ACO Student Seminar
Time
Friday, February 22, 2013 - 13:05 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Matt Baker – School of Mathematics, Georgia Tech
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.

Discrete models in systems biology

Series
ACO Student Seminar
Time
Friday, February 8, 2013 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
David Murrugarra – School of Math, Georgia Tech –
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.

Alternating minimization algorithm based optimization method for Total Variation

Series
ACO Student Seminar
Time
Friday, February 1, 2013 - 13:00 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Hyenkyun Woo – CSE, Georgia Tech –
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).

Forbidding solutions in (integer) linear programming

Series
ACO Student Seminar
Time
Wednesday, January 23, 2013 - 12:00 for 1 hour (actually 50 minutes)
Location
ISyE Executive classroom
Speaker
Gustavo Angulo – Georgia Tech ISyE
In this talk we consider the problem of finding basic solutions to linear programs where some vertices are excluded. We study the complexity of this and related problems, most of which turn out to be hard. On the other hand, we show that forbidding vertices from 0-1 polytopes can be carried out with a compact extended formulation. A similar result holds for integer programs having a box-integrality property. We discuss some applications of our results.

Slow Mixing for the Hard-Core Model on Z^2

Series
ACO Student Seminar
Time
Friday, December 7, 2012 - 13:10 for 1 hour (actually 50 minutes)
Location
Skiles 005
Speaker
Dana Randall – College of Computing, Georgia Tech
The hard-core model has attracted much attention across several disciplines, representing lattice gases in statistical physics and independent sets in discrete mathematics and computer science. On finite graphs, we are given a parameter \lambda, and an independent set I arises with probability proportional to \lambda^{|I|}. We are interested in determining the mixing time of local Markov chains that add or remove a small number of vertices in each step. On finite regions of Z^2 it is conjectured that there is a phase transition at some critical point \lambda_c that is approximately 3.79. It is known that local chains are rapidly mixing when \lambda < 2.3882. We give complementary results showing that local chains will mix slowly when \lambda > 5.3646 on regions with periodic (toroidal) boundary conditions and when \lambda > 7.1031 with non-periodic (free) boundary conditions. The proofs use a combinatorial characterization of configurations based on the presence or absence of fault lines and an enumeration of a new class of self-avoiding walks called taxi walks. (Joint work with Antonio Blanca, David Galvin and Prasad Tetali)

Pages