Integrality gap and hardness of approximation

Lap Chi Lau

I will present recent results connecting integrality gaps of LP/SDP relaxations of combinatorial optimization problems to computational hardness of these problems assuming unique games conjecture. The main technical tool is an Invariance Principle by Mossel.

• Optimal Algorithms and Inapproximability Results for Every CSP?, by Prasad Raghavendra, STOC 2008.
• SDP Gaps and UGC Hardness for Multiway Cut, 0-Extension and Metric Labeling, by Manokaran, Naor, Raghavendra, Schwartz, STOC 2008.
• Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes, by Elchanan Mossel, FOCS 2008.

Inapproximability of k-CSP and Gowers norm

Andrej Bogdanov

I will talk about hardness of approximating kCSP using the Gowers norm, following "Gowers uniformity, influence of variables, and PCPs" by Samorodnitsky and Trevisan and some simplifications from a recent paper by Guruswami and Raghavendra.

• Gowers Uniformity, Influence of Variables, and PCPs, by Samorodnitsky and Trevisan, STOC 2006.
• Constraint Satisfaction over Non Boolean Domain : Approximation Algorithms and Unique Games Hardness, by Guruswami and Raghavendra, APPROX 2008.

Analysis of boolean functions

Andrej Bogdanov

We will go over the proof of Kahn, Kalai, and Linial that evrey boolean function has a variable of influence O(log n / n) and a theorem of Friedgut that every boolean function whose sum of influences is small is close to a junta.

• The influence of variables on boolean functions, by Kahn, Kalai, Linial, FOCS 1988.
• Boolean Functions With Low Average Sensitivity Depend On Few Coordinates, by Friedgut, Combinatorica 1998.

Optimal inapproximability of MAX-CUT?

Lap Chi Lau

Assuming the unique games conjecture, we will prove that the Goemans-Williamson SDP .878 approximation algorithm for MAX-CUT is optimal.

• Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, by Khot, Kindler, Mossel, O'Donnell, in SIAM Journal of Computing 2007 (also in FOCS 2004).

Majority is stablest

Shengyu Zhang

Today we will prove the majority is stablest theorem, which will later be used to prove optimal inapproximability for the MAX-CUT problem.

• Noise stability of functions with low influences: invariance and optimality , by Mossel, O'Donnell, Oleszkiewicz, to appear in Annals of Mathematics (also in FOCS 2005).

Unique Games Conjecture

Chandra Nair

I will talk about the motivation, and origins of Unique games conjecture and on hardness of 2-lin-mod 2. In particular, I will prove that NP = PCP_(1-\ep, 1-\ep^t)[O(log n),2] or 1/2 < t < 1. The proof uses Fourier analysis.

• On the power of unique 2-prover 1-round games , by Subhash Khot, STOC 2002.

Hastad 3-bit PCP

Lap Chi Lau

We will prove Hastad 3-bit PCP theorem and show a hardness result of set cover, following the presentation in Arora-Barak book.

• Computation Complexity: A Modern Approach , by Sanjeev Arora and Boaz Barak, chapter 22.

Weak PCP theorem and Fourier analysis

Lap Chi Lau

We will prove a weak PCP theorem and introduce the Fourier analysis technique, following the presentation in Arora-Barak book.

• Computation Complexity: A Modern Approach , by Sanjeev Arora and Boaz Barak, chapter 11 and 22.

Introduction to PCP theorem 2

Andrej Bogdanov

We will discuss the parallel repetition theorem, and Dinur's proof of PCP theorem.

Introduction to PCP theorem 1

Andrej Bogdanov

For this Friday's seminar I plan to give an introduction to PCP, outline the connection to hardness of approximation, and try to give a proof of a "weak" PCP theorem (which is used in Dinur's proof of the real PCP theorem). Most of this is in Chapter 11 of the Arora-Barak book.

• PCP Theorem and hardness of approximation: an introduction , by Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, chapter 11.

Combinatorial Nustellensatz

Lap Chi Lau

Combinatorial Nullstellensatz is a method to prove the existence of combinatorial objects by the existence of non-zero solutions of polynomial equations. We will discuss the general method and see some applications.

• Combinatorial Nullstellensatz, by Noga Alon, Combinatorics, Probability and Computing, 8, 7-29, 1999.

