Seminars and Colloquia by Series

Friday, November 8, 2013 - 13:05 , Location: Skiles 005 , Gustavo Angulo , ISyE, Georgia Tech , Organizer:
In this talk, we introduce and study the forbidden-vertices problem. Given a polytope P and a subset X of its vertices, we study the complexity of linear optimization over the subset of vertices of P that are not contained in X. This problem is closely related to finding the k-best basic solutions to a linear problem. We show that the complexity of the problem changes significantly depending on how both P and X are described, that is, on the encoding of the input data. For example, we analyze the case where the complete linear formulation of P is provided, as opposed to the case where P is given by an implicit description (to be defined in the talk). When P has binary vertices only, we provide additional tractability results and linear formulations of polynomial size. Some applications and extensions to integral polytopes will be discussed. Joint work with Shabbir Ahmed, Santanu S. Dey, and Volker Kaibel.
Friday, November 1, 2013 - 13:05 , Location: Skiles 005 , Yingyu Liang , College of Computing, Georgia Tech , Organizer:
Recently, Bilu and Linial formalized an implicit assumption often made when choosing a clustering objective: that the optimum clustering to the objective should be preserved under small multiplicative perturbations to distances between points. They showed that for max-cut clustering it is possible to circumvent NP-hardness and obtain polynomial-time algorithms for instances resilient to large (factor O(\sqrt{n})) perturbations, and subsequently Awasthi et al. considered center-based objectives, giving algorithms for instances resilient to O(1) factor perturbations. In this talk, for center-based objectives, we present an algorithm that can optimally cluster instances resilient to (1+\sqrt{2})-factor perturbations, solving an open problem of Awasthi et al. For k-median, a center-based objective of special interest, we additionally give algorithms for a more relaxed assumption in which we allow the optimal solution to change in a small fraction of the points after perturbation. We give the first bounds known for k-median under this more realistic and more general assumption. We also provide positive results for min-sum clustering which is a generally much harder objective than center-based objectives. Our algorithms are based on new linkage criteria that may be of independent interest.
Friday, October 25, 2013 - 13:05 , Location: Skiles 005 , Ton Dieker , ISyE, Georgia Tech , Organizer:
This talk evolves around Markov functions, i.e., when a function of a Markov chain results in another Markov chain. We focus on two examples where this concept yields new results and insights: (1) the evolution of reflected stochastic processes in the study of stochastic networks, and (2) spectral analysis for a special high-dimensional Markov chain.
Friday, October 11, 2013 - 13:05 , Location: Skiles 005 , Jugal Garg , College of Computing, Georgia Tech , Organizer:
Although production is an integral part of the Arrow-Debreu market model, most of the work in theoretical computer science has so far concentrated on markets without production, i.e., the exchange economy. In this work, we take a significant step towards understanding computational aspects of markets with production. We first define the notion of separable, piecewise-linear concave (SPLC) production by analogy with SPLC utility functions. We then obtain a linear complementarity problem (LCP) formulation that captures exactly the set of equilibria for Arrow-Debreu markets with SPLC utilities and SPLC production, and we give a complementary pivot algorithm for finding an equilibrium. This settles a question asked by Eaves in 1975.  Since this is a path-following algorithm, we obtain a proof of membership of this problem in PPAD, using Todd, 1976. We also obtain an elementary proof of existence of equilibrium (i.e., without using a fixed point theorem), rationality, and oddness of the number of equilibria.  Experiments show that our algorithm runs fast on randomly chosen examples, and unlike previous approaches, it does not suffer from issues of numerical instability. Additionally, it is strongly polynomial when the number of goods or the number of agents and firms is constant. This extends the result of Devanur and Kannan (2008) to markets with production. Based on a joint work with Vijay V. Vazirani. 
Friday, September 27, 2013 - 13:05 , Location: Skiles 005 , Ernie Croot , School of Math, Georgia Tech , Organizer:
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.
Friday, September 13, 2013 - 13:05 , Location: Skiles 005 , Ying Xiao , College of Computing, Georgia Tech , Organizer:
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.
Wednesday, August 21, 2013 - 13:00 , Location: ISyE Executive classroom , Daniel Dadush , Courant Institute, NYU , Organizer:
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
Friday, April 26, 2013 - 13:05 , Location: Skiles 005 , Santanu Dey , ISyE, Georgia Tech , Organizer:
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. 
Friday, April 5, 2013 - 13:05 , Location: ISyE Executive classroom , Cristobal Guzman , ISyE, Georgia Tech , , Organizer:
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.
Friday, March 15, 2013 - 13:05 , Location: Skiles 005 , Georgios Piliouras , 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.