A demonstration will be given of the current state of the system. The talk will conclude with ideas for future enhancements. This is joint work with Bette Bultena, Sean Daugherty, Patrick Fowler, Sameer Girn, Marsha Minchenko, and Jennifer Woodcock.

We introduce an old, and somehow, widely overlooked, result of Vladimir Muller about uniquely colourable graphs. We show how this result can be used to get results dealing with such things as Ramsey Theory, Colour Critical (Hyper-)graphs, and Graph Homomorphisms.

Given a set E in Rⁿ, what can we say about the lower bounds on the size of the set Delta(E) of all possible distances between pairs of points in E, depending on the size of E itself? For discrete sets, this is a notorious unsolved combinatorial problem due to Erdos; there is also a continuous version, due to Falconer, where the best results so far have been obtained by Fourier-analytic methods. Although the main conjectures remain open, recent years have seen significant progress on these and other closely related questions. In this talk, I will review the recent work on the distance set problem, its variants (non-Euclidean distance functions, averaging estimates), and connections to other well known problems such as the restriction conjecture.

Planar graphs are of interest in combinatorics and geometry but also physics (referred to as 2-dimensional quantum gravity). Geometrically, they may be seen as discretized surfaces. Random maps are a model for a "typical" 2 dimensional surface, with no imposed Euclidean structure. A fundamental question is to understand the scaling limit of such maps.

I will present my exploration process for planar maps, and some of the results that can be derived by using it. In particular, the ball of radius R typically has volume of order R4, suggesting that a "typical" surface has Hausdorff dimension 4. Critical percolation on the maps can also be analyzed, resulting in an analogue of Cardy's formula.

Refreshments will be served in CLE D-252 at 3:30 p.m.

Node-to-node latencies can be seen as a notion of distance in networks such as the Internet. For a number of applications it is useful to represent this distance via coodinates in a low-dimensional Euclidean space and, moreover, compute these coordinates in a decentralized fashion, with low overhead on participating nodes. In particular, each node is allowed only a near-constant number of distance measurements. This is in sharp contrast with existing theoretical work on metric embeddings which assumes full (and centralized) access to the distance matrix.

Here we show how to extend theoretical guarantees for embedding to this decentralized setting. We also consider a more basic problem of 'triangulation', in which one uses the triangle inequality to infer the distances that have not been measured. We also report on some successes of this style of analysis in the context of a deployed system.

We study the problem of exploring an unknown, strongly connected directed graph. Starting at some vertex of the graph, we must visit every edge and every vertex at least once. The goal is to minimize the number of edge traversals. It is known that the competitive ratio of online algorithms for this problem depends on the deficiency d of the graph, which is the minimum number of edges that must be added to make the graph Eulerian. We present the first deterministic online exploration algorithm whose competitive ratio is polynomial in d (it is O(d⁷)).

This is joint work with Rudolf Fleischer, Fudan University, Shanghai.

In this talk, I will point out the success of using nonabelian automorphism groups to reduce the search space for a certain problem in combinatorial design theory.

The problems of Byzantine Agreement and Leader Election have been well-studied in the area of distributed algorithms where there is a subset of processors controlled by a malicious adversary. The first requires that all uncorrupted come to an agreement on a bit initially held by one of the uncorrupted processors; the second requires that the uncorrupted processors choose a leader who is uncorrupted.

In order to get around quite large lower bounds in the case of Byzantine Agreement, and impossibility in the case of Leader Election, researchers have resorted to a randomized model with some probability of failure. Typically these protocols use rounds where every uncorrupted processor broadcasts to all the other processors.

In this talk, we consider what happens if we limit the number of point-to- point communications to a polylogarithmic number for uncorrupted processors, but allow corrupted processors to send as many bits as they like. We show upper bounds and lower bounds, but the most fundamental questions remain open.

This is joint work with Holtby and Kapron, and also Saia, Sanwalani, and Vee.