## Seminars and Colloquia by Series

Friday, March 15, 2013 - 13:05 , Location: Skiles 005 , , ECE, Georgia Tech , Organizer:
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.
Friday, March 1, 2013 - 13:05 , Location: Skiles 005 , Amin Coja-Oghlan , Goethe University Frankfurt/Main , Organizer:
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.
Friday, February 22, 2013 - 13:05 , Location: Skiles 005 , , School of Mathematics, Georgia Tech , Organizer:
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.
Friday, February 8, 2013 - 13:00 , Location: Skiles 005 , David Murrugarra , School of Math, Georgia Tech , , Organizer:
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.
Friday, February 1, 2013 - 13:00 , Location: Skiles 005 , Hyenkyun Woo , CSE, Georgia Tech , , Organizer:
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).
Wednesday, January 23, 2013 - 12:00 , Location: ISyE Executive classroom , Gustavo Angulo , Georgia Tech ISyE , Organizer:
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.
Friday, December 7, 2012 - 13:10 , Location: Skiles 005 , , College of Computing, Georgia Tech , Organizer:
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)
Friday, November 30, 2012 - 13:00 , Location: Skiles 005 , , College of Computing, Georgia Tech , Organizer:
Mechanism design for distributed systems is fundamentally concerned with aligning individual incentives with social welfare to avoid socially inefficient outcomes that can arise from agents acting autonomously. One simple and natural approach is to centrally broadcast non-binding advice intended to guide the system to a socially near-optimal state while still harnessing the incentives of individual agents. The analytical challenge is proving fast convergence to near optimal states, and we present the first results that carefully constructed advice vectors yield stronger guarantees.                                        We apply this approach to a broad family of potential games modeling vertex cover and set cover optimization problems in a distributed setting.  This class of problems is interesting because finding exact solutions to their optimization problems is NP-hard yet highly inefficient equilibria exist, so a solution in which agents simply locally optimize is not satisfactory.  We show that with an arbitrary advice vector, a set cover game quickly converges to an equilibrium with cost of the same order as the square of the social cost of the advice vector.  More interestingly, we show how to efficiently construct an advice vector with a particular structure with cost $O(\log n)$ times the optimal social cost, and we prove that the system quickly converges to an equilibrium with social cost of this same order.
Wednesday, November 21, 2012 - 12:00 , Location: ISyE Executive classroom , , ISyE, Georgia Tech , , Organizer:
Inpainting, deblurring and denoising images are common tasks required for a number of applications in science and engineering. Since the seminal work of Rudin, Osher and Fatemi, image regularization by total variation (TV) became a standard heuristic for achieving these tasks.                                                   In this talk, I will introduce the TV regularization model and some connections with sparse optimization and compressed sensing. Later, I will summarize some of the fastest existing methods for solving TV regularization.                                                                                                                                  Motivated by improving the super-linear (on the dimension) running time of these algorithms, we propose two heuristics for image regularization models: the first one is to replace the TV by the \ell^1 norm of the Laplacian, and the second is a new, to the best of our knowledge, approximation of the TV seminorm, based on a redundant parameterization of the gradient field.                                                 We prove that the latter regularizer is an O(log n) approximation of the TV seminorm. This proof is based on basic techniques from Discrete Fourier Analysis and an estimate of the fundamental solutions of the Laplace equation on a grid, due to Mangad.                                                                                  Finally, we present preliminary computational results for the three models, on mid-scale images.              This talk will be self-contained. Joint work with Arkadi Nemirovski.
Friday, November 16, 2012 - 13:00 , Location: Skiles 005 , , Georgia Tech, ISyE , Organizer:
We solve a 20-year old problem posed by M. Yannakakis and prove that there exists no polynomial-size linear program (LP) whose associated polytope projects to the traveling salesman polytope, even if the LP is not required to be symmetric. Moreover, we prove that this holds also for the maximum cut problem and the stable set problem. These results follow from a new connection that we make between one-way quantum communication protocols and semidefinite programming reformulations of LPs. (joint work with Samuel Fiorini, Serge Massar, Hans Raj Tiwary, and Ronald de Wolf)