Circle packing and planar graph

Isaac Fung

In this talk, we will present the Koebe theorem, which says that every planar graph is the intersection graph of a circle packing. Then we will use it to show that every planar graph has a small separator whose removal disconnects the graph into two parts of roughly eqaul sizes. We will see some applications of this theorem.

• Circle packing theorem on Wikiepedia.
• Chapter 3 of Advanced Geometric Algrotihms.
• Applications of a planar separator theorem, by Lipton and Tarjan, 1977.
• Geometric graph theory (chapter 5), by Lovasz.

Hall's theorem for hypergraphs

Tom Chan

In this talk, an extension of the Hall's theorem to the hypergraph is discussed. The theorem provides a sufficient condition for the existence of a system of disjoint representative in a family of hypergraphs. The proof of the theorem uses Sperner's lemma, which is topological. This theorem is the main ingredient in proving the Ryser's conjecture for tripartite 3-graphs. Also, we will show how another extension of the Hall's theorem for hypergraphs is applied to prove a constant integrality gap of configuration LP relaxation for a kind of Santa Claus Problem called restricted assignment problem (max min allocation). Attendance of previous meeting is not assumed.

• Hall's theorem for hypergraphs, by Ron Aharoni and Penny Haxell, Journal of Graph Theory, 2000.
• Ryser's conjecture for tripartite 3-graphs, by Ron Aharoni, Combinatorica, 2001.
• Santa Claus meets hypergraph matching, by Arash Asadpour, Uriel Feige, Amin Saberi, APPROX 2008.

Applications of Borsuk-Ulam theorem

Darek Yung

This week, we will continue on the discussion of the Borsuk-Ulam theorem. Materials to be covered include the combinatorial analog of the Borsuk-Ulam theorem, the Tucker's lemma; and applications of the Borsuk-Ulam theorem, namely, the Ham Sandwich theorem and a proof of the Lovasz-Kenser theorem. Attendance of last week's meeting is not assumed.

• Using the Borsuk-Ulam theorem, by Jiri Matousek, Springer Verlag, Berlin, 2003. Chapter 2-3.

Borsuk-Ulam theorem

Siu Man Chan

Topological theorems, most notably Borsuk-Ulam theorem and Brouwer fixed-point theorem, have been used in combinatorial settings. They found applications to colouring of graphs and hypergraphs (in particular the solution of Kneser conjecture) and various fair division problems. To explain the theorems, we discuss several of their equivalent formulations (including their combinatorial counterparts, i.e. Tucker Lemma and Sperner Lemma) and prove their equivalences. Then a fairly elementary, geometric proof of Borsuk-Ulam Theorem will be presented. We also discuss how to apply Sperner Lemma to solve the fair cake-cutting problem. Only a minimal understanding of continuity (as provided by elementary real analysis) is all prerequisite assumed for topological discussion.

• Using the Borsuk-Ulam theorem, by Jiri Matousek, Springer Verlag, Berlin, 2003.
• On the Sperner Lemma and its Applications, by Jonathan Huang.

On the constant-depth complexity of k-clique

Siu On Chan

Recently, Rossman proved that recognizing k-cliques in a graph by depth-d circuits requires more than £s(n^(k/4)) gates, improving on the previous lower bound of £s(n^(k/89d^2)) by Paul Beame. Main ideas behind Rossman's proof will be presented in this talk. The technical lemma central to this and many other circuit lower bound results (i.e. Switching Lemma) will also be introduced.

• On the constant-depth complexity of k-clique, by Benjamin Rossman, STOC 2008.
• AC and switching lemma, Lecture 19, Computational Complexity.
• Parity is not in AC^0: proof with the switching lemma, Lecture 26, Computational Complexity.
• A Switching Lemma Primer, by Paul Beame.

Epsilon-net theorem and its applications

Isaac Fung

In this talk, we will present the epsilon-net theorem which roughly says that in a set system with bounded VC dimension, there exists a "small" sample that intersects with all the "heavy" sets. And we will see some applications in computational geometry, network failure detection and an improved set cover approximation algorithm.

