Theory Reading Group

Szemeredi regularity lemma

Li Fan

Szemeredi's Regularity Lemma is an important tool in discrete mathematics. It says that, in some sense, all graphs can be approximated by random-looking graphs. Therefore the lemma helps in proving theorems for arbitrary graphs whenever the corresponding result is easy for random graphs. Recently quite a few new results were obtained by using the Regularity Lemma, and also some new variants and generalizations appeared. In this survey we describe some typical applications and some generalizations.

Date: 20 Nov 2009 Time: 12:30 pm Venue: SHB 1021

Polar codes

Sidharth Jaggi

The problem of finding "good" channel codes -- i.e., codes with "good" properties that enable almost error-free transmission at "high" rates over noisy channels -- has been essentially open since Shannon started the ball rolling in 1948. In particular, though good codes are known in practice, their performance cannot be theoretically guaranteed. Codes with *provably*asymptotically rate-optimal performance *and* low computational complexity were not known until recently.

Polar codes have recently attracted much attention in the information theory community -- they start bridging the gap between theory and practice. Over the last couple of years they've been used to construct good codes for a large number of channel and source coding problems.

Date: 13 Nov 2009 Time: 12:30 pm Venue: SHB 1021

The intersection of two halfspaces has high threshold degree

Shengyu Zhang

I'll talk about Sherstov's recent FOCS paper.

Date: 6 Nov 2009 Time: 12:30 pm Venue: SHB 1021

Algebraic algorihm for matching problems

Leo Cheung

We have learned various ways to find matching on graphs.

A long while ago Edmonds suggested a randomized algorithm to check if a perfect matching exists in a bipartite graph in O(n^\omega) time, where O(n^\omega) is the time required to compute matrix multiplication. This is done by computing determinants of the so called Edmonds matrix. And Tutte has extended the idea to general graphs. So people start thinking if these ideas can be extended to actually find out a matching if one exists. And finally this is solved by Mucha and Sankowski[2] with algorithm in O(n^\omega) time, and the algorithm is further simplified by Nick Harvey.

Date: 23,30 Oct 2009 Time: 12:30 pm Venue: SHB 1021

Perfect matchings in regular bipartite graphs

Lap Chi Lau

In August, Sanjeev Khanna presented in an ITCSC seminar an O(n^1.5)-algorithm to find a perfect matching in a regular bipartite graph. In this talk I will present their new O(nlogn)-algorithm for the same problem. Don't worry if you did not attend his talk, since the O(nlogn) algorithm is completely different, and furthermore it is very simple and elegant. I will also briefly review some previous work about matchings.

Date: 16 Oct 2009 Time: 12:30 pm Venue: SHB 1021

Proofs of conjectures in random assignment problem

Chandra Nair

Disclaimer: This is not a talk on information theory, it is a talk on matchings in bipartite graphs. This is mostly work I had done during my PhD years, and a field I left altogether subsequently for a break.

Abstract: This talk deals with the proof of conjectures about weights of the minimum weighted matchings in complete bipartite graphs with random edge costs. What I wish to do in this talk is the following:

1. give an outline of the proof

2. present some new combinatorial properties of matchings that play a key role. There are many properties used, but I would classify only two of them as non-trivial. I will use one of the non-trivial facts to give a proof of the second non-trivial fact.

History and Problem description

Consider an n x n bipartite graph whose edge weights are drawn i.i.d. from some distribution (say that has a density equal 1 at origin like Uniform[0,1] or exp(1)). Let An denote the weight of the minimum weight matching (weight of a matching is sum of the edge weights of the corresponding edges). The behavior of An has been investigated since late 60s.

Upper bounds:

In 1979 Walkup showed that An <= 3 whp for very large n; in 1984 Karp improved the upper bound to An <= 2. It has been "alleged" by Rajeev Motwani? during my thesis defence that Karp knew at this time that the limiting value should be \pi^2/6 even before it was formally conjectured by Mezard and Parisi, two physicists, a year later. Coppersmith and Sorkin improved the upper bound to 1.98 in 1998. In 1992 David Aldous showed that the lim An exists (and depends only on the value of the density at the origin) and in 2001 proved that it is indeed \pi^2/6.

Lower bounds:

In 1979 Walkup showed a lower bound of 1 + 1/e. It was improved by Goemans and Kodialam to 1.41 (sqrt{2}) and later to 1.51 by Olin, all around 1991-1993.

