October 19, 2012
Title: A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities
Speaker: Vijay Vazirani, Georgia Institute of Technology
Abstract:
The simplest way to describe our result is by analogy with the Lemke-Hawson complementary pivot algorithm for 2-player Nash equilibrium. This path-following algorithm gives a direct proof of membership of the problem in the class PPAD, and is a practical algorithm despite PPAD-completeness of the problem. It also yields deep structural insights, such as oddness of the number of equilibria.
Our algorithm accomplishes the above for the problem of finding an equilibrium for an Arrow-Debreu market under separable, piecewise-linear concave utilities. Our key steps are deriving an LCP that captures the set of equilibria of the market, and solving it using Lemke's algorithm; the latter involves showing that the polyhedron associated with the LCP has no secondary rays.
Our result answers an open problem of Eaves from 1975 and a recent open problem of Vazirani and Yannakakis.
Based on the following joint paper with Jugal Garg, Ruta Mehta and Milind Sohini: http://www.cc.gatech.edu/~vazirani/SPLC.pdf
October 12, 2012
Title: Reconstructing Strings from Random Traces
Speaker: Sampath Kannan, University of Pennsylvania
Abstract:
In a deletion channel each transmitted symbol is deleted independently with some probability p. We consider settings where no error correction is allowed and where the receiver does not know where the gaps in the transmitted string are. We ask what deletion probabilities can be tolerated for reconstruction with polynomially many retransmissions. We consider two variants of the problem – one where we want worst-case reconstruction and one where we want reconstruction with high probability and survey the best known bounds for these two variants.
September 28, 2012
Title: Beck's Three Permutations Conjecture: A Counterexample and Some Consequences
Speaker: Alantha Newman, Rutgers University
[No Video]
Abstract:
Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations. In 1982, Beck conjectured that the discrepancy of this set system is O(1). In other words, the conjecture says that each integer from 1 through n can be colored either red or blue so that the number of red and blue integers in each interval of each permutations differs only by a constant. (The discrepancy of a set system based on two permutations is at most two.)
We will present a counterexample to this conjecture: for any positive integer n = 3^k, we construct three permutations whose corresponding set system has discrepancy Omega(log(n)).
Our work was inspired by an intriguing paper from SODA 2011 by Eisenbrand, Palvolgyi and Rothvoss, who show a surprising connection between the discrepancy of three permutations and the bin packing problem: They show that Beck's conjecture implies a constant worst-case bound on the additive integrality gap for the Gilmore-Gomory LP relaxation for bin packing in the special case when all items have sizes strictly between 1/4 and 1/2, also known as the three partition problem. Our counterexample shows that this approach to bounding the additive integrality gap for bin packing will not work. We can, however, prove an interesting implication of our construction in the reverse direction: there are instances of bin packing and corresponding optimal basic feasible solutions for the Gilmore-Gomory LP relaxation such that any packing that contains only patterns from the support of these solutions requires at least OPT + Omega(log(m)) bins, where m is the number of items.
Joint work with Ofer Neiman and Aleksandar Nikolov.