CAG Schedule of Talks: Spring 2006

Schedule of Talks: Spring 2006

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (

Schedule for Talks:

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?

Previous Talks:

Fuigui: A Graphical User Interface for Investigating Conjectures About Fullerenes
Wendy Myrvold
Friday Jan. 27, 2:30pm, Clearihue A 207

Fullerenes are all-carbon molecules whose molecular structures correspond to 3-regular 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:

  • Making the system fully interactive, fast and fun to play with.
  • Plug and play parameters- a user can add his or her own fullerene parameters without changing the code for fuigui.
  • Drawing pictures which are pleasing to the chemists.
  • Facilitating animated algorithms.

    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.

    Some uses of uniquely colourable graphs
    Mark Siggers
    Friday Feb. 17, 2:30, EOW 430

    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.

    Distance sets: combinatorics and Fourier analysis
    Izabella Laba
    Department of Mathematics, UBC
    2:30, Tues. Feb. 28, DSB C 116

    Given a set E in Rn, 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.

    Scaling of Random Planar Graphs
    Omer Angel
    Department of Mathematics, UBC
    4:00, Tues. Feb. 28, Elliott 162

    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.

    Triangulation and Embedding using Small Sets of Beacons
    Aleksandrs Slivkins
    Department of Computer Science
    Cornell University
    1:30pm, Tuesday March 14, EOW 430

    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.

    Exploring an Unknown Graph Efficiently
    Gerhard Trippen
    Department of Computer Science
    Hong Kong University of Science and Technology
    2:45pm, Friday March 17, EOW 430

    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(d7)).

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

    An application of computer search with nonabelian automorphism groups
    Peter Dukes
    2:30pm, Friday March 24, EOW 430

    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.

    Is Scalable Distributed Computing Possible?
    Valerie King
    Friday Mar. 31, 2:30pm, Clearihue D 131

    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.

    CAG Schedule of Talks: Spring 2006 / maintained by Wendy Myrvold / / revised Apr. 11, 2006