Exact Conjectures for finite problems:

1. The following exact conjecture is formally attributed to Parisi (1998): If the edge weights are drawn from exp(1) distribution, in particular, then a more remarkable fact may hold:

E(An) = 1 + 1/2^2 + ... + 1/n^2

2. Coppersmith and Sorkin (1998) generalized this exact conjecture to smallest matchings of size k in complete m * n bipartite graphs with iid edge weights drawn from exp(1)

3. There were more general conjectures by:

a) Linusson and Wastlund (2000) about the expected decrease in weight of the smallest matching if certain entries were made zero.

b) Buck, Chan, and Robbins (2000) about the weight of the smallest matching if the eqdewights had means given by a rank 1 matrix.

c) Sharma and Prabhakar about distributions of the differences in weights of some matchings in n-1 \times n matrix. They showed that if these distributions were true, then Parisi conjecture holds.

d) Nair (aka myself) - motivated by conjectures of Sharma and Prabhakar - about distributions of the differences in weights of some matchings in general m \times n matrix. Showed showed that if these distributions were true, then both Parisi conjecture and Coppersmith Sorkins.

Proofs of conjectures and subsequent work:

1. Dotsenko (2000) claimed a proof of Parisi finite conjecture. However this argument had a critical gap.

2. In 2003 March, Linusson and Wastlund announced a proof of their generalizations of conjectures (a) and Nair, Prabhakar and Sharma announced the proof of their conjectures b) and c). These were correlated announcements but completely independent proofs of different facts that both imply Parisi conjectures.

3. In my thesis, I close the gap of the argument by Dotsenko using the machinery developed.

4. In reference 3 below, wastlund shows that the results in our paper could be used to related matchings to shortest path problems and recover some known results in an independent manner.

Some references:

The following papers can be downloaded from my website:

1. Proofs of the Parisi and Coppersmith-Sorkin conjectures in the random assignment problem, C. Nair. Ph.D. Thesis, Stanford University, June 2005.

2. Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures, C. Nair, B. Prabhakar, and M. Sharma. Random Structures and Algorithms, vol. 27(4), pp. 413-444, 2005. Proceedings of the IEEE Foundations of Computer Science (FOCS), pp. 168-178, 2003.

The following papers can be downloaded at the web-page of Johan Wastlund:

3. Random assignment and shortest path problems, Invited paper in Proceedings of the Fourth Colloquium on Mathematics and Computer Science, Algorithms, Trees, Combinatorics and Probabilities, September 18-22, 2006, Institut ie Cartan, Nancy, France.

4. A simple proof of the Parisi and Coppersmith-Sorkin formulas for the random assignment problem, Linkping Studies in Mathematics No. 6 (2005).

5. A simple proof of the Parisi and Coppersmith-Sorkin formulas for the random assignment problem, Linkping Studies in Mathematics No. 6 (2005).

Date: 9 Oct 2009 Time: 12:30 pm Venue: SHB 1021

On the structure of arithmetic circuits and formulas

Andrej Bogdanov

Boolean circuit lower bounds are notoriously hard to prove. Arithmetic circuit lower bounds seem a bit more tractable. What is the difference? In the 1970s and 1980s, Hyafil, Valiant, Skyum and others proved some structural results for arithmetic circuits and formulas which are apparently the cornerstone of all known lower bounds. I will tell you about these results and (if I learn enough by Friday) talk about some real lower bounds.

The presentation is inspired by Amir Yehudayoff's recent talk in Princeton: [pdf]

Date: 2 Oct 2009 Time: 12:30 pm Venue: SHB 1021

Forbidden permutation submatrices: the Marcus-Tardos proof of Stanley-Wilf conjecture

Jesse Zhang

The Stanley-Wilf conjecture was raised in 1993 on Erdos' 80th birthday [2], that the number of n-permutations avoiding a k-permutation $\sigma$ $F(n, \sigma) \le [ c_{\sigma} ]^n $. Attempts to attack (part of) the problem has been made by numerous great minds, until a "0-th year grad student" [1] Adam Marcus and Gabor Tardos gave a mind-disturbingly simple proof that a high school grad can (almost, if he knows linear recurrence or can cheat with master theorem) read.

Date: 25 Sept 2009 Time: 12:30 pm Venue: SHB 1027

Theory Group