Raimund Seidel -Universität des Saarlandes

Top-down analysis of path compression and related problems

Abstract: The so-called inverse Ackermann function is an exceedingly slowly growing function that arises in bounds for a number of computational/ combinatorial problems. The proofs of those bounds are usually tedious, proceed in a bottom-up fashion, and provide little, if any, intuition in the nature of the bound.

In my lecture I will describe a top-down approach that is rather simple and leads naturally to such inverse Ackermann function bounds (without ever having to talk about the Ackermann function itself). The most striking example will be so-called path compression, which arises in algorithms for the union-find problem. This is one of the basic problems in algorithmics. It is distinguished by the fact that it is typically the only basic problem in intermediate level algorithms courses for which fast solutions are taught but not analyzed.

Colloquium - 16:00

Ares Ribó Mor -Freie Universität Berlin

Advances in counting polyominoes on the twisted cylinder

Abstract: A polyomino of size n is a connected set of n adjacent squares on the plane. Let A(n) be the number of polyominoes of size n, where two polyominoes are distinct if they have different shapes or different orientations. To this day no analytic formula for A(n) is known, and the only known methods for computing A(n) are based on explicitly or implicitly enumerating all polyominoes. A(n) has only been computed for n ≤ 56. Klarner showed that the limit λ = lim _{n → ∞} A(n+1)/A(n), the asymptotic growing rate of A(n), exists. This limit λ is known as Klarner's constant, and not even a single significant digit of it is known for sure. The best known lower and upper bounds were 3.903184 and 4.649551. The constant λ is estimated to be around 4.06.

We significately improve the lower bound on Klarner's constant to 3.980137 by counting polyominoes on a different grid structure, the twisted cylinder. We are based on the Jensen transfer-matrix algorithm. We have implemented a program in C which iterates the transfer equations, obtaining a lower bound for the growing rate of the number of polyominoes on the twisted cylinder, which is also a lower bound for the number of polyominoes in the plane. Our program encodes and ranks the states by Motzkin paths, which is much more space-efficient than the previous encodings.

Joint work with Gill Barequet (CS, Technion), Micha Moffie (CS, Northeastern Univ.), and Günter Rote (FU Berlin).