Colloquium Details
IBM Research NYU/Columbia Theory Day
Speaker:
Location: Schapiro (CEPSR) Building, Columbia University 412
Date: April 15, 2005, 9:30 a.m.
Host: Yevgeniy Dodis
Synopsis:
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.
Notes:
In-person attendance only available to those with active NYU ID cards.