The Ph.D. defense starts with a 25' lecture about

- Growth of polyominoes

(see below for the abstract), which is followed by a discussion and

a short presentation of the Ph.D. thesis with the title:

- Growth of bilinear maps

### Abstract of the first talk: Growth of polyominoes

A polyomino is an edge-connected set of cells in the square lattice. Although the

notion is simple and natural, many problems related to polyominoes are open,

namely computing efficiently the number of polyominoes A(n) with n cells and

estimating its exponential growth constant λ = lim_{{n→∞}} A(n)^^{(1/n)}, which is

known as Klarner's constant. The best algorithm for the former problem still

suffers the exponential time complexity, whose base can be decreased usually by

using more space. It follows that the natural way to bound λ from below by A(n)^^{(1/n)}

asks for a lot of computation. The best approach for a bound so far is by

considering twisted cylinders, a model that is similar to polyominoes

but a bit simpler to compute. This allows the lower bound to just exceed 4 by

Barequet, Rote, and Shalah in 2016, which is close to the believed value λ ≈ 4.06.

The known upper bounds are however not so good: the bound 4.65 has existed since

1973 by Klarner and Rivest, and only very recently got improved to 4.53 in 2022

by Barequet and Shalah, which actually asks for a good deal of computation.

Related aspects and new approaches will be also discussed.

### Time & Location

Dec 18, 2023 | 12:30 PM s.t. - 02:00 PM

Seminarraum 053

Institut für Informatik

Takustraße 9

Freie Universität Berlin