CAG Schedule of Talks: Fall 2009

Schedule of Talks: Fall 2009

If you would like to give a talk in our seminar series, please contact Wendy Myrvold ( To get e-mail notification of our seminars and other events, you can subscribe to the CAG e-mail list at

Schedule for Talks:

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 Sample-efficient 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 Fixed-Height 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

Upcoming Talks:

Small Grid Drawings of Planar Graphs with Balanced Bipartition
Takao Nishizeki, Graduate School of Information Sciences
Tohoku University, Japan
Monday Dec. 21, 2:00pm, ECS 660

In a grid drawing of a planar graph, every vertex is located at a grid point, and every edge is drawn as a straight-line segment without any edge-intersection. It has been known that every planar graph G of n vertices has a grid drawing on an (n-2)x(n-2) 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 edge-disjoint subgraphs G1 and G2, 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 G1 and in G2. In particular, we show that every series-parallel 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!

Previous talks:

Exploratory Experimentation and Computation
Jonathan Borwein, University of Newcastle, NSW
Tues. Sept. 15th, 3:30pm, Elliot 168

The mathematical research community is facing a great challenge to re-evaluate 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 data-mine 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 bench-marking examples of the opportunities and challenges we face, along with some interactive demonstrations.

The Center for Women in Mathematics at Smith College
Ruth Hass (Director of the Center), Smith College
Thurs. Sept. 17, 3:30pm, Cornett A 221

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 post-baccalaureate 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.

Efficient Region Computations and Visual Classification with Euler Diagrams
Andrew Fish
Senior Research Fellow, University of Brighton, UK
Friday Sept. 18, 2:00pm, MacLaurin D 101

Euler diagrams are an accessible and effective visualisation of data involving simple set-theoretic 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

Taming the complexity monster
Holger H. Hoos,
Dept. of Computer Science, UBC
Tuesday Sept. 22, 10:30am, ECS 660

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, NP-hardness. I will investigate the question to which extent NP-hard 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 NP-hard problems; in particular, I will present empirical scaling results for the best-performing complete TSP solver currently known and discuss recent improvements in the state of the art in solving SAT-encoded software verification problems. I will also briefly discuss new results in the areas of timetabling, protein structure prediction and analysis of financial market data.

Some new applications of the domino shuffling algorithm
Benjamin Young
Dept. of Mathematics and Statistics, McGill University
Friday Sept. 25, 2:30pm, ECS 660

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.

Optimising access in underground mine design.
Hyam Rubinstein, Dept. of Math. & Statistics, Univ. of Melbourne
Friday Sept 25th, 3:30pm, David Strong C108

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 3-dimensions, 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 life-time 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.

Bubblesort and Juggling Sequences
Ronald Graham
Univ. of California at San Diego
Thurs. Oct. 22, 3:30pm, HSD A240

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.

Sample-efficient learning from cooperative teachers
Sandra Zilles, University of Regina
Friday Nov. 6, 2:30pm, ECS 660

Most machine learning models assume either (a) that the data fed to a learning algorithm is sampled at random from some (unknown) distribution or (b) that a learning algorithm has to be successful even for the worst possible data presentation (no matter how unlikely it is). However, in many application scenarios, e.g., when a human interacts with a learning machine, in fact "helpful" data is selected and presented to the learning machine by a "teacher".

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 long-standing open question on sample compression.

This is joint work with Steffen Lange, Robert Holte, and Martin Zinkevich.

The following two talks are dry runs of talks for the 33rd Australasian Conference on Combinatorial Mathematics and Combinatorial Computing, University of Newcastle, December 7-11, 2009.

The End to the Keller Conjecture
Wendy Myrvold
Friday Nov. 27, 2:30pm, ECS 104

A d-dimensional Keller graph has vertices which are numbered with each of the 4^d possible d-digit 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.

Counting Fixed-Height Tatami Tilings
Jenni Woodcock
Friday Nov. 27, 2:30pm, ECS 104

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.

Communication Complexity and Its Applications
Andrew Chi-Chih Yao
Friday Dec. 4, 2:30pm, ECS 104

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.

CAG Schedule of Talks: Fall 2009 / maintained by Wendy Myrvold / / revised Dec. 18, 2009