Thursday, March 18, 2010 - 16:30 , Location: Skiles 255 , Jaroslav Nesetril , Charles University, Prague , Organizer: Robin Thomas
***Refreshments at 4PM in Skiles 236.***
Forbidding (undirected or directed) paths in graphs, what can be easier? Yet we show that in the context of coloring problems (CSP) and structural graph theory, this is related to the notions tree depth, (restricted) dualities, bounded expansion and nowhere dense classes with applications both in and out of combinatorics.
Wednesday, February 17, 2010 - 16:30 , Location: Skiles 255 (Refreshments at 4pm in Skiles 236) , David Gamarnik , Professor, M.I.T. , firstname.lastname@example.org , Organizer: Prasad Tetali
We establish the existence of scaling limits for several combinatorial optimization models on Erdos-Renyi and sparse random regular graphs. For a variety of models, including maximum independent sets, MAX-CUT, coloring and K-SAT, we prove that the optimal value appropriately rescaled, converges to a limit with high probability (w.h.p.), as the size of the underlying graph divergesto infinity. For example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p. thus resolving an open problem. Our approach is based on developing a simple combinatorial approach to an interpolation method developed recently in the statistical physics literature. Among other things, theinterpolation method was used to prove the existence of the so-called free energy limits for several spin glass models including Viana-Bray and random K-SAT models. Our simpler combinatorial approach allows us to work with the zero temperature case (optimization) directly and extend the approach to many other models. Additionally, using our approach, we establish the large deviationsprinciple for the satisfiability property for constraint satisfaction problems such as coloring, K-SAT and NAE(Not-All-Equal)-K-SAT. The talk will be completely self-contained. No background on random graph theory/statistical physics is necessary. Joint work with Mohsen Bayati and Prasad Tetali
In search of a thin tree - new approximation algorithms for the asymmetric traveling salesman problemThursday, January 14, 2010 - 16:30 , Location: Skiles 255 , Amin Saberi , Stanford University , Organizer: Robin Thomas
Refreshments at 4:00PM in Skiles 236
I will talk about new approximation algorithms for the Asymmetric Traveling Salesman Problem (ATSP) when the costs satisfy the triangle inequality. Our approach is based on constructing a "thin" spanning tree from the solution of a classical linear programming relaxation of the problem and augmenting the tree to an Eulerian subgraph. I will talk about Goddyn's conjecture on the existence of such trees and its relations to nowhere-zero flows. I will present an O(log n/log log n) approximation algorithm that uses a new randomized rounding method. Our rounding method is based on sampling from a distribution and could be of independent interest. Also, I will talk about the special case where the underlying undirected graph of the LP relaxation of the problem has bounded genus. This is the case for example, when the distance functions are shortest paths in a city with few bridges and underpasses. We give a constant factor approximation algorithm in that case. The first result is a joint work with A. Asadpour, M. Goemans, A. Madry and S. Oveis Gharan, and the second result is a joint work with S. Oveis Gharan.
Thursday, November 12, 2009 - 16:30 , Location: Skiles 255 , Miklos Simonovits , Alfred Renyi Institute, Budapest, Hungary , Organizer: Robin Thomas
In my talk I will give a survey on the rise and early development of Extremal Graph Theory, one of the large areas in Discrete Mathematics.I will give a description of the asymptotic solution of extremal graph problems for ordinary graphs, describe the stability method and expose the difficulties connected to hypergraph extremal problems.I will expose several unsolved problems in the field, and move on to some new results.I will also describe the connection of the field to several other areas of Discrete Mathematics, like to Ramsey Theory,Random graphs, Regularity lemma, Quasi-randomness, etc.I will also mention some applications of extremal graph theory. The lecture will be a non-technical one.***Refreshments at 4PM in Skiles 236.***
Tuesday, April 21, 2009 - 16:30 , Location: Skiles 255 , Anna Gilbert , University of Michigan, Ann Arbor , Organizer: Prasad Tetali
The past 10 years have seen a confluence of research in sparse approximation amongst computer science, mathematics, and electrical engineering. Sparse approximation encompasses a large number of mathematical, algorithmic, and signal processing problems which all attempt to balance the size of a (linear) representation of data and the fidelity of that representation. I will discuss several of the basic algorithmic problems and their solutions, focusing on special classes of matrices. I will conclude with an application in biological testing.
Wednesday, April 1, 2009 - 16:30 , Location: Klaus 1116E , Ilan Adler , UC Berkeley , Organizer: Robin Thomas
One of the most interesting aspects of the Linear Complementarity Problem (LCP) is its range from relatively easy problems such as linear and convex quadratic programming problems to NP-hard problems. A major effort in LCP theory had been the study of the Lemke algorithm, a simplex-like algorithm which is guaranteed to terminate in finite number of iterations but not necessarily with a solution (or a certificate that no solution exists). Over the years, many subclasses of LCP were proven to be workable by the Lemke algorithm. Those subclasses were often characterized as ‘nice’ even when no polynomial upper bound for the algorithm was known to exist. In fact, for most of these classes, instances with exponential number of steps had been discovered. In this talk, I’ll discuss the close connection between these classes and the PPAD (Polynomial-time Parity Argument Directed) complexity class. The discovery that computing Nash equilibrium (which is an LCP) is PPAD complete is particularly significant in analyzing the complexity of LCP. I’ll also discuss the LCP reduction-via-perturbation technique and its relation to the PPAD class and the Lemke Algorithm. This talk is based on a joint work with Sushil Verma.
Wednesday, January 21, 2009 - 16:30 , Location: Klaus , Michael Mitzenmacher , Harvard University , Organizer: Robin Thomas
We describe recent progress in the study of the binary deletion channel and related channels with synchronization errors, including a clear description of many open problems in this area. As an example, while the capacity of the binary symmetric error channel and the binary erasure channel have been known since Shannon, we still do not have a closed-form description of the capacity of the binary deletion channel. We highlight a recent result that shows that the capacity is at least (1-p)/9 when each bit is deleted independently with fixed probability p.