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. 22  ECS 660  2:30  Nancy Ann Neudauer  An Introduction to the Bicircular Matroid and its Graphs 
Feb. 16  Cle A204  2:30  Alexander Holroyd  Random Sorting Networks 
Feb. 23  No CAG  Coast Combinatorics Conference, Feb. 2425  
Mar. 2  ECS 660  2:30  Brett Stevens  Primitive Pentanomials, Shift Register Sequences and Orthogonal Arrays 
Mar. 9  Cle A 204  2:30  Yevgeniy Kovchegov  Mixing Times via Superfast Coupling 
Mar. 16  Cle A 204  2:30  Chris Hoffman  Phase Transitions for Topological Properties of Random 2D Simplicial Complexes 
Mar. 23  ECS 660  2:30  Tetsuo Asano  Optimal Triangulation of a Polygon Using Steiner Points 
Mar. 26  ECS 660  2:30  Vahab S. Mirrokni  Convergence and Approximation in Games 
Apr. 26  ECS 660  3:30  Brett Stevens  Teaching Games 
May 4  Cle C112  3:30  Adel Guitouni  NetEnabled Adaptive Distributed Information Fusion for Large Volume Surveillance 
Matroids are everywhere. Vector spaces are matroids. Matroids are useful in situations that are modelled by both graphs and matrices. Bicircular matroids model generalized network flow problems whose algorithms are more efficient than those available for general linear programming codes.
Let G be a graph (loops and parallel edges allowed) with vertex
set V={1,2,...,n} and edge set E. In the classical matroid associated
with a graph, a set of edges is independent in the matroid if it
contains no cycles, and the circuits of the matroid are the single
cycles of G. The bicircular matroid of G is the matroid B(G) defined
on E whose circuits are the subgraphs which are subdivisions of one
of the graphs:
(i) two loops on the same vertex,
(ii) two loops joined by an edge,
(iii) three edges joining the same pair of vertices.
The bicircular matroid is known to be a transversal matroid and thus can be represented by a family of sets, called a presentation. Given a transversal matroid, we can determine whether it is bicircular. I will show that, given any presentation of a bicircular matroid, we can find a graph representing the matroid, and that, in some cases, there is more than one graph. We investigate how the graphs representing a bicircular matroid are related, and what this means in terms of their presentations as transversal matroids.
Sorting a list of items is perhaps the most celebrated problem in computer science. If one must do this by swapping neighboring pairs, the worst initial condition is when the n items are in reverse order, in which case n choose 2 swaps are needed. A sorting network is any sequence of n choose 2 swaps which achieves this.
We investigate the behavior of a uniformly random nitem sorting network as n>infinity. We prove a law of large numbers for the spacetime process of swaps. Exact simulations and heuristic arguments have led us to astonishing conjectures. For example, the halftime permutation matrix appears to be circularly symmetric, while the trajectories of individual items appear to converge to a famous family of smooth curves. We prove the more modest results that, asymptotically, the support of the matrix lies within a certain octagon, while the trajectories are Holder1/2. A key tool is a connection with Young tableaux.
Consider a maximumlength binary shiftregister sequence generated by a primitive polynomial f of degree m. Let C_{n}^{f} denote the set of all subintervals of this sequence with length n, where m < n <= 2m, together with the zero vector of length n. Munemasa [MR1640769] considered the case in which the polynomial f generating the sequence is a trinomial satisfying certain conditions. He proved that, in this case, C_{n}^{f} corresponds to an orthogonal array of strength 2 that has a property very close to being an orthogonal array of strength 3. Munemasa's result was based on his proof that very few trinomials of degree at most 2m are divisible by the given trinomial f. In this talk, we consider the case in which the sequence is generated by a pentanomial f satisfying certain conditions. Our main result is that no trinomial of degree at most 2m is divisible by the given pentanomial f, provided that f is not in a finite list of exceptions we give. As a corollary, we get that, in this case, C_{n}^{f} corresponds to an orthogonal array of strength 3. This effectively minimizes the skew of the Hamming weight distribution of subsequences in the shiftregister sequence.
We provide a coupling proof that the transposition shuffle on a deck of n cards is mixing of rate n\log(n) with a moderate constant. This has already been shown by Diaconis and Shahshahani but no natural coupling proof has been demonstrated to date. We also enlarge the methodology of coupling to include intuitive but nonadapted coupling rules, for example, to take in account future events and to prepare for their occurrence. This is joint work with R.Burton)
The paper for this talk can be found on Math ArXiv at http://front.math.ucdavis.edu/math.PR/0609568
The ErdosRenyi random graph G(n,p) is the probability measure on all graphs on the vertex set [n]={1,2,...n}, with each edge inserted independently with probability p. Usually p is defined to be a function of n, and one asks whether a graph in G(n,p) is likely to have some (monotone) property as n goes to infinity. In their seminal 1959 paper, Erdos and Renyi showed that if p << log(n)/n then G(n,p) is almost always disconnected, but if p >> log(n)/n, then it is almost always connected. We view this as a topological statement and seek twodimensional analogues of the ErdosRenyi Theorem. We construct a measure on twodimensional simplicial complexes and look at two questions about phase transitions for topological properties. For which values of p is the random complex almost always simply connected, and for which values of p does the random complex almost always have trivial homology? This is based on joint work with Matt Kahle and Eric Babson.
It is rather easy to triangulate a simple ngon even under some optimization criterion, such as maximization of the smallest internal angle. A problem we consider in this talk is just a simple extension. Given a simple polygon P and one point p in its interior, we can again find an optimal triangulation maximizing the smallest internal angle just by applying a constrained Delaunay triangulation algorithm. We can associate the smallest angle with the point p. Now, our problem is to find a point that optimizes the evaluation. It looks easy, but no straightforward dynamic programming works. We present a polynomialtime algorithm for the problem. We also show that the result can be extended to a problem of finding where to insert two points to optimize the resulting triangulation in polynomial time in n. A practical heuristic approach called Pixel method is also presented.
This is joint work with Boris Aronov and Stefan Funke.
This talk will survey recent results on convergence to approximate solutions in games. For potential games in which a sequence of bestresponses converge to a pure Nash equilibrium, we study the speed of convergence to efficient solutions in three classes of congestion games, selfish scheduling games, and cut games. For nonpotential games, we introduce sink equilibria based on the convergence of the bestresponse moves of players and study the properties of this equilibrium concept. The talk is mainly based on three papers in this area coauthored with A. Vetta, M. Goemans, G. Christodoulou, and A. Sidiroupolous.
In the Fall of 2006 at Carleton University, I taught a course entirely using Games and Puzzles as the context for learning mathematics and theoretical computer science. We looked at LightsOut type games , Shannon's Switching Games , Chinese Rings, and Towers of Hanoi, Sudoku, Card Tricks and the Rubik's Cube. We looked at Linear Algebra, Matroids and Graphs, Gray Codes, Latin Squares, linear feedback shift registers, and permutation groups. I will discuss my experiences with the course; what worked best; what I would change and give references to relevant material for those interested in including games and puzzles into their classes.
Refreshments will be served in the Computer Science Lounge next to the seminar room at 3:00 pm.
A bibliography for this talk is available (brett.pdf).
The large volume surveillance problem is characterised by the employment of mobile and fixed surveillance assets to a large geographic area in order to identify, assess and track the maximum number of moving, stopped or drifting objects. The observed objects are not necessarily aware of being observed and are cooperative or noncooperative and friendly or hostile. Coastal and Arctic surveillance are good examples of large volume surveillance. The scarce surveillance and tracking capabilities (e.g. sensors) makes it very difficult to perform large volume surveillance and to keep tracking all activities. The question is therefore how to improve employment of a set of surveillance and patrolling assets, their networking capabilities and fusion engines in order to address large volume surveillance challenges.
This project assumes that available Intelligence, Surveillance and Reconnaissance (ISR) platforms include the long range patrol aircrafts (CP140), Canadian Forces warships (Frigate and Coastal Patrol Ship), Helicopters, Unmanned Aerial Vehicles (UAVs), CoastGuard ships, Fishery and Ocean, RCMP and other Government departments (OGDs) surveillance resources. These resources have multiple networking capabilities allowing them to exchange information. The volume to be surveyed is very large, thus deploying all the resources will not guarantee full and seamless coverage at all times. At any given time there are many observable dynamic and static objects traveling in that volume. These objects have different characteristics and behaviours. They might appear during an interval of time in the surveyed volume (entrance and exit time windows). A priori information includes identification of a subset of these objects and possible intelligence reports about specific behaviours to be identified.
This NSERCIndustry funded project proposes to use distributed information fusion algorithms coupled with decision support tools to address the issues of large volume coastal surveillance. In particular, adaptive fusion, dynamic resource allocation, and configurable network management are combined to form a unique distributed information fusion approach. Tasks will be naturally determined or dynamically allocated as a result of an outcome or changes in current status. The project can be used to pioneer research in the strategic direction of large volume surveillance. It also fills the niche of Canadian needs in the defence, security and information industries for a more autonomous surveillance system.
In this presentation, the project, its motivations and the work plan are discussed. Some initial results are also presented.
About the speaker:
Dr. A. Guitouni is a defence scientist with Defence R&D Canada Valcartier and Atlantic since 1998. He is specialised in the domain of decision support systems, operational research and artificial intelligence. His work includes planning and optimisation, automated classification, decision analysis, multiple criteria decision aids, netenabled dynamic resource management, and collaborative decision making (planning). He is an adjunct professor with Laval University, Sherbrooke University, Concordia University and University of Victoria. He has supervised Ph.D., M.Sc. and MBA students.