COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Spring 2004

A torus is a surface shaped like a doughnut. A graph is toroidal if it embeds on the torus with no crossing edges. A topological obstruction for the torus is a graph G with minimum degree three that is not embeddable on the torus but for all edges e, G-e embeds on the torus. A minor order obstruction has the additional property that for all edges e, G contract e embeds on the torus.

The aim of our research is to find all the obstructions to the torus (both minor order and topological). To date, we have found 239,322 topological obstructions and 16,629 minor order obstructions. Previously, only a few thousand had been determined. This talk discusses the techniques used to find these obstructions and suggests avenues for completing this research.

Several students have participated in this research effort including John Chambers, Eugene Neufeld, Matthew Skala, Jianping Roth, Angus Argyle, Ben Ellenberger, and Hongmei Wang. Current efforts are in conjunction with Bill Kocay and Jennifer Woodcock.

Wireless sensor networks consist of a large number of tiny sensors that have only limited energy supply. One of the major challenges in constructing such networks is to maintain long network lifetime as well as sufficient sensing area. To achieve this goal, a broadly-used method is to turn off redundant sensors. In this talk, we will talk about the problem of estimating redundant sensing areas among neighbouring wireless sensors. We will present an interesting observation concerning the minimum and maximum number of neighbours that are required to provide complete redundancy and introduce simple methods to estimate the degree of redundancy without the knowledge of location or directional information. We also provide tight upper and lower bounds on the probability of complete redundancy and on the average partial redundancy. With random sensor deployment, our analysis shows that partial redundancy is more realistic for real applications, since complete redundancy is expensive, requiring up to 11 neighbouring sensors to provide a 90 percent chance of complete redundancy. Several open questions will be posed.

Graph drawing is the construction of geometric representations of graphs in two or three dimensions. It has many applications such as information visualization, VLSI design, software visualization and Bioinformatics.

Symmetry is one of the most important aesthetic criteria in graph drawing. It clearly reveals the structure of an abstract graph. The problem of determining whether a graph can be drawn symmetrically is NP-complete in general. However, the problem can be solved in polynomial time for several restricted classes of graphs such as trees, outerplanar graphs and planar graphs.

This talk briefly covers recent results in symmetric graph drawing including symmetry models, heuristics and exact algorithms for general graphs, and optimal algorithms for trees and planar graphs, both in two and three dimensions.

There are three major algorithmic problems for autonomous robots: localization, navigation, and exploration. A common feature of all three problems is that the robot must solve them with incomplete information. For example, in the navigation and exploration problem the robot has no a priori knowledge about the environment but should nevertheless find a short search or exploration path. Such problems are called online problems in theoretical computer science. Their effectiveness is usually measured by the competitive ratio which is the quotient of the cost of the online algorithm's solution over the optimal offline cost computed with full a priori knowledge.

In this talk, I will present some recent research results on the three problems mentioned above. In particular, I will discuss algorithms for geometric routing in planar graphs (an important problem in mobile ad-hoc networks), an exploration algorithm for directed planar graphs that is much more effective than the known algorithms for general directed graphs, and a general framework to transform exploration algorithms into approximation algorithms for the search ratio. The search ratio is the worst-case quotient of the distance to a goal when traveling along an exploration path over the shortest distance to the goal.

When a protein is isolated in an experiment, one would like to know whether it is already known, i.e., one would like to check whether the protein is stored in the databases of known proteins. Otherwise, if the protein is new, then we will start to investigate it from scratch.

A commonly employed approach for database lookup compares the masses of fragments of the protein (its mass fingerprint) against the proteins stored in a database. We will present and discuss efficient algorithms, that allow to compare one mass against a given protein sequence in time sublinear in the sequence length.

