COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca).
Date  Place  Time  Speaker  Abbreviated Title 

Jan. 27  Cle A 207  2:30  Wendy Myrvold  Fuigui: Fullerene Interactive Graphical User Interface 
Feb. 17  EOW 430  2:30  Mark Siggers  Some uses of uniquely colourable graphs 
Feb. 24  _  _  No CAG  Reading Break. 
Feb. 28  DSB C 116  2:30  Isabella Laba  Distance sets: combinatorics and Fourier analysis 
Feb. 28  Ell 162  4:00  Omer Angel  Scaling of Random Planar Graphs 
Mar. 10  _  _  No CAG  SE Conference 
Mar. 14  EOW 430  1:30  Aleksandrs Slivkins  Triangulation and Embedding using Small Sets of Beacons 
Mar. 17  EOW 430  2:45  Gerhard Trippen  Exploring an Unknown Graph Efficiently 
Mar. 24  EOW 430  2:30  Peter Dukes  An application of computer search with nonabelian automorphism groups 
Mar. 31  Cle D 131  2:30  Valerie King  Is Scalable Distributed Computing Possible? 
Fullerenes are allcarbon molecules whose molecular structures correspond to 3regular planar graphs that have face sizes equal to five or six. Fuigui (Fullerene Interactive Graphical User Interface) is a java program under development whose goal is to aid the exploration of fullerenes and their parameters. Some of the design challenges covered in this talk are:
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^{n}, 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 Fourieranalytic 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 (nonEuclidean 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 2dimensional 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 D252 at 3:30 p.m.
Nodetonode 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 lowdimensional 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 nearconstant 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
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 wellstudied 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 pointto 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.