Seminars and Colloquia by Series

Friday, April 6, 2012 - 13:00 , Location: Skiles 005 , , Georgia Tech, School of Mathematics , Organizer:
Consider a series of n single-server queues each with unlimited waiting space and FIFO discipline. At first the system is empty, then m customers are placed in the first queue. The service times of all the customers at all the queues are iid. We are interested in the exit time of the last customer from the last server and that's when queues meet random matrices and GUEs. If the number of customers is a small fractional power of the number of servers, and as such customers stay within a tube, that's when queues encounter Tracy and Widom. This talk will be self contained and accessible to graduate students.
Friday, March 30, 2012 - 13:00 , Location: Skiles 005 , Ning Tan , School of Math, Georgia Tech , , Organizer:
In a celebrated result, Raghavendra [Rag08] showed that, assuming Unique Game Conjecture, every Max-CSP problem has a sharp approximation threshold that matches the integrality gap of a natural SDP relaxation. Raghavendra and Steurer [RS09] also gave a simple and unified framework for optimally approximating all the Max-CSPs.In this work, we consider the problem of approximating CSPs with global cardinality constraints. For example, Max-Cut is a boolean CSP where the input is a graph $G = (V,E)$ and the goal is to find a cut $S \cup \bar S = V$ that maximizes the number of crossing edges, $|E(S,\bar S)|$. The Max-Bisection problem is a variant of Max-Cut with an additional global constraint that each side of the cut has exactly half the vertices, i.e., $|S| = |V|/2$. Several other natural optimization problems like Small Set Expansion, Min Bisection and approximating Graph Expansion can be formulated as CSPs with global constraints.In this talk, I will introduce a general approach towards approximating CSPs with global constraints using SDP hierarchies. To demonstrate the approach, I will present an improved algorithm for Max-Bisection problem that achieves the following:- Given an instance of Max-Bisection with value $1-\epsilon$, the algorithm finds a bisection with value at least $1-O(\sqrt{\epsilon})$ with running time $O(n^{poly(1/\eps)})$. This approximation is near-optimal (up to constant factors in $O()$) under the Unique Games Conjecture.- Using computer-assisted proof, we show that the same algorithm also achieves a 0.85-approximation for Max-Bisection, improving on the previous bound of 0.70 (note that it is UGC-hard to approximate better than 0.878 factor). As an attempt to prove matching hardness result, we show a generic conversion from SDP integrality gap to dictatorship test for any CSP with global cardinality constraints. The talk is based on joint work with Prasad Raghavendra.
Friday, March 16, 2012 - 13:00 , Location: Executive classroom, ISyE Main Building , , CoC, Georgia Tech , , Organizer:
I  present a new class of vertex cover and set cover games, with the price of anarchy bounds matching the best known constant factor approximation guarantees for the centralized optimization problems for linear and also for submodular costs. In particular, the price of anarchy is 2 for vertex cover. The basic intuition is that the members of the vertex cover form a Mafia that has to "protect" the graph, and may ask ransoms from their neighbors in exchange for the protection. These ransoms turn out to capture a good dual solution to the linear programming relaxation. For linear costs we also exhibit linear time best response dynamics that converge that mimic the classical greedy approximation algorithm of Bar-Yehuda and Even. This is a joint work with Georgios Piliouras and Tomas Valla.
Friday, March 9, 2012 - 13:00 , Location: Executive classroom, ISyE Main Building , David Goldberg , ISyE , , Organizer:
Recently, there has been great interest in understanding the fundamental limits of our ability to sample from the independent sets (i.s.) of a graph.  One approach involves the study of the so-called hardcore model, in which each i.s. is selected with probability proportional to some fixed activity $\lambda$ raised to the cardinality of the given i.s.  It is well-known that for any fixed degree $\Delta$, there exists a critical activity $\lambda_{\Delta}$ s.t. for all activities below $\lambda_{\Delta}$, the sampled i.s. enjoys a long-range independence (a.k.a. uniqueness) property when implemented on graphs with maximum degree $\Delta$, while for all activities above $\lambda_{\Delta}$, the sampled i.s. exhibits long-range dependencies.  Such phase transitions are known to have deep connections to the inherent computational complexity of the underlying combinatorial problems.  In this talk, we study a family of measures which generalizes the hardcore model by taking more structural information into account, beyond just the number of nodes belonging to the i.s., with the hope of further probing the fundamental limits of what we can learn about the i.s. of a graph using only local information.  In our model, the probability assigned to a given i.s. depends not only on its cardinality, but also on how many excluded nodes are adjacent to exactly $k$ nodes belonging to the i.s., for each $k$, resulting in a parameter for each $k$.  We generalize the notion of critical activity to these neighborly measures", and give necessary and sufficient conditions for long-range independence when certain parameters satisfy a log-convexity(concavity) requirement.  To better understand the phase transitions in this richer model, we view the classical critical activity as a particular point in the parameter space, and ask which directions can one move and still maintain long-range independence.  We show that the set of all such directions of uniqueness” has a simple polyhedral description, which we use to study how moving along these directions changes the probabilities associated with the sampled i.s.  We conclude by discussing implications for choosing how to sample when trying to optimize a linear function of the underlying probabilities.
Friday, March 2, 2012 - 13:00 , Location: TBA , Linji Yang , CoC, Georgia Tech , Organizer:
In this seminar, I will talk about a few recent developments in the random colorings, random weighted independent sets and other 2-spin models on different classes of graphs such as the square lattices and the triangular free graphs. I will focus on the so-called spatial mixing property of these models and discuss about the consequences (e.g., fast mixing of the Markov chains) of the spatial mixing property as well as the techniques of proving it.
Friday, February 24, 2012 - 13:00 , Location: Klaus 1116W , , CoC, Georgia Tech , Organizer:
I will show a new approach based on the discrepancy of the constraint matrix to verify integer feasibility of polytopes. I will then use this method to show a threshold phenomenon for integer feasibility of random polytopes. The random polytope model that we consider is P(n,m,x0,R) - these are polytopes in n-dimensional space specified by m "random" tangential hyperplanes to a ball of radius R centered around the point x0. We show that there exist constants c_1 < c_2 such that with high probability, the random polytope P(n,m,x0=(0.5,...,0.5),R) is integer infeasible if R is less than c_1sqrt(log(2m/n)) and the random polytope P(n,m,x0,R) is integer feasible for every center x0 if the radius R is at least c_2sqrt(log(2m/n)). Thus, a transition from infeasibility to feasibility happens within a constant factor increase in the radius. Moreover, if the polytope contains a ball of radius Omega(log (2m/n)), then we can find an integer solution with high probability (over the input) in randomized polynomial time. This is joint work with Santosh Vempala.
Friday, February 17, 2012 - 13:00 , Location: Skiles 005 , , Georgia Tech, School of Mathematics , , Organizer:
I will define planted distributions of random structures and give plenty of examples in different contexts: from balls and bins, to random permutations, to random graphs and CSP's.  I will give an idea of how they are used and why they are interesting.  Then I'll focus on one particular problem: under what conditions can you distinguish a planted distribution from the standard distribution on a random structure and how can you do it?
Friday, February 10, 2012 - 13:00 , Location: TBD , , School of Computer Science , Organizer:
I'll give a high-level tour of how lattices are providing a powerful new mathematical foundation for cryptography. Lattices provide simple, fast, and highly parallel cryptoschemes that, in contrast with many of today's popular methods (like RSA and elliptic curves), even appear to remain secure against quantum computers. No background in lattices, cryptography, or quantum computers will be necessary -- you only need to know how to add and multiply vectors and matrices.
Friday, February 3, 2012 - 13:00 , Location: Executive classroom, ISyE Main Building , , Georgia Tech, School of Industrial and Systems Engineering , Organizer:
A fundamental result in the geometry of numbers states that any lattice free convex set in R^n has integer width bounded by a function of dimension, i.e. the so called Flatness Theorem for Convex Bodies. This result provides the theoretical basis for the polynomial solvability of Integer Programs with a fixed number of (general) integer variables. In this work, we provide a simplified proof of the Flatness Theorem with tighter constants. Our main technical contribution is a new tight bound on the smoothing parameter of a lattice, a concept developed within lattice based cryptography which enables comparisons between certain discrete distributions over integer points with associated continuous Gaussian distributions. Based on joint work with Kai-Min Chung, Feng Hao Liu, and Christopher Peikert.
Wednesday, April 28, 2010 - 13:30 , Location: ISyE Executive Classroom , Karthik Chandrasekaran , CS ACO , Organizer:
Abstract: A hitting set for a collection of sets T is a set that has a non-empty intersection with eachset in T; the hitting set problem is to find a hitting set of minimum cardinality. Motivated bythe fact that there are instances of the hitting set problem where the number of subsets to behit is large, we introduce the notion of implicit hitting set problems. In an implicit hitting setproblem the collection of sets to be hit is typically too large to list explicitly; instead, an oracleis provided which, given a set H, either determines that H is a hitting set or returns a set inT that H does not hit. I will show a number of examples of classic implicit hitting set problems,and give a generic algorithm for solving such problems exactly in an online model.I will also show how this framework is valuable in developing approximation algorithms by presenting a simple on-line algorithm for the minimum feedback vertex set problem. In particular, our algorithm gives an approximation factor of 1+ 2 log(np)/(np) for the random graph G_{n,p}.Joint work with Richard Karp, Erick Moreno-Centeno (UC, Berkeley) and Santosh Vempala (Georgia Tech).