• Advanced algorithms Lecture 19-21.
• Almost Optimal Set Covers in Finite VC-Dimension, by H. Bronnimann and M.T. Goodrich, Discrete and Computational Geometry 1995.
• Detecting a Network Failure, by Jon Kleinberg, FOCS 2000.

LP Relaxation and Belief Propagation for Weighted Matchings

Tom Chan

A b-Matching on a graph is a set of edges such that each vertex i is incident to at most b_i of them, and the total weight of edges is minimized (maximized). In this talk we will cover the belief propagation formulation for the b-matching problem and see how the existence of unique LP solution implies the convergence (to the correct solution) of the BP. The correctness of BP allows distributed computing of a b-matching and this has applications in sensor networks where nodes cannot afford too many connections due to power constraint.

• Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions, by M. Bayati, C. Borgs, J. Chayes, R. Zecchina, ArXiv Preprint, Feb 2008.
• Equivalence of LP Relaxation and Max-Product for Weighted Matching in General Graphs, by S. Sanghavi, Information Theory Workshop 2007.
• Linear Programming Analysis of Loopy Belief Propagation for Weighted Matching, by S. Sanghavi, D.M. Malioutov, A.S. Willsky, Neural Information Processing Systems (NIPS) 2007.

Transversals of d-intervals

Lap Chi Lau

Given a real line, a d-interval is the union of d closed intervals. Given a system of d-intervals such that no k+1 of them are pairwise disjoint, it has been proven that there is a set of O(kd^2) points that intersect every d-interval. Two proofs will be presented, one is topological using Borsuk-Ulam theorem, another is elementary using LP-duality theorem.

• Transversals of d-intervals, by Tomas Kaiser, Discrete and Computational Geometry, 1997.
• Piercing d-intervals, by Noga Alon, Discrete and Computational Geometry, 1998.

Strong Steiner Tree Packing

Hehui Wu

Given a graph G and a subset S of vertices, a S-Steiner-tree is a subtree of G containing S. We call a subgraph H a strong S-subgraph if there exists a system of edge-disjoint paths in H with two end points in S, after replacing the paths with edges joining their end points, they induce a connected graph in S. We generalize Nash-William's Theorem and give a sufficient condition for G to have k edge-disjoint strong S-subgraphs. In use of this, we improve Lap Chi Lau's result, and prove if S is 11k edge-connected in G, then there exist k edge- disjoint S-Steiner-trees. Furthermore, if S is 16k edge-connected in G, then there exist k edge-disjoint strong S-subgraphs in G.

LP Decoding Corrects a Constant Fraction of Errors

Tom Chan

In this talk the techniques used by Feldman et al. will be discussed. They analysed the performance of the LP decoder (discussed last time) under an adversarial bit flipping channel and showed a constant fraction of errors can be corrected.

The LP decoding success is shown by a "dual witness". The existence of such witness is guaranteed by a feasible edge weight assignment and the assignment is implied by a special matching called (delta, lambda)-matching. Finally the assumption that the Tanner graph is an expander imply the existence of the matching. A hyperflow interpretation of the feasible edge weight assignment will also be covered.

• LP Decoding Corrects a Constant Fraction of Errors, by Jon Feldman, Tal Malkin, Rocco A. Servedio, Cliff Stein, Martin J. Wainwright, IEEE Transactions on Information Theory, 2007.
• Probabilistic Analysis of LP Decoding, by Constantinos Daskalakis, Alexandros G. Dimakis, Richard M. Karp, Martin J. Wainwright, SODA 2007.

Online Routing via Online Priaml-Dual Method

Qin Zhang

In this talk, we study a wide range of online and offline routing and packing problems with various objectives. We provide a unified approach, based on a clean primal-dual method, for the design of online algorithms for these problems, as well as improved bounds on the competitive factor.

• Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach, by Niv Buchbinder and Seffi Naor, FOCS 2006.
• Multiplicative weights method: a meta-algorithm and its applications (A survey), by Sanjeev Arora, Elad Hazan, and Satyen Kale.

Proof of the capacity region of the degraded broadcast channel

Chandra Nair

Combination of results by Cover '72 (the achievability part) and Gallager '74 (the converse)

I will present the proof of one of the few known capacity regions in multi-user information theory. This talk will be introductory and will not assume any knowledge of information theory. In general, the proof that a certain expression represents the capacity region has two parts: one is a achievability part - meaning existence of a scheme that achieves a certain rate pair region, and the other is an impossibility part - meaning a proof that no scheme can beat the rate region.

