Lower Bounds on Monotone Circuit Complexity

Shagnik Das

One of the more fruitful attempts to separate P and NP has come through circuit complexity. While a solution to the problem still evades us, exponential lower bounds have been obtained for restricted classes of circuits. In this talk we will examine the work of Razborov on monotone circuit complexity, and see that there are no efficient monotone circuits for the clique problem. The proofs will use the probabilistic method, a topic we shall explore further should time permit.

• The monotone circuit complexity of Boolean functions, by N. Alon, R. B. Boppana, 1985.

Some Results on Graph Sparsificiation

Isaac Fung

Cut sparsfiers are sparse subgraphs that approximately preserve the cuts of the input graph. They are useful in speeding up graph algorithms like min cut/max flow. In this talk, I will talk about several results on cut sparsifiers, including a recent one that resolves a question of Benczur and Karger. This is based on joint work with Nicholas Harvey.

• Random sampling in cut, flow, and network design problems, by David Karger, Mathematics of Operations Research, 1994.
• Randomized approximation schemes for cuts and flows in capacitated graphs, full version of Benczur and Karger's STOC '96 and SODA '98 papers.
• Graph Sparsification by Edge-Connectivity and Random Spanning Trees, by Wai Shing Fung, Nicholas J. A. Harvey.

Triangle Removal Lemma

Siuman Chan

The Triangle Removal Lemma has applications to graph theory, additive combinatorics, property testing and beyond. Recently, there is a new proof of the Triangle Removal Lemma, which avoids the Szemeredi Regularity Lemma and improves substantially on the dependence of key parameters.

This talk will be an exposition on the Triangle Removal Lemma, its applications, and the recent proof.

• Property testing and Szemeredi's Theorem, by Luca Trevisan, blogpost.
• A new proof of the graph removal lemma, by Jacob Fox.

Invariance Principle

Siuon Chan

Invariance Principle, introduced by Mossel, O'Donnell and Oleszkiewicz, generalizes Berry-Esseen's Central Limit Theorem. The principle has become an indispensable tool in hardness of approximation and constructing pseudorandom generators.

In this talk, I will present a representative application of the principle, namely Majority-is-Stablest Theorem. I will also sketch the proof of the principle. No background is assumed.

• Noise stability of functions with low influences: invariance and optimality, Annauls of Mathematics, 2010

Efficient splitting-off algorithms

Darek Yung

This is a practice conference talk on the following paper.

• Efficient edge splitting-off algorithms maintaining all-pairs edge-connectivities, IPCO 2010

Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing

Danupon Nanongkai

In the previous talk in January, I have introduced the pricing problems and presented an O(log n)-approximation algorithm for the Stackelberg shortest path problem. In this talk I will present my progress so far in proving the hardness of approximation of this problem. In particular, I will show that the problem is hard to approximate within a factor of 2-o(1) and some progress towards proving a stronger lower bound. The results can be found in the following manuscript (joint work with P. Briest, P. Chalermsook, S. Khanna, and B. Laekhanukit). If time permits, I will also sketch another O(log n)-approximation algorithm which reveals more structure of the problem. This is from this paper by Roch, Marcotte, and Savard.

• Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing
• An Approximation Algorithm for Stackelberg Network Pricing

A New Approach to Strongly Polynomial Linear Programming

Chengwei Guo

Linear programming is perhaps the most general setting that holds open the possibility of a strongly polynomial algorithm. The paper present an affine-invariant approach for solving linear programs, based on the simplex method. Unlike previous pivot rules, the new algorithm picks direction by taking a linear combination of all the improving rays and takes shortcuts through the interior of the polytope, not be restricted to its edges. It is proved that the new approach works efficiently for deformed products, a class of polytopes that generalizes all known counterexamples for variants of simplex method.

• A New Approach to Strongly Polynomial Linear Programming by Mihaly Barasz and Santosh Vemplala, Innovations in Computer Science, 2010

Minimum Cut in Near-Linear Time

Hackson Leung

In graph theory, a cut is a subset of edges whose removal disconnects the graph. A cut is minimum if the size of the cut is not larger than the size of any other cut.

