COMBINATORIAL ALGORITHMS GROUP

If you would like to give a talk in our seminar series, please contact Wendy Myrvold (wendym@cs.uvic.ca). To get email notification of our seminars and other events, you can subscribe to the CAG email list at http://mailman.csc.uvic.ca/mailman/listinfo/cag
Date  Place  Time  Speaker  Abbreviated Title 

Tues. Sept. 15  3:30pm  Ell 168  Jonathan Borwein  Exploratory Experimentation and Computation 
Thurs. Sept. 17  3:30pm  Cor A 221  Ruth Hass  The Center for Women in Mathematics at Smith College 
Fri. Sept. 18  2:00pm  Mac D 101  Andrew Fish  Efficient Region Computations and Visual Classification with Euler Diagrams 
Tues. Sept. 22  10:30am  ECS 660  Holger H. Hoos  Taming the complexity monster 
Fri. Sept. 25  2:30pm  ECS 660  Benjamin Young  Some new applications of the domino shuffling algorithm 
Fri. Sept. 25  3:30pm  DSB C 108  Hyam Rubinstein  Optimising access in underground mine design. 
Fri. Oct. 2  2:30pm  _  No CAG.  
Thurs. Oct. 22  3:30pm  HSD A240  Ronald Graham  Bubblesort and Juggling Sequences 
Fri. Nov. 6  2:30pm  ECS 660  Sandra Zilles  Sampleefficient learning from cooperative teachers 
Fri. Nov. 21  _  _  No CAG  Combinatorial Potlatch 
Fri. Nov. 27  2:30pm  ECS 104  Wendy Myrvold  The End to the Keller Conjecture 
Fri. Nov. 27  2:30pm  ECS 104  Jenni Woodcock  Counting FixedHeight Tatami Tilings 
Fri. Dec. 4  2:30pm  ECS 104  Andrew Yao  DVD: Communication Complexity and Its Applications 
Mon. Dec. 21  2:00pm  ECS 660  Takeo Nishizeki  Small Grid Drawings of Planar Graphs with Balanced Bipartition 
In a grid drawing of a planar graph, every vertex is located at a grid point, and every edge is drawn as a straightline segment without any edgeintersection. It has been known that every planar graph G of n vertices has a grid drawing on an (n2)x(n2) integer grid and such a drawing can be found in linear time. In this talk, we show that if a planar graph G has a balanced bipartition then G has a grid drawing with small grid area. More precisely, if a separation pair bipartitions G into two edgedisjoint subgraphs G_{1} and G_{2}, then G has a grid drawing on a WxH grid such that both the width W and height H are smaller than the larger number of vertices in G_{1} and in G_{2}. In particular, we show that every seriesparallel graph G has a grid drawing on a (2n/3)x(2n/3) grid and such a drawing can be found in linear time.
Note: Refreshments will be served immediately following the lecture in ECS 668. All are welcome!
The mathematical research community is facing a great challenge to reevaluate the role of proof in light of the growing power of current computer systems, of modern mathematical computing packages, and of the growing capacity to datamine on the Internet. Add to that the enormous complexity of many modern capstone results such as the Poincar\'e conjecture, Fermat's last theorem, and the Classification of finite simple groups. As the need and prospects for inductive mathematics blossom, the requirement to ensure the role of proof is properly founded remains undiminished.
I shall look at the philosophical context and then offer five benchmarking examples of the opportunities and challenges we face, along with some interactive demonstrations.
Women still represent significantly less than half of math graduate students and faculty, despite the fact that they are majoring in math at higher rates. Women often don't choose math or get serious about mathematics until later in their education, when it is too late to adequately prepare for graduate school. The Center for Women in Mathematics provides a postbaccalaureate program for women who have graduated college but whose preparation is not adequate for graduate school. I will describe the program and the features that we feel are most helpful for encouraging success for women in mathematics graduate programs.
Euler diagrams are an accessible and effective visualisation of data involving simple settheoretic relationships. A common problem is the Euler diagram Generation Problem: given a set system automatically construct a diagram with the correct set of regions present that satisfies certain geometric or topological constraints. However, little work has been performed in the opposite direction, but we provide efficient algorithms to compute the set system of a given (reducible) Euler diagram.
One application of this theory is the development of a java library which enables the user to utilise Euler diagrams for the organisation of resources such as files or bookmarks. The interface enables the construction of overlapping ellipses to represent categories together with the drag and drop of resources in order to categorise them. Fast algorithms to interpret the wellformed diagrams and associate the correct set of tags to resources upon export have been developed. The generic approach is demonstrated via an integration with the bookmarking site del.icio.us.
We live in interesting times  as individuals, as members of various communities and organisations, and as inhabitants of planet Earth, we face many challenges, ranging from climate change to resource limitations, from market risks and uncertainties to complex diseases. To some extent, these challenges arise from the complexity of the systems we are dealing with and of the problems that arise from understanding, modelling and controlling these systems. As computing scientists and IT professionals, we have a lot to contribute: solving complex problems by means of computer systems, software and algorithms is an important part of what our field is about.
In this talk, I will focus on one particular type of complexity that has been of central interest in many areas within computing science and its applications, namely computational complexity, and in particular, NPhardness. I will investigate the question to which extent NPhard problems are as formidable as is often thought, and I will present an overview of research that fearlessly, and perhaps sometimes foolishly, attempts to deal with these problems in a rather pragmatic way. I will also argue that the area of empirical algorithmics holds the key to solving computationally challenging problems more effectively than many would think possible, while at the same time producing interesting scientific insights. The problems I will be covering include SAT and TSP, two classical and very prominent NPhard problems; in particular, I will present empirical scaling results for the bestperforming complete TSP solver currently known and discuss recent improvements in the state of the art in solving SATencoded software verification problems. I will also briefly discuss new results in the areas of timetabling, protein structure prediction and analysis of financial market data.
The domino shuffling algorithm was first described by Elkies, Kuperberg, Larsen and Propp in 1992, as a way of understanding domino tilings of Aztec Diamonds. I will review the algorithm, and describe two new applications of it: domino shuffling can be used to count "pyramid partitions", and also as a type of transfer matrix for sweeping out a solid partition.
The Melbourne University network design team is a group of mathematicians and engineers. We have been studying shortest networks for more than twenty years and have developed new algorithms and software to aid with the design of the access network for underground mines. Shortest planar networks are often called Steiner trees. In 3dimensions, there are important gradient and curvature constraints for navigability. Moreover barriers are required to avoid faults, old workings and the ore zone itself. Finally the objective function to be optimised is a combination of development and haulage costs, so the result is a weighted network. I will survey some of the work we have been doing recently with other researchers specialising in the design of mineable units (stopes) and scheduling, over the lifetime of the mine. The aim is to integrate different aspects of design, so that many designs can be generated to give a clearer picture of the value of a mine, required because of the uncertainty of costs, commodity prices and the ore body.
In this talk I will describe some recent results concerning the connection between the bubblesort sorting algorithm and certain integer sequences used to analyze various juggling patterns. The analysis leads to new results on the joint distribution of the descent and maximum drop statistics of a permutation, as well as a new class of identities for the classical Eulerian numbers.
We introduce two models of cooperative teaching and learning, showing how a learning algorithm can benefit from knowing that the data is chosen by a teacher. These new models can drastically reduce the sample size required for teaching. For instance, monomials can be taught with only two labeled data points, independent of the number of variables, whereas in standard teaching models the required number of labeled data points is exponential in the number of variables.
This theory of cooperative learning opens new ways of (a) showing inherent connections between teaching and active learning and (b) tackling a longstanding open question on sample compression.
This is joint work with Steffen Lange, Robert Holte, and Martin Zinkevich.
A ddimensional Keller graph has vertices which are numbered with each of the 4^d possible ddigit numbers which have each digit equal to 0, 1, 2, or 3. Two vertices are adjacent if their labels differ in at least two positions, and in at least one position the difference in the labels is two modulo four. Keller graphs are in the benchmark set of clique problems from the DIMACS clique challenge, and they appear to be especially difficult for clique algorithms. The dimension seven case was the last remaining graph for which the maximum clique order was not known. To resolve the last case for a conjecture of Keller, it is only necessary to determine if the maximum clique order is 128 or less than 128. It has been claimed in order to resolve this last case it might take a ``high speed computer the size of a major galaxy''. This talk describes the computation we used to determine that the maximum clique order is 124.
This is joint work with Jennifer Debroni, John Eblen, Mike Langston, Peter Shor, and Dinesh Weerapurage.
A tatami tiling is an arrangement of 1 by 2 tiles  or dimers  in a rectangle with m rows and n columns, subject to the constraint that no four corners meet at a point. In this talk, we will expand upon Dean Hickerson's beautiful combinatorial decomposition of the set of tatami tilings and use it to show ordinary generating functions of tatami tilings that fit in a rectangle with m rows and n columns, for fixed m and n = m. This allows us to verify a slightly modified version of a conjecture that Don Knuth made in Fascicle 1B of The Art of Computer Programming Volume IV. We will also present recent research into allowing a fixed number of 1 by 1 tiles  or monomers  to be present in the tiling.
For any function f(x, y), its communication complexity is the minimum number of bits needed to be exchanged between two parties holding integers x and y respectively. Invented thirty years ago, communication complexity has been a central research area in theoretical computer science with rich applications to algorithmic problems in data structure, circuit complexity, and cryptography. In this talk, we give an overview of communication complexity, highlighting notable recent results and the diverse mathematical techniques needed to obtain these results.
Valerie King is hosting this CAG and she will play a DVD of this talk.