Yale Discrete Mathematics Seminar - Mondays 4:30 AKW 200

... And Other talks on Discrete mathematics at Yale.

http://cs-www.cs.yale.edu/homes/kalai/ysem.html

YALE 2004 WORKSHOP on DISCRETE MATHEMATICS and THEORETICAL COMPUTER SCIENCE. Monday, October 18, 2004, 4:30 AKW 200: Workshop's theme: Harmonic Analysis of Boolean functions. Dates: Monday afternoon, September 27, 2004 until Wednesday, September 29, 2004.

YALE 2005 WORKSHOP on DISCRETE MATHEMATICS and THEORETICAL COMPUTER SCIENCE. tentative theme: linear programming and polytopes. tentative dates: Monday afternoon, September 26, 2005 until Wednesday, September 28, 2005.

Monday, October 18, 2004, 4:30 AKW 200:

Dan Spielmen (Yale and MIT) Low-Stretch Spanning Trees

abstract:

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.

Future talks:

October 25: Santosh Vampala

Old talks:

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.

Discrete Math and theoretical CS seminar

Monday, September 27, 4:30 AKW (CS building) room 200

Van Vu

Title: Divide and Conquer Martingales and Distribution of random Polytopes

Abstract 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: Dependent random choice and Ramsey-Turan type problems

Abstract:

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

Abstract:

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.