COMBINATORIAL ALGORITHMS GROUP Schedule of Talks: Fall 2009

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 G₁ and G₂, 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₁ and in G₂. 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:

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.

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.

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 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, 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.

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

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

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

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.

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.