Many deterministics algorithms were proposed to solve the minimum cut problem, but none of them hits the linear time bound. In 2000 Karger gives a randomized (Monte Carlo) algorithm that finds a minimum cut in an m-edge, n-vertex graph with high probability in O(m log^3 n) time by utilizing tree-packing and random sampling on an undirected graph.

• Minimum cuts in near-linear time, David R. Karger, Journal of the ACM, vol 47(1), pp. 46-76, 2000

A Computational Game-Theoretic Framework for Cryptography

Li Yang

• A Computational Game-Theoretic Framework for Cryptography by Joseph Halpern and Rafael Pass, 2009.

Flavor of algorithmic pricing problems

Danupon Nanongkai

Algorithmic pricing problems refer to a large class of problems that arose recently from the field of algorithmic mechanism design. Besides being natural and easy to state, some of these problems have interesting structures that are different from previously studied problems. Many approximability results of various variations of these problems were discovered in the last few year. Yet, many problems are still open. In this talk, I will try to give a flavor of the problems and results in this area. In particular, I plan to cover the following three sub-topics.

• Unit-demand pricing problems
• Single-minded pricing problems
• Stackelberg pricing problems

Two simple algorithms will be presented.

• An O(k)-approximation algorithm for Hypergraph Vertex Pricing problem by Balcan and Blum [1].
• An O(log n)-approximation algorithm for Stackelberg Pricing by Briest and Krysta [2]

No background will be assumed.

• [1] Approximation Algorithms and Online Mechanisms for Item Pricing, by Maria-Florina Balcan and Avrim Blum. Theory of Computing 3(1): 179-195 (2007)
• [2] Stackelberg Network Pricing Games by Patrick Briest, Martin Hoefer, Piotr Krysta, STACS 2008.

Randomised communication protocols of Hamming distance and symmetric XOR function

Helic Leung

Communication complexity quantifies the minimum number of bits for the worst-case input in the communication that two or more parties want to compute some boolean function f. The communication complexity model was first introduced by Yao. The communication complexity of any important functions have been studied and many efficient protocols are found. In this talk, we are going to focus on the communication protocol on some functions related to bitwise XOR operations, including Hamming distance function and symmetric XOR function. Recently quite a few new randomized protocols were obtained for those XOR-related functions. These result matches the lower bound proposed by Shi and Zhang [SZ09] about the communication complexity of symmetric XOR functions, it could well be the truth that there is no asymptotic gap for all the XOR functions between quantum and classical communication complexity.

• The communication complexity of the Hamming Distance problem, by Wei Huang, Yaoyun Shi, Shengyu Zhang, Yufan Zhu. Information Processing Letters, 99(4), pp. 149-153, 2006.
• Communication Complexities of XOR functions by Yaoyun Shi, Zhiqiang Zhang, 2008.

Szemeredi regularity lemma

Li Fan and Andrej Bogdanov

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.

• Szemeredi Regularity Lemma and its applications in graph theory, by Janos Komlos and Miklos Simonovits.
• Graph Theory (chapter 7), by Reinhard Diestel, GTM 173, Springer.

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.

• Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels, by Erdal Arikan, IEEE Transactions on Information Theory, July 2009.
• Polar Codes: Characterization of Exponent, Bounds, and Constructions, by Satish Babu Korada, Eren Sasoglu, Rudiger Urbanke, submitted to IEEE Transactions on Information Theory.

The intersection of two halfspaces has high threshold degree

Shengyu Zhang

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

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.

• Tutte matrix
• Maximum Matchings via Gaussian Elimination

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.

• Perfect Matchings in O(n \log n) Time in Regular Bipartite Graphs, by Ashish Goel, Michael Kapralov, Sanjeev Khanna, 2009.

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).

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]

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.

• Excluded permutation matrices and the Stanley-Wilf conjecture, by A. Marcus, G. Tardos, Journal of Combinatorial Theory, Series A, 2004.
• A Loving Rendition of the Marcus-Tardos Amazing Proof of the Furedi-Hajnal Conjecture, by Doron Zeilberger.