Friday, September 4, 2009 - 15:00 , Location: Skiles 255 , Karthekeyan Chandrasekaran , College of Computing , Organizer: Prasad Tetali
Lovasz Local Lemma (LLL) is a powerful result in probability theory that states that the probability that none of a set of bad events happens is nonzero if the probability of each event is small compared to the number of events that depend on it. It is often used in combination with the probabilistic method for non-constructive existence proofs. A prominent application of LLL is to k-CNF formulas, where LLL implies that, if every clause in the formula shares variables with at most d \le 2^k/e other clauses then such a formula has a satisfying assignment. Recently, a randomized algorithm to efficiently construct a satisfying assignment was given by Moser. Subsequently Moser and Tardos gave a randomized algorithm to construct the structures guaranteed by the LLL in a very general algorithmic framework. We will address the main problem left open by Moser and Tardos of derandomizing their algorithm efficiently when the number of other events that any bad event depends on is possibly unbounded. An interesting special case of the open problem is the k-CNF problem when k = \omega(1), that is, when k is more than a constant.
Friday, August 21, 2009 - 15:00 , Location: Skiles 255 , Satoru Iwata , Kyoto University , Organizer: Prasad Tetali
In this lecture, I will explain the greedy approximation algorithm on submodular function maximization due to Nemhauser, Wolsey, and Fisher. Then I will apply this algorithm to the problem of approximating an monotone submodular functions by another submodular function with succinct representation. This approximation method is based on the maximum volume ellipsoid inscribed in a centrally symmetric convex body. This is joint work with Michel Goemans, Nick Harvey, and Vahab Mirrokni.
Wednesday, August 19, 2009 - 15:00 , Location: Skiles 255 , Satoru Iwata , Kyoto University , Organizer: Prasad Tetali
In this lecture, I will review combinatorial algorithms for minimizing submodular functions. In particular, I will present a new combinatorial algorithm obtained in my recent joint work with Jim Orlin.
Friday, August 14, 2009 - 15:05 , Location: Skiles 255 , Prof. Satoru Iwata , Kyoto University , Organizer: Prasad Tetali
In this lecture, I will explain connections between graph theory and submodular optimization. The topics include theorems of Nash-Williams on orientation and detachment of graphs.
Thursday, May 21, 2009 - 11:00 , Location: Skiles 255 , Joshua Cooper , Department of Mathematics, University of South Carolina , Organizer: Prasad Tetali
We consider the Ulam "liar" and "pathological liar" games, natural and well-studied variants of "20 questions" in which the adversarial respondent is permitted to lie some fraction of the time. We give an improved upper bound for the optimal strategy (aka minimum-size covering code), coming within a triply iterated log factor of the so-called "sphere covering" lower bound. The approach is twofold: (1) use a greedy-type strategy until the game is nearly over, then (2) switch to applying the "liar machine" to the remaining Berlekamp position vector. The liar machine is a deterministic (countable) automaton which we show to be very close in behavior to a simple random walk, and this resemblance translates into a nearly optimal strategy for the pathological liar game.
Friday, April 24, 2009 - 15:00 , Location: Skiles 255 , Mokshay Madiman , Department of Statistics, Yale University , Organizer: Prasad Tetali
We develop an information-theoretic foundation for compound Poisson approximation and limit theorems (analogous to the corresponding developments for the central limit theorem and for simple Poisson approximation). First, sufficient conditions are given under which the compound Poisson distribution has maximal entropy within a natural class of probability measures on the nonnegative integers. In particular, it is shown that a maximum entropy property is valid if the measures under consideration are log-concave, but that it fails in general. Second, approximation bounds in the (strong) relative entropy sense are given for distributional approximation of sums of independent nonnegative integer valued random variables by compound Poisson distributions. The proof techniques involve the use of a notion of local information quantities that generalize the classical Fisher information used for normal approximation, as well as the use of ingredients from Stein's method for compound Poisson approximation. This work is joint with Andrew Barbour (Zurich), Oliver Johnson (Bristol) and Ioannis Kontoyiannis (AUEB).
Friday, April 17, 2009 - 15:00 , Location: Skiles 255 , Guantao Chen , Georgia State University , Organizer: Prasad Tetali
Let G be a graph and K be a field. We associate to G a projective toric variety X_G over K, the cut variety of the graph G. The cut ideal I_G of the graph G is the ideal defining the cut variety. In this talk, we show that, if G is a subgraph of a subdivision of a book or an outerplanar graph, then the minimal generators are quadrics. Furthermore we describe the generators of the cut ideal of a subdivision of a book.
Tuesday, April 7, 2009 - 11:00 , Location: Skiles 255 , Adam Marcus , Yale University , Organizer: Prasad Tetali
The entropy function has a number of nice properties that make it a useful counting tool, especially when one wants to bound a set with respect to the set's projections. In this talk, I will show a method developed by Mokshay Madiman, Prasad Tetali, and myself that builds on the work of Gyarmati, Matolcsi and Ruzsa as well as the work of Ballister and Bollobas. The goal will be to give a black-box method for generating projection bounds and to show some applications by giving new bounds on the sizes of Abelian and non-Abelian sumsets.
Graph Patches (Partial Sparsifiers) and their applications to designing cost-effective, expanding networksFriday, April 3, 2009 - 15:00 , Location: Skiles 255 , Alexandra Kolla , UC Berkeley , Organizer: Prasad Tetali
I will present an approximation algorithm for the following problem: Given a graph G and a parameter k, find k edges to add to G as to maximize its algebraic connectivity. This problem is known to be NP-hard and prior to this work no algorithm was known with provable approximation guarantee. The algorithm uses a novel way of sparsifying (patching) part of a graph using few edges.
Friday, March 27, 2009 - 15:00 , Location: Skiles 255 , Graeme Kemkes , UCSD , Organizer: Prasad Tetali
Choose a graph uniformly at random from all d-regular graphs on n vertices. We determine the chromatic number of the graph for about half of all values of d, asymptotically almost surely (a.a.s.) as n grows large. Letting k be the smallest integer satisfying d < 2(k-1)\log(k-1), we show that a random d-regular graph is k-colorable a.a.s. Together with previous results of Molloy and Reed, this establishes the chromatic number as a.a.s. k-1 or k. If furthermore d>(2k-3)\log(k-1) then the chromatic number is a.a.s. k. This is an improvement upon results recently announced by Achlioptas and Moore. The method used is "small subgraph conditioning'' of Robinson and Wormald, applied to count colorings where all color classes have the same size. It is the first rigorously proved result about the chromatic number of random graphs that was proved by small subgraph conditioning. This is joint work with Xavier Perez-Gimenez and Nick Wormald.