COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca).
On Friday Sept. 1, Frank Ruskey and Mark Weston will both present short talks in preparation for a conference.
We show that a family of generalized metaFibonacci sequences arise when counting the number of leaves at the largest level in certain infinite sequences of kary trees and restricted integer compositions. For this family of generalized metaFibonacci sequences and two families of related sequences we derive ordinary generating functions and recurrence relations.
(Research with Chris Deugau).
Necklaces are strings that are lexicographicallysmallest under rotation; they are wellstudied objects with many applications. Recently, a Gray code for binary necklaces and their relatives was discovered by Vajnovszki [J. of Automata, Languages and Combinatorics, to appear]. The Gray code is constructed by modifying the classical FKM algorithm for generating necklaces in lexicographic order. We present a generalisation of Vajnovszki's algorithm, giving a Gray code for necklaces and their relatives over an arbitrarilylarge alphabet. Each string in the resulting code differs from adjacent strings in at most three positions. To our knowledge this is the first Gray code for necklaces of arbitrary base.
This is joint work with Vincent Vajnovszki.
A basic question in computational complexity asks whether somewhat more time allows us to solve strictly more decision problems on a given model of computation. Despite its fundamental nature, the question remains unanswered for many models of interest. Essentially, time hierarchies are known for every syntactic model of computation but open for everything else, where we call a model syntactic if there exists a computable enumeration consisting exactly of the machines in the model.
There has been significant progress in recent years, namely in establishing time hierarchies for nonsyntactic models with small advice. In this talk, we survey these results and present a generic theorem that captures and strengthens all of them. We show that for virtually any semantic model of computation and for any rationals 1 <= c < d, there exists a language computable in time n^d with one bit of advice but not in time n^c with one bit of advice, where we call a model semantic if there exists a computable enumeration that contains all machines in the model but may also contain others.
Our result implies the first such hierarchy theorem for randomized machines with zerosided error, quantum machines with one or zerosided error, unambiguous machines, symmetric alternation, ArthurMerlin games of any signature, etc. Our argument also yields considerably simpler proofs of earlier hierarchy theorems with one bit of advice for randomized or quantum machines with twosided error.
Based on joint work with Konstantin Pervyshev.
On Friday June 23, six short talks were presented in preparation for the SIAM conference.
Given a complete edgeweighted graph G=(V, E) with source s in V and bound B, Minimum Energy Broadcast Cover asks for a directed spanning tree T for G rooted at s, such that the sum of edgeweights in T is bounded by B. Hollemans provides NPcompleteness for MBC when V is a subset of Z+ x Z+ and the edgeweights are the square Euclidean lengths (EMBC). We show that EMBC parameterized by B is solvable in fixedparametertractable time using a bounded searchtree algorithm based on GaussianCircle formulas.
This is joint work with Anissa Agah St. Pierre and Ulrike Stege.
We present algorithms that exhaustively generate primitive and irreducible polynomials over GF(3), GF(4) and GF(5). Polynomials are represented as computer words and we have determined optimal bitsliced strategies for addition over GF(3) and GF(4). Using tables created by these programs we discuss some conjectures concerning the enumeration of restricted classes of irreducible and primitive polynomials over GF(3).
Fuigui (Fullerene Interactive Graphical User Interface) is a java program under development whose goal is to facilitate research on the graphs which represent fullerenes and on their parameters. This talk will include a selection of interesting open problems about various fullerene parameters. A demonstration of how Fuigui can be used to attack these will be provided.
This is joint work with Bette Bultena, Sean Daugherty, Brad Debroni Patrick Fowler, Sameer Girn, Marsha Minchenko, and Jennifer Woodcock.
Venn diagrams and their close relatives, the Euler diagrams, form an important class of combinatorial objects which are used in set theory, logic, and many applied areas. Convex polygons are fundamental geometric objects that have been investigated since antiquity. This paper addresses the question of which convex polygons can be used to create Venn diagrams of certain numbers of curves. We establish a new lower bound for the number of sides required for the component curves of simple Venn diagrams made from polygons. Specifically, for any nVenn diagram of convex kgons, we prove that k >= ( 2^n  2  n ) / ( n (n2)). In the process we prove that Venn diagrams of seven curves, simple or not, cannot be formed from triangles. We then give an example achieving the new lower bound of a (simple, symmetric) Venn diagram of seven quadrilaterals. Previously Grunbaum had constructed a 7Venn diagram of nonconvex 5gons [``Venn Diagrams II'', Geombinatorics 2:2531, 1992].
The Josephus Problem is well studied in Computer Science and Discrete Mathematics. In this talk we generalize the Josephus Problem by introducing a uniform weight to each element, and we prove two interesting results.
The aim of our research is to facilitate searching for all torus obstructions (graphs G with minimum degree three that do not embed on the torus but for all edges e, Ge embeds on the torus) by determining small obstructions using a computer search. Polynomial time algorithms have been proposed, but are complex and implementations are not yet available. This talk describes a new exponential algorithm, based on Demoucron's planarity testing algorithm, that is faster in practice than other implemented alternatives.
This is joint work with Wendy Myrvold.
We all know that fast hardware can help us compute faster, and usually we simply think of buying a faster processor. We also know that it is infeasible to have a custom circuit designed and implemented for our particular algorithm. Now reconfigurable hardware has come along to change this infeasibility to a possibility, and we'll explain how to do it, without resorting to any hardware knowledge.
We will illustrate the technique using Gilbert Lee's circuit, which is the basis of an algorithm for the construction of irreducible and primitive polynomials over GF(3). The software implementation of the circuit is extremely efficient. Another hardware solution, but using a different circuit and with a cryptographic application, was also proposed through reconfigurable hardware by some researchers in the UK.
The challenge was to beat the timing of both implementations. Here we explain how and why, and propose new ideas on how to exploit this fairly new technological approach further to other computationally intensive problems.
Virtual Private Networks (VPNs) provide customers with predictable and secure network connections over a shared network. The Hose model for VPN configuration alleviates the scalability problem of the Pipe model by reserving bandwidth for aggregates instead of between every pair of endpoints. Existing studies on quality of service guarantees in the Hose model either deal only with bandwidth requirements or take delay requirement as the basic and scarifies bandwidth cost. In this work we enhance the Hose model to guarantee delay requirements between endpoints while optimizing the provisioning bandwidth cost. Our proposed approach takes the user preferences in meeting the delay requirements and provisioning cost to find the optimal solution of resource allocation with small computation overhead.