Talks from previous semesters
2004 Fall term grand opening: Monday SEPTEMBER 13
Monday, September 13, 2004, 4:30
Speaker:
Thorsten Theobald
Title:Algebraic methods in computational geometry
Abstract:
The aim of this talk is to exhibit some classes of problems
from computational geometry which lead to fundamental
problems from (real-)algebraic geometry.
The initial problems include visibility computations with
moving viewpoints in 3-space or the computation of
smallest enclosing cylinders of polytopes. These problems
lead to enumerative questions concerning the lines
simultaneously tangent to given bodies.
In particular, we discuss these problems for the case that the
set of admissible bodies consist of balls and polytopes.
Monday, September 20, 2004, 4:30
Speaker: Michael Elkin (Yale)
Title (1 + a,b)$-Spanner Constructions for General Graphs
The topic of this seminar is how well a sparse subgraph
$G' = (V,H)$ of an unweighted undirected graph $G = (V,E)$
may "approximate" the distances between nodes that are
"far away" one from another in $G$.
If one is interested in approximating all the distances by a subgraph,
then there is a well-understood tradeoff between the sparsity of the
subgraph and the quality of approximation.
We show that under a somewhat relaxed requirement of approximating
only the distances between pairs of nodes that are "far away" in $G$
(we mean that the distance between them is at least certain threshold
that does not depend on the number of nodes in the graph)
the sparsity of the subgraph and the quality of approximation
can be made arbitrarily small simultaneously.
The tradeoff that we present is between the sparsity of the subgraph and
the quality of the approximation on the one hand, and the
value of the threshold that we mentioned above on the other.
The talk is based on a paper joint with David Peleg.
The paper appeared in STOC 2001, and in SICOMP 2004.
Monday, September 27, 4:30 AKW (CS building) room 200
Van Vu (UCSD):
Divide and Conquer Martingales and Distribution of random Polytopes
Let K be convex body with volume one in R^d. Choose n random points
in K with respect to the uniform distribution. The convex hull of these
points, denoted by K_n, is a random polytope.
The study of K_n was started by Renyi-Sulanke and Efron about 40 years
ago. The goal of this study is to understand the distribution of the key
functionals of K_n (such that its volume or its number of vertices).
The espectations of most functionals are known, but little has been
achieved beyond this. For instance, there are very few results about
higher moments. The main obstacle is that the geometric methods which are
efficient for computing the expectation become very difficult to apply
for other purposes.
In this talk, we are going to introduce a new method by
which one can give
fairly accurate estimates concerning the distributions of key functionals
of K_n. This helps us to answer several open questions, including the one
above about moments. The main tool of
our method is the so-called "Divide and Conquer Martingale" technique, a
refinement of Azuma's inequality.
Monday, October 4, 2004, 4:30 AKW 200:
Benny Sudakov (Princeton): Dependent random choice and Ramsey-Turan type problems
The Probabilistic Method is a powerful tool in tackling many problems in
Combinatorics and it belongs to those areas of mathematical research that have
experienced a most impressive growth in recent years. One of the parts of
discrete mathematics where this approach has proved to be especially useful is
Extremal Combinatorics. In fact, many of the strongest results in this area in
the last few decades are examples of this method.
In this talk we discuss a few recent applications of this methodology. In
particular, we present simple but yet surprisingly powerful probabilistic
arguments which were used recently to make progress on some long-standing
Ramsey and Tur\'an type problems.
Monday, October 11, 2004, 4:30 AKW 200:
Helene Barcelo (ASU): Hyperplanes arrangements
During the last 30 years, hyperplane arrangements have been the subject
of a very active area of research in Combinatorics.
In this talk we will not attempt the impossible task of
giving a general survey of this discipline.
Rather, we will present some selected results and techniques that
we believe convey the depth and beauty of this subject.
Monday, October 18, 2004, 4:30 AKW 200
Dan Spielmen (Yale and MIT) Low-Stretch Spanning Trees
A low-stretch spanning tree T of a graph G is a spanning tree subgraph
in which most edges of G can be routed with small dilation. In
particular, the stretch of an edge of G in T is the length of the path
in T connecting the endpoints of that edge. The average stretch
is the average over edges in G of their stretch.
In an analysis of an algorithm for the k-server problem, Alon, Karp,
Peleg and West showed that there exist spanning trees of average
stretch 2^(O(sqrt(n)). We were motivated to improve their
construction because this average-stretch is the dominant term
in the complexity of a new solver for diagonally-dominant
systems of equations.
We present a O(m log^2 n)-time algorithm that constructs
trees of much lower average stretch: O(log^2 n).
The algorithm is simple, so the talk should be short.
Joint work with Michael Elkin and Shang-Hua Teng.
Monday, October 25, 2004
Santosh Vempala (MIT): How to Compute the Volume?
Computing the volume of a geometric body is an ancient, basic and
surprisingly difficult task. Even for convex bodies in n-dimensional
space, no polynomial-time deterministic algorithm can approximate the
volume to within a factor that is exponential in n. On the other hand,
Dyer, Frieze and Kannan showed that, using randomness, the volume can be
approximated to arbitrary accuracy in polynomial time (the 23rd power of n).
This remarkable result has been improved several times; each improvement
has yielded new techniques for algorithm design and has contributed to
classical fields such as geometry and probability. In this talk, we will
discuss the history of the volume problem, illustrate its difficulty and
describe the latest algorithm whose complexity grows as the 4th power of n.
The key ingredients of the algorithm are: (1) a method for rapidly
"morphing" one convex body into another and (2) a geometric random walk
that "mixes" rapidly from any starting point inside a convex body (the
only walk known to have this property).
Monday, November 1, 2004
Jon Kelner (MIT): Spectral partitioning, eigenvalue bounds,
and circle packings for graphs of bounded genus
In this paper, we address two longstanding questions about finding
good separators in graphs of bounded genus and degree:
1. It is a classical result of Gilbert, Hutchinson, and Tarjan that
one can find asymptotically optimal separators on these graphs if he
is given both the graph *and* an embedding of it onto a low genus
surface. Does there exist a simple, efficient algorithm to find these
separators given only the graph and not the embedding?
2. In practice, spectral partitioning heuristics work extremely well
on these graphs. Is there a theoretical reason why this should be the
case?
We resolve these two questions by showing that a simple spectral
algorithm finds separators of cut ratio O(\sqrt{g/n}) and vertex
bisectors of size O(\sqrt{gn}) in these graphs, both of which are
optimal. As our main technical lemma, we prove an O(g/n) bound on the
second smallest eigenvalue of the Laplacian of such graphs and show
that this is tight, thereby resolving a conjecture of Spielman and
Teng. While this lemma is essentially combinatorial in nature, its
proof comes from continuous mathematics, drawing on the theory of
circle packings and the geometry of compact Riemann surfaces.
Past Related Talks
Thursday, November 4, 2004, 4:15 pm, AKW200
Michael Mahoney (Yale): The CUR Matrix Decomposition with Applications to Algorithm
Design and
Massive Data Set Analysis
Motivated by applications in massive data set analysis and
algorithm design,
we are interested in developing and analyzing fast Monte Carlo
algorithms
for performing useful computations on large matrices. Of particular
interest
is the compressed approximate CUR matrix decomposition. After
describing the
CUR matrix decomposition, we describe how it can be used to design an
improved
approximation algorithm for the Max-Cut problem. We then focus on
applications
of the CUR decomposition to the analysis of large scientific data sets.
In
particular, we describe how extensions of the CUR decomposition may be
used for
improved kernel-based statistical learning and for the efficient
approximation
of massive tensor-based data sets. This may then be coupled with more
traditional and/or refined methods of data set analysis in order to
construct
in a principled manner a "sketch" of an extremely large data set and
then to
perform more refined field-specific analysis on the sketch; recent work
along
this direction will be discussed.
April 7, 2005
Andrew Yao (Tsinghua): Directions in Theoretical Computer
Science
Related Talk: April 28, 2005, 10:30 a.m.
Moses Charikar (Princeton)
Title: Metrics, embeddings and all that.
Abstract: A metric space is simply a collection of objects associated
with a distance function. Several metrics arise naturally in Computer
Science--for instance, Hamming distance on bit vectors, Euclidean distance
on points, and edit distance on strings. From an algorithmic standpoint, some
of these metrics are much easier to deal with than others. A natural question
that arises here is whether "complicated" metrics can be mapped to "simpler"
metrics in some way. Such mapping (metric embeddings) were originally
studied in functional analysis. In the last decade, the discovery of
several algorithmic applications have triggered a great interest in these
questions in Computer Science.
So, what is the excitement all about? In this talk, I will show how various
incarnations of metric embeddings arise in basic optimization problems
in graphs. I will also show how dimension reduction and compact
representation techniques from embeddings give rise to a powerful
algorithmic toolkit for dealing with large data sets. Enroute, we will
see some of the classical results in this area as well as some of the
exciting new developments from the past few years.
No prior background will be assumed.