If the protein does not occur in the databases, we want to establish its amino acid sequence. This process is called de novo protein sequencing. There are algorithms available that can determine the correct amino acid sequence efficiently, given a noise-free tandem mass spectrum (MS/MS spectrum) of the protein. However, real-life MS/MS spectra are always prone to error, which makes the sequencing process difficult. In fact, we conjecture that a single MS/MS spectrum does not contain sufficient information to allow for reliable de novo sequencing. For this reason, we propose to develop techniques for parallel protein sequencing, where many MS/MS spectra that belong to the same protein are sequenced at once.

We survey a good deal of recent work on the set of all possible lists of multiplicities among Hermitian matrices with a given graph G. When G is a tree, there are especially strong results, and the maximum multiplicity, along with other information is known in general. A number of classes of trees for which all lists of multiplicities are known will be given, and recent results about non-trees will be indicated as well. Underlying methods, including constraints from a surprising theorem and construction techniques will be indicated.

I will first give an overview of quantum information theory and algorithms, including some of my work on quantum Fourier transforms and quantum walks. I will then explain some nonlocal effects that can arise from entangled states, and how they are related to complexity classes that are based on multi-prover interactive proof systems.

Please join us in the lounge (EOW 330) for refreshments after this talk. Dr. Cleve is a candidate for a Tier 1 Canada Research Chair in the department of Computer Science.

A matching in a graph H, may be viewed as a collection of vertex disjoint subgraphs of H, each isomorphic to K₂. Matchings are fundamental objects of study in graph theory, providing many rich examples of both structural theorems and algorithms.

Thus, it is natural to consider generalizations of matchings. To this end, let G be a fixed family of graphs. A G-packing of H is a collection of vertex disjoint subgraphs of H, each isomorphic to some member of G.

Graph packings have been extensively studied in the literature. The speaker was part of a team that initiated the study for digraphs. In this talk we will review basic results from matching theory. We will then examine digraph packing problems, presenting both structural theorems, for example analogs of Berge's Theorem and Hall's Theorem, as well as algorithmic results. We shall focus on the cases when G is a family of directed paths, and a family of oriented stars.

A t-(v, k, lambda) design is a set of v points, together with a collection of k-subsets of the points, or blocks, such that every t-subset of the points is contained in exactly lambda blocks. Existence of t-(v, k, lambda) designs containing a certain configuration D (for instance, an n-fold repeated block or two blocks meeting in exactly µ points) can be viewed as the existence of nonnegative integral solutions x to an equation W x = b, where W is a 0,1-matrix depending on the parameters v, k, t, and b is a vector depending on lambda and D. When the integrality constraint on x is dropped, the resulting necessary condition on such a design is known as the cone condition. This talk will discuss how the Farkas Lemma, when applied to the cone condition, implies some classical and some new inequalities concerning the structure of t-designs. In particular, certain polynomials with connections to design theory will be explored. This is joint work with Richard M. Wilson at the California Institute of Technology.

Landsdowne Visitor

Robert Moody will be visiting the Mathematics Department at the University of Victoria this spring as a Lansdowne Lecturer. Professor Robert Moody is one of Canada's leading mathematicians. He received the Wigner Medal in Mathematical Physics, jointly with Victor Kac (MIT). He is a Fellow of the Royal Society of Canada and an Officer of the Order of Canada. Descriptions of his three talks are given below.

People have been struggling with the problem of commensurability (finding a common measure for two magnitudes) and its opposite, incommensurability, since the ancient times, for it arises for anyone trying to fathom the great cycles of Nature. In Euclid one finds one of the oldest of all algorithms, that of finding the common measure of two magnitudes -- still used countless times everyday in public key encryption. But, as the Greeks also discovered, this algorithm is not foolproof: incommensurables exist. This incommensurability runs like a common thread through the ages and is no less interesting and puzzling nowadays where it arises in the quasicrystals and incommensurable phases of materials science as well as in the recent work on aperiodic tilings. Throughout all this the number 5 plays a charming and enigmatic role, as we shall see.