I hope from this talk, one could perhaps draw useful parallels to the CS algorithmic world.

Nash Equilibrium

Isaac Fung

In the first part of this talk, Isaac will talk about the proof of Sperner's lemma and Brouwer's fixed point theorem which are used in establishing the existence of Nash's equilibrium and then describe the Lemke-Howson algorithm for finding Nash equilibrium in 2 player game. In the second part, he will introduce the class of PPAD problem and sketch the reduction of the Brouwer's fixed point problem to the Nash eqilibrium problem, thus showing that Nash is PPAD-complete.

• Proof of existence of equilibria.
• The Lemke-Howson Algorithm in Chapter 3 of Algorithmic Game Theory.
• Introduction to PPAD.
• The Complexity of the Parity Argument and Other Inefficient proofs of Existence (1991) (the paper in which PPAD is defined).
• Settling the Complexity of Two-Player Nash Equilibrium.

LP decoding of LDPC codes

Tom Chan

In this talk, Linear Programming (LP) formulation of the Low-Density Parity-Check (LDPC) codes will be discussed. Specifically, we will look at the LP relaxation to the Maximum Likelihood (ML) decoding and see what are the differences in terms of decodeable region and why is it so.

• Chapter 4, 5 of PhD thesis of Jon Feldman.

On Problems Without Polynomial Kernels

Lin Yang

In this talk we'll look at the kernelization method in parameterized computation, and talk about a recent progress on finding lower bounds on the kernel size. Kernelization is a well studied method in designing FPT algorithms for parameterized problems, however we can seldom say anything about the lower bound on the kernel size, until recently. With a negative result developed when people investigate a property of NP languages called /Compressibility/, a wide range of parameterized problems are shown to be not polynomially kernelizable *under resonable complexity-theoretic assumptions*.

• On Problems Without Polynomial Kernels, by Hans Bodlaender, Rodney Downey, Michael Fellows, and Danny Hermelin, 2007.
• Infeasibility of NP Compression and Succinct PCPs for NP, by Lance Fortnow and Rahul Santhanam, ECCC report 2007, to appear in STOC 2008.

Approximate Distance Oracles

Qin Zhang

We will consider the following problem: given a graph G, how to perform a preprocessing of G and construct a data structure of small size such that we can compute the approximate distance between any pair of points of G efficiently?

We will also briefly mention the relationship between the hierarchical sampling technique used in this paper and that used in the metric embedding paradigm.

• Approximate distance oracles, by Mikkel Thorup and Uri Zwick, JACM 2005.

Approximating Minimum Degree Spanning Tree

Darek Yung

Consider the minimum degree spanning tree problem, which is that of constructing a spanning tree whose maximal vertice degree is smallest among all spanning trees of the graph. Although computing spanning tree is efficiently solvable, introducing such simple constraint already makes the problem NP-hard.

We will discuss an iterative polynomial time approximation algorithm for this problem. The algorithm computes a spanning tree whose maximal degree is at most optimal + 1. Unless P = NP, this is the best achievable bound in polynomial time.

• Approximating the minimum degree spanning tree to within one from the optimal degree, by Martin Furer and Balaji Raghavachari, SODA 1993.

Introduction to online computation and competitive analysis

Lap Chi Lau

We will introduce the area of online computation and competitive analysis. In particular we will focus on the online paging problem, where we have a small cache (fast memory) and the objective is to minimize the number of page faults (loading pages from slow memory to fast memory if the pages are not currently in the fast memory), in an online setting (where we don't know which pages will be requested next).

This introduction will serve as a background for more advanced topics in online computation, e.g. the k-server problem. Also, it motivates the recently developed "online primal-dual method", which provides a general framework to solve many online problems, including the online weighted paging problem which was open for many years.

• Chapter 3 and 4 of "Online Computation and Competitive Analysis", by Allan Borodin and Ran El-Yaniv, Cambridge University Press, 1998.
• A Primal-Dual Randomized Algorithm for Weighted Paging, by Nikhil Bansal, Niv Buchbinder and Joseph Naor, FOCS 2007 (future reading).