Introduction to Probabilistic Method and Lovasz Local Lemma

Tom Chan

In this talk, Tom will give a brief introduction to the Probabilistic Method, a powerful tool in Combinatorics pioneered by Paul Erdos. Well known examples in graph colouring will be given to illustrate some of the techniques used in Probabilistic Method, including First Moment Method, optimality of parameters, and how it may lead to efficient probabilistic algorithm. Lovasz local lemma will also be introduced. No background is assumed.

• The Probabilistic Method, by Noga Alon and Joel Spencer.
• Graph Colouring and the Probabilistic Method, by Michael Molloy and Bruce Reed.

Simple deterministic approximation algorithms for counting matchings

Chandra Nair

In this talk, I will show how local (w.r.t. graph topology) messages can be used to count the number of matchings in graphs. Restricting ourselves to polynomial time algorithms we show how these messages can be used to give a deterministic approximation algorithm for counting matchings in bounded degree graphs. Counting matchings for regular graphs (with degree at least 5) has been known to be #P-complete (ref: Vadan) and this algorithm follows shortly on the heels of the first ever deterministic poly-time approximation algorithms for a #P-complete problem (counting independent sets) by Dror Weitz. In this talk, we shall follow up on the talks in previous weeks by showing the usefulness of message passing algorithms in deriving fast, distributed, iterative algorithms to solve combinatorial optimization problems.

• Counting independent sets up to the tree threshold, by Dror Weitz, STOC 2006.
• Simple deterministic approximation algorithms for counting matchings, STOC 2007.

Message Passing and Iterative Decoding

Isaac Fung

Isaac will continue the presentation started last week. In this talk, he will introduce the Low Density Parity Check Code and the modification required for the sum-product algorithm to decode codes with cyclic factor graphs. We will also analyze the asymptotic performance of iterative decoding for the Binary Erasure Channel.

• Appendix C of Modern Coding Theory by T. Richardson and R. Urbanke.

Message Passing and Iterative Decoding

Isaac Fung

In the first part of this presentation, Isaac will illustrate how the sum-product algorithm (message passing) can be used to solve the marginalization problem and its application on probabilistic reasoning problems. In the second part, he will explain another application of the sum-product algorithm on iterative decoding of LDPC code.

• Modern coding theory by Richardson and Urbanke.
• Chapter 6,8 of Fundamentals of codes, graphs and iterative decoding (e-book access via CUHK library)
• Capacity approaching codes lecture notes of David Forney
• notes on sum-product algorithm and LDPC code by Isaac

Register Allocation by Puzzle Solving

Fernando Pereira (UCLA)

Register allocation is the problem of mapping the variables in a program into physical locations, which can be either registers or memory. Good compilers generally try to maximize the number of variables stored in registers, sending to memory as few values as possible. Unfortunately, the core register allocation problem of deciding if all the variables in a program can be mapped into registers is NP-complete, as shown by Gregory Chaitin in 1981, via a reduction to the graph coloring problem. However, in 2005 Bouchez, Brisk et al., and Hack proved independently that every program in static single assignment (SSA) form has a chordal interference graph that is colorable in linear time. This means that core register allocation for SSA-form programs and machines with registers of uniform size executes in polynomial time.

In this talk we discuss the polynomial time register assignment algorithm, and show how it can be extended to the common and more general setting of aliased registers and pre-coloring, which is found in the x86 architecture, for example. We define the concepts of elementary programs and elementary graphs. Our main result is that an elementary graph is colorable in linear time, even in the presence of aliased registers and pre-coloring. The key to our linear-time algorithm is that we prove that coloring of an elementary graph can be viewed as solving a collection of puzzles, and that each puzzle can be solved in linear time. This means that spill-free register allocation for elementary programs, aliased registers, and pre-coloring executes in polynomial time. Moreover, any well structured program can be converted to an elementary program, and the new representation never requires more registers than the original one. We conclude the talk discussing recent experimental results showing that optimal register assignment algorithms are feasible and useful for computer architectures as constrained as the x86. For instance, our implementation generates Pentium code that is on average 11% faster than the code produced by gcc.

• Register Allocation by Puzzle Solving.

Primal Dual Method for Approximation Algorithm

Darek Yung