In this lecture we traverse some of these ideas from ancient to modern times and indicate some of the wonderful mathematics they have generated. The lecture is intended for a general audience, mathematical or otherwise.

This talk, intended for a general mathematical audience, will be a natural follow-up for the public lecture, now looking at the mathematics that has been developed recently to study the phenomenon of long-range aperiodic order. This will lead us through diffraction, tilings, dynamical systems, and some of the remarkable properties of discrete point sets called Meyer sets . If time permits we will say a few things about physical quasicyrstals and the problems facing theorists in that subject.

In 1991, R.Thomas posed the problem: does every large connected matroid have a large circuit or cocircuit? This problem was answered affirmatively by Lovasz, Schrijver, and Seymour who showed that for any connected matroid M with circumference c and cocircumference c*, it holds that |e(M)| <= 2^{c+c*-1}. Later Lemos and Oxley improved this bound by showing that |e(M)| <= (1/2)cc*. Oxley posed as a conjecture a stronger result: For any connected matroid M with at least 2 elements, one can find a collection of at most c*(M) cycles which cover each element of M at least twice.

We shall show the above conjecture is true for graphic matroids; that is, for any 2-connected graph G with cocircumference c*(G) there is a collection of at most c*(G) cycles which cover the edges of G at least twice (which also settles a problem raised by Oxley). The central idea is to show that for any 2-connected graph G there is a circuit which intersects every cocircuit of size c*(G). We shall discuss extensions of this and related results to matroids.

Many combinatorial optimization problems of theoretical and practical interest are NP-hard. Unless P = NP, there are no polynomial time algorithms that give optimal solutions for these problems. Hence, it is natural to try and design efficient approximation algorithms for these problems.

In this talk, I will describe my recent results in this area by focusing on two NP-hard optimization problems: a) Maximizing the number of satisfied equations in a system of linear equations mod 2 and b) Computing the best lower dimensional subspace that fits a given set of points in a high dimensional space.

These results are joint work with Johan Hastad, Kasturi Varadarajan and Jiawei Zhang.

With the current information explosion, massive data sets are now pervasive and they pose new challenges in algorithm design. For example, a linear time algorithm, which was considered as the ultimate efficiency goal for many years, could easily be unacceptably slow for massive data sets. It is thus necessary to develop algorithms that use sublinear amount of time or space resources. Recently, great progress has been made in this research direction, and the study of sublinear algorithms has emerged as a field unto itself. In computational geometry, such sublinear efficiency is traditionally achieved by performing a one-time preprocessing of the data. This is often a satisfactory solution, but is of little use when datasets are so massive that examining the whole input -- let alone preprocessing it -- is out of the question.

We initiate an investigation of sublinear algorithms in the domain of geometry and show that, for many classical geometric problems, the standard representation of the input or the standard data-structures supporting it, allow for sublinear algorithms. These algorithms randomly sample a small fraction of the input and do not require any preprocessing.

We present randomized algorithms for the following problems: detecting the intersection of convex 3D polyhedra; ray-shooting and nearest-neighbor with respect to polyhedra; point location in two-dimensional planar subdivision. All presented algorithms run in expected time O(sqrt n), where n is the size of the input. We also provide approximation algorithms with similar running times for finding the volume of a polytope and for finding the shortest path between two points on the boundary a polytope. In a different setting, we look at the well known problem of computing the weight of the minimal spanning tree in Euclidean space. We show how to approximate this weight in O(sqrt n) time. Prior to these results, the problems described above had only linear or superlinear algorithms.

The talk contains results achieved together with B. Chazelle, D. Liu, A. Czumaj, F. Ergun, L. Fortnow, I. Newman, R. Rubinfeld and C. Sohler.

We study the complexity of a well-known data structure problem called the static membership problem: Given a set of keys, S, drawn from a large underlying universe U, store S as succintly as possible so that membership queries of the form "Is q in S?" can be answered efficiently. We look at deterministic and randomized schemes for this problem and show that randomization helps.