COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Summer 2006

We show that a family of generalized meta-Fibonacci sequences arise when counting the number of leaves at the largest level in certain infinite sequences of k-ary trees and restricted integer compositions. For this family of generalized meta-Fibonacci sequences and two families of related sequences we derive ordinary generating functions and recurrence relations.

(Research with Chris Deugau).

Necklaces are strings that are lexicographically-smallest under rotation; they are well-studied 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 arbitrarily-large 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.

Previous Talks:

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 non-syntactic 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 zero-sided error, quantum machines with one- or zero-sided error, unambiguous machines, symmetric alternation, Arthur-Merlin 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 two-sided 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 edge-weighted 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 edge-weights in T is bounded by B. Hollemans provides NP-completeness for MBC when V is a subset of Z+ x Z+ and the edge-weights are the square Euclidean lengths (EMBC). We show that EMBC parameterized by B is solvable in fixed-parameter-tractable time using a bounded search-tree algorithm based on Gaussian-Circle 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 bit-sliced 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 n-Venn diagram of convex k-gons, we prove that k >= ( 2^n - 2 - n ) / ( n (n-2)). 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 7-Venn diagram of non-convex 5-gons [``Venn Diagrams II'', Geombinatorics 2:25-31, 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, G-e 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.