Georgia Institute of Technology

TBA

Wed, 01/20/2010 - 4:30pm, Skiles 255

Amin Saberi, Stanford University        Organizer: Robin Thomas

Extremal graph theory and related areas

Thu, 11/12/2009 - 4:30pm, 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.***

CANCELLED -- Sparse matrices, sparse signals, and sparse algorithms

Tue, 04/21/2009 - 4:30pm, 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.

The Linear Complementarity Problem, Lemke Algorithm, Perturbation, and the Complexity Class PPAD

Wed, 04/01/2009 - 4:30pm, 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.

A Survey of Results for Deletion Channels and Related Synchronization Channels

Wed, 01/21/2009 - 4:30pm, 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.