tcs math – some mathematics of theoretical computer science

October 16, 2009

Bloomington summer school recap

A couple months ago, at Indiana University, David Fisher, Nets Katz, and I  organized a summer school on Analysis and geometry in the theory of computation.  This school is one in a series organized by David and funded by NSF grant DMS-0643546 (see, e.g. last year’s school). What follows is a brief synopsis of what the school covered.  All the lectures were given by the participants, and there are links to their lecture notes below.  This is essentially an extended version of an introductory document I wrote for the participants, who were a mix of mathematicians and theoretical computer scientists.

Approximation Algorithms

In the following discussion, we will use the word efficient to describe an algorithm that runs in time polynomial in the size of its input. For a graph {G=(V,E)}, we use {\textsf{MC}(G)} to denote the “MAX-CUT value,” i.e. the quantity

\displaystyle \max_{S \subseteq V} \frac{|E(S, \bar S)|}{|E|},

where {E(S, \bar S)} denotes the set of edges between {S} and its complement. It is well-known that computing {\textsf{MC}(G)} is {\mathsf{NP}}-complete, and thus assuming {\mathsf{P} \neq \mathsf{NP}}, there is no efficient algorithm that, given {G}, outputs {\textsf{MC}(G)}.

Given this state of affairs, it is natural to ask how well we can approximate the value {\mathsf{MC}(G)} with an efficient algorithm. For an algorithm {\mathcal A}, we use {\mathcal A(G)} to denote its output when run on the graph {G}. If {\mathcal A} satisfies {\mathcal A(G) \leq \mathsf{MC}(G)} for all {G}, we define its approximation ratio as

\displaystyle \alpha(\mathcal A) = \sup \left\{ \alpha : \mathcal A(G) \geq \alpha \cdot \mathsf{MC}(G) \textrm{ for all graphs}\right\}

Clearly {\mathcal A(G) \in [0,1]}. Now we are interested in the best approximation ratio achievable by an efficient algorithm {\mathcal A}, i.e. the quantity

\displaystyle \textrm{approx}(\mathsf{MC}) = \sup \left\{ \alpha(\mathcal A) : \mathcal A \textrm{ is efficient} \right\}

It should be clear that similar questions arise for all sorts of other values which are NP-hard to compute (e.g. the chromatic number of a graph, or the length of its shortest tour, or the length of the longest simple path, etc.) An algorithm of Goemans and Williamson (based on a form of convex optimization known as semi-definite programming) shows that

\displaystyle \mathrm{approx}(\mathsf{MC}) \geq \alpha_{\mathrm{GW}} = \frac{2}{\pi} \min_{0 < \theta < \pi} \frac{\theta}{1-\cos\theta} = 0.878\ldots

On the other hand, Håstad proved that, as a consequence of the PCP Theorem, it is NP-complete to obtain an approximation ratio better than {16/17}, i.e. if {\mathsf{P} \neq \mathsf{NP}}, then

\displaystyle \mathrm{approx}(\mathsf{MC}) \leq \frac{16}{17} = 0.941\ldots

How does one prove such a theorem? Well, the {\mathsf{NP}}-hardness of MAX-CUT is based on constructing graphs where every optimal solution has a particular structure (which eventually encodes the solution to another NP-hard problem like SATISFIABILITY). Similarly, the NP-hardness of of obtaining even “near-optimal” solutions is proved, in part, by constructing graphs where every solution whose value is close to optimal has some very specific structure (e.g. is close—in some stronger sense—to an optimal solution).

In this way, one of the main steps in proving the inapproximability of {\mathsf{NP}}-hard problems involves constructing objects which have such a “rigidity” property. This summer school is about how one can use the rigidity of analytic and geometric objects to obtain combinatorial objects with the same property. In fact, assuming something called the “Unique Games Conjecture” (which we will see later), the approximability of many constraint satisfaction problems can be tied directly to the existence of certain geometric configurations.

The Lectures

The first series of lectures will concern the Sparsest Cut problem in graphs and its relationship to bi-lipschitz {L_1} embeddings of finite metric spaces. In particular, we will look at rigidity properties of  “nice” subsets of the Heisenberg group, and how these can be used to prove limitations on a semi-definite programming approach to Sparsest Cut. In the second series, we will see how—assuming the Unique Games Conjecture (UGC)—proving lower bounds on certain simple semi-definite programs actually proves lower bounds against all efficient algorithms. This will entail, among other things, an analytic view of {\{0,1\}}-valued functions, primarily through harmonic analysis.

Sparsest Cut and {L_1} embeddings

The Sparsest Cut problem is classically described as follows. We have a graph {G=(V,E)} and two functions {C : V \times V \rightarrow \mathbb R_+} and {D : V \times V \rightarrow \mathbb R_+}, with {\mathrm{supp}(C) \subseteq E}. The goal is to compute

\displaystyle   \Phi^*(G;C,D) = \min_{S \subseteq V} \frac{C(S, \bar S)}{D(S, \bar S)},

where we use {C(A,B) = \sum_{a \in A, b\in B} C(a,b)} and {D(A,B) = \sum_{a \in A, b \in B} D(a,b)}. The problem has a number of important applications in computer science.

Computing {\Phi^*(G;C,D)} is NP-hard, but again we can ask for approximation algorithms. The best-known approach is based on computing the value of the Goemans-Linial semi-definite program, \mathsf{sdp}(G;C,D), which is

\displaystyle \min \left\{ \frac{\sum_{u,v} C(u,v) \|x_u-x_v\|_2^2}{\sum_{u,v} D(u,v) \|x_u-x_v\|_2^2}: \{x_u\}_{u \in V} \subseteq \mathbb R^V\textrm{ and }\|x_u-x_v\|^2 \leq \|x_u-x_w\|^2 + \|x_w-x_v\|^2 \textrm{ for all }  u,v,w \in V \right\}.

This value can be computed by a semi-definite program (SDP), as we will see. It is an easy exercise to check that {\mathsf{sdp}(G;C,D) \leq \Phi^*(G;C,D)}, and we can ask for the smallest {\alpha = \alpha(n)} such that for all {n}-node graphs {G} and all functions {C,D}, we have

\displaystyle \Phi^*(G;C,D) \leq \alpha(n) \cdot \mathsf{sdp}(G;C,D).

(E.g. it is now known that {(\log n)^{2^{-1000}} \leq \alpha(n) \leq O(\sqrt{\log n} \log \log n)}, with the upper bound proved here, and the lower bound proved here.)

By some duality arguments, one can characterize {\alpha(n)} in a different way. For a metric space {(X,d)}, write {c_1(X,d)} for the infimal constant {B} such that there exists a mapping {f : X \rightarrow L_1} satisfying, for all {x,y \in X},

\displaystyle   \|f(x)-f(y)\|_1 \leq d(x,y) \leq B \|f(x)-f(y)\|_1.

It turns out that

\displaystyle \alpha(n) = \sup \left\{ c_1(X,d) : |X|=n \textrm{ and } (X, \sqrt{d})\textrm{ embeds isometrically in } L_2\right\} (1)

This shows that determining the power of the preceding SDP is intimately connected to understanding bi-lipschitz embeddings into {L_1}. This is what we will study in the first 6 lectures.

  1. (Arnaud de Mesmay) In the first lecture, we will be introduced to the basic geometry of the 3-dimensional Heisenberg group {\mathbb H^3}, and how differentiation plays a roll in proving lower bounds on bi-lipschitz distortion. In particular, we will see Pansu’s approach for finite-dimensional targets and a generalization to spaces with the RNP, and also why a straightforward generalization would fail for {L_1}.
  2. (Mohammad Moharrami) Next, we will see how a differentiation approach to {L_1} embeddings might work in a toy setting that uses only finite graphs. The study of “monotone subsets” (which is elementary here) also arises in the work of Cheeger and Kleiner in lectures 4 and 5.  (See also this post.)
  3. (Sean Li) Here, we will see that there is an equivalent metric {d} on the Heisenberg group for which {(\mathbb H^3, \sqrt{d})} embeds isometrically into {L_2}. This is one half of proving lower bounds on {\alpha(n)} using (1).
  4. (Jeehyeon Seo and John Mackay) In Lectures 4-5, we’ll look at the approach of Cheeger and Kleiner for proving that {\mathbb H^3} does not bi-lipschitz embed into {L_1}.  (Note that these authors previously offered a different approach to non-embeddability, though the one presented in these lectures is somewhat simpler.)
  5. (Florent Baudier) Finally, in Lecture 6, we see some embedding theorems for finite metric spaces that allow us to prove upper bounds on {\alpha(n)}.

The UGC, semi-definite programs, and constraint satisfaction

In the second series of lectures, we’ll see how rigidity of geometric objects can possibly say something, not just about a single algorithm (like a semi-definite program), but about all efficient algorithms for solving a particular problem.

  1. (An-Sheng Jhang) First, we’ll review basic Fourier analysis on the discrete cube, and how this leads to some global rigidity theorems for cuts. These tools will be essential later.  (See also these lecture notes from Ryan O’Donnell.)
  2. (Igor Gorodezky) Next, we’ll see a semi-definite program (SDP) for the MAX-CUT problem, and a tight analysis of its approximation ratio (which turns out to be the {0.878\ldots} value we saw earlier).
  3. (Sam Daitch) In the third lecture, we’ll see the definition of the Unique Games Conjecture, and how it can be used (in an ad-hoc manner, for now) to transform our SDP analysis into a proof that the SDP-based algorithm is optimal (among all efficient algorithms) under some complexity-theoretic assumptions.
  4. (Deanna Needell) A key technical component of the preceding lecture is something called the Majority is Stablest Theorem that relates sufficiently nice functions on the discrete cube to functions on Gaussian space.
  5. (Sushant Sachdeva) In the final lecture, we’ll see Raghavendra’s work which shows that, for a certain broad class of NP-hard constraint satisfaction problems, assuming the UGC, the best-possible algorithm is the “canonical” semi-definite program. In other words, the approximation ratio for these problems is completely determined by the existence (or lack thereof) of certain vector configurations in {\mathbb R^n}.  (See also this post.)

The Shocking Blue Green Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

Join 63 other followers