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)
LinearDegree Extractors and the NPCompleteness 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)
NearlyLinear Time Algorithms for Graph Partitioning, Graph
Sparsification, and Solving Symmetric, DiagonallyDominant Linear Systems
For directions, please see: http://www.cs.columbia.edu/theory/directions.html
To subscribe to our mailing list, follow instructions at: http://www.cs.nyu.edu/mailman/listinfo/theoryny
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
LinearDegree Extractors and the NPCompleteness of
Approximating Clique and Chromatic Number
Prof. David Zuckerman
University of Texas, Austin
A randomness extractor is an algorithm which extracts randomness from
a lowquality 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 FeigeKilian and show that approximating Clique and Chromatic
Number to within n^{1epsilon} are NPcomplete, for any epsilon>0.
Our constructions rely on recent results in additive number theory and
extractors by BourgainKatzTao, BarakImpagliazzoWigderson,
BarakKindlerShaltielSudakovWigderson, 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 polylogarithmic 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.
NearlyLinear Time Algorithms for Graph Partitioning, Graph
Sparsification, and Solving Symmetric, DiagonallyDominant Linear Systems
Prof. Daniel Spielman
MIT
Motivated by the problem of solving linear systems, we develop
nearlylinear 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 lowstrech
spanning trees, to optimize an approach to solving linear systems
introduced by Vaidya. We thereby obtain a nearlylinear 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 ShangHua Teng.
top  contact webmaster@cs.nyu.edu