Linear program strongly influences combinatorial optimization in the past few decades. A number of problems, such as assignment problem, can be modelled and solved by linear program. In this seminar, we will discuss the duality of linear program and the primal dual method for solving the problem. No background knowledge is assumed

• Duality: Teaching Duality in Linear Programming - the Multiplier Approach.
• The Primal-Dual Method for Approximation Algorithms and its Application to Network Design Problems.

Cut tree and minimum 3-way cut

Mingyu Xiao

Cut tree, also known as Gomnory-Hu tree or separator tree, is a compact way to represent all the (n \choose 2) s-t cuts of an undirected graph with n vertices. In this talk, I'd like to discuss:

(1) What is a cut tree, how to compute a cut tree, and current results on cut tree,

(2) How to use a cut tree to design a faster algorithm for the minimum 3-way cut problem (to find a subset of edges with minimum weight whose removal separates the graph into 3 disconnected components).

• An O~(mn) Gomory-Hu tree construction algorithm for unweighted graphs STOC 2007.
• On minimum 3-way cuts 2007.

Network Design via Iterative Relaxation

Lap Chi

Network design captures many fundamental problems in approximation algorithm and combinatorial optimization. We'll see how the iterative relaxation method, which is an extension of Jain's iterative rounding method, provides a unifying framework to solve these problems, including the minimum bounded degree spanning tree problem. This method is based on fundamental ideas in combinatorial optimization, namely submodular functions and the uncrossing technique, which will be discussed in details. We'll also mention how this method can be used to obtain new approximation algorithms, simple proofs of known approximation algorithms, and alternate proofs of classical polynomial time algorithms.

• A Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem by Kamal Jain, Combinatorica 2001.
• Survivable network design with degree or order constraints 2007.
• Approximating minimum bounded degree spanning tress to within one of optimal 2007.

Analysis in Graph Regularity

Siu Man

We introduce some analytic languages for studying graph regularity. The equivalence of some finitary and infinitary arguments will be established. The analytic language for studying convergent graph sequences will be employed to give a short proof of the subgraph counting lemma, completing the proof outline of Szemeredi's Theorem.

• Soft analysis, hard analysis, and the finite convergence by Tao
• Limits of dense graph sequences by Lovasz and Szegedy

Szemeredi's Regularity Lemma

Siu On

Szemeredi's Regularity Lemma is a powerful tool in additive combinatorics, extremal graph theory, property testing, etc. In this seminar we will introduce the Lemma, related ideas (e.g. quasi-randomness) and some applications.

• The regularity lemma by Mahdian
• Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs by W.T. Gowers

Submodular functions in graph theory

Lap Chi

We'll see how submodular functions play an important role in graph theory. To illustrate this, new proofs of classical theorems on matchings, edge-disjoint paths, and edge-disjoint spanning trees are provided, as well as new applications on graph orientations and graph augmentations. No background is assumed.

• Submodular functions in graph theory by Andras Frank, Discrete Mathematics 1993.
• Submodular functions in combinatorial optimization

Integer Multiplication

Tom Chan

In this seminar, a brief overview on integer multiplication will be given, including:

• Long multiplication
• Karatsuba algorithm
• Toom-Cook algorithm
• Strönhage-Strassen algorithm

• Faster integer multiplications by Furer, STOC 2007.

Single Source Multicommodity Unsplittable Flow

Issac Fung

In this seminar, two papers on single source multicommodity unsplittable flow will be presented. The first paper we present describes an algorithm that transforms a splittable flow to an unsplittable flow, while the edge capacity constraint on each edge is violated by no more than the max demand. The second paper we present gives similar result on bounding the congestion, and in addition, the cost of the unsplittable flow is also bounded by the cost of the splittable flow.

• On the single source unsplittable flow problem by Dinitz, Garg, and Goemans, Combinatorica 1999 (FOCS 1998).
• Approximating the Single Source Unsplittable Min-Cost Flow Problem by Skutella, Mathematical Programming B 2002 (FOCS 2000).

Rectangle Covering

Darek Yung

In this seminar, the problem of covering orthogonal polygons with rectangles will be discussed.

• Covering Regions by Rectangles by Chaiken, Kleitman, Saks, and Shearer, SIAM Journal on Discrete Mathematics 1981.