The IBM Research/NYU/Columbia Theory Day

Friday, April 15, 2005
412 Schapiro (CEPSR) Building
Columbia University
New York, NY

Program

9:30 - 10:00 Coffee and bagels

10:00 - 10:55 Prof. David Zuckerman (University of Texas, Austin)
Linear-Degree Extractors and the NP-Completeness of Approximating Clique and Chromatic Number

10:55 - 11:05 Short Break

11:05 - 12:00 Dr. Nikhil Bansal (IBM T.J. Watson Research Center)
On Variations of Traveling Repairman Problems

12:00 - 2:00 Lunch break

2:00 - 2:55 Dr. Howard Karloff (AT&T Labs - Research)
On Approximation Algorithms for Minimum Linear Arrangement, or How to Use [ARV] for Fun and Profit

2:55 - 3:15 Coffee break

3:15 - 4:10 Prof. Daniel Spielman (MIT)
Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Symmetric, Diagonally-Dominant Linear Systems

Organizers:

Yevgeniy Dodis dodis@cs.nyu.edu
TalRabin talr@watson.ibm.com
Baruch Shieber talr@watson.ibm.com
Cliff Stein cliff@ieor.columbia.edu

Abstracts

Linear-Degree Extractors and the NP-Completeness of Approximating Clique and Chromatic Number

Prof. David Zuckerman
University of Texas, Austin

A randomness extractor is an algorithm which extracts randomness from a low-quality random source, using some additional truly random bits. Extractors have proved useful in a variety of seemingly unrelated areas. We construct new extractors which require only log n + O(1) additional random bits for sources with constant entropy rate. A similar construction allows us to derandomize the results of Hastad and Feige-Kilian and show that approximating Clique and Chromatic Number to within n^{1-epsilon} are NP-complete, for any epsilon>0.

Our constructions rely on recent results in additive number theory and extractors by Bourgain-Katz-Tao, Barak-Impagliazzo-Wigderson, Barak-Kindler-Shaltiel-Sudakov-Wigderson, and Raz. We also simplify and slightly strengthen key lemmas in the second and third of these papers.

On Variations of Traveling Repairman Problems

Dr. Nikhil Bansal
IBM T.J. Watson Research Center

In the classic traveling repairman problem, given a weighted graph on n vertices, we wish to find a tour that minimizes the average time a vertex waits before it is visited.

In this talk I will survey several recent variations/generalizations of the problem, and in particular focus on the following two problems:

1) Each vertex contains several requests with arbitrary release dates. A visit to a vertex satisfies all outstanding requests at that vertex. The goal is to find a tour that minimizes the average waiting time for a request. I describe the first poly-logarithmic approximation for the case of a uniform metric space (joint with Coppersmith and Sviridenko).

2) Each vertex has an associated interval of time, and fetches a reward if and only if visited during its interval. The goal is to find a tour that maximizes the reward collected (joint with Blum, Chawla and Meyerson).

On Approximation Algorithms for Minimum Linear Arrangement, or How to Use [ARV] for Fun and Profit

Dr. Howard Karloff
AT&T Labs - Research

We study Minimum Linear Arrangement (MLA), the problem of placing the n vertices of a graph onto {1,2,3,...,n} so as to minimize the sum of the edge lengths. Until the appearance of Arora, Rao, and Vazirani's groundbreaking work on Sparsest Cut, the best known approximation ratio for MLA was O(log n), achieved by Rao and Richa, who improved on a O((log n)(log log n)) approximation algorithm of Even, Naor, Rao, and Schieber.

We show how to use the main lemma of Arora, Rao, and Vazirani, together with the decomposition techniques of Rao and Richa, to improve the approximation ratio of MLA to O((sqrt(log n))log log n). The best part is, no previous knowledge of [ARV] will be necessary.

This is joint work with Moses Charikar of Princeton and Satish Rao of Berkeley.

Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Symmetric, Diagonally-Dominant Linear Systems

Prof. Daniel Spielman
MIT

Motivated by the problem of solving linear systems, we develop nearly-linear time algorithms for partitioning graphs and for building strong sparsifiers. The graph partitioning algorithm is the first provably fast graph partitioning algorithm that finds sparse cuts of nearly optimal balance. It is based on an algorithm for finding small clusters in massive graphs that runs in time proportional to the size of the cluster it outputs. Using the graph partitioning algorithm and random sampling, we produce strong graph sparsifiers.

We then apply these algorithms, along with constructions of low-strech spanning trees, to optimize an approach to solving linear systems introduced by Vaidya. We thereby obtain a nearly-linear time algorithm for approximately solving systems of linear equations of the form Ax=b, where A is symmetric and diagonally dominant.

This is joint work with Shang-Hua Teng.