CAG Schedule of Talks: Spring 2007

COMBINATORIAL ALGORITHMS GROUP
Schedule of Talks: Spring 2007

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca).

Schedule for Talks:

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. 24-25
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 Super-fast 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 Net-Enabled Adaptive Distributed Information Fusion for Large Volume Surveillance

Previous Talks:

An Introduction to the Bicircular Matroid and its Graphs
Nancy Ann Neudauer
Dept. of Mathematics
Pacific University, Forest Grove, Oregon
Monday Jan. 22, 2:30pm, ECS 660

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.

Random Sorting Networks
Alexander Holroyd
Mathematics Department, UBC
Currently visiting Microsoft Research
Friday Feb. 16, 2:30, Clearihue A204

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 n-item sorting network as n->infinity. We prove a law of large numbers for the space-time process of swaps. Exact simulations and heuristic arguments have led us to astonishing conjectures. For example, the half-time 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 Holder-1/2. A key tool is a connection with Young tableaux.

Primitive Pentanomials, Shift Register Sequences and Orthogonal Arrays
Brett Stevens
School of Mathematics and Statistics
Carleton University
Currently visiting at UVic
Friday March 2, 2:30pm, ECS 660

Consider a maximum-length binary shift-register sequence generated by a primitive polynomial f of degree m. Let Cnf 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, Cnf 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, Cnf corresponds to an orthogonal array of strength 3. This effectively minimizes the skew of the Hamming weight distribution of subsequences in the shift-register sequence.

Mixing Times via Super-fast Coupling
Yevgeniy Kovchegov
Department of Mathematics
Oregon State University
Friday Mar. 9, 2:30, Clearihue A204

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

Phase Transitions for Topological Properties of Random Two Dimensional Simplicial Complexes
Chris Hoffman, University of Victoria
Friday Mar. 16, 2:30, Clearihue A204

The Erdos-Renyi 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 two-dimensional analogues of the Erdos-Renyi Theorem. We construct a measure on two-dimensional 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.

Optimal Triangulation of a Polygon Using Steiner Points
Tetsuo Asano
Japan Advanced Institute of Science and Technology (JAIST)
Friday March 23, 2:30pm, ECS 660

It is rather easy to triangulate a simple n-gon 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 polynomial-time 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.

Convergence and Approximation in Games
Vahab S. Mirrokni
Theory Group, Microsoft Research
Monday March 26, 2:30pm, ECS 660

This talk will survey recent results on convergence to approximate solutions in games. For potential games in which a sequence of best-responses 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 non-potential games, we introduce sink equilibria based on the convergence of the best-response moves of players and study the properties of this equilibrium concept. The talk is mainly based on three papers in this area co-authored with A. Vetta, M. Goemans, G. Christodoulou, and A. Sidiroupolous.

Teaching Games
Brett Stevens
School of Mathematics and Statistics, Carleton University
Currently visiting at the University of Victoria
Thursday April 26, 3:30, ECS 660

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 Lights-Out 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).

Net-Enabled Adaptive Distributed Information Fusion for Large Volume Surveillance
Adel Guitouni
Decision Support System Section, Defence R&D Canada
Adjunct Professor with the Business School, UVic
Friday May 4, 3:30pm, Clearihue C112

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 non-cooperative 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 (CP-140), 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 sub-set of these objects and possible intelligence reports about specific behaviours to be identified.

This NSERC-Industry 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, net-enabled 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.


CAG Schedule of Talks: Spring 2007 / maintained by Wendy Myrvold / wendym@cs.UVic.ca / revised May 3, 2007