Helsinki Algorithms Seminar: Fast zeta transform in semimodular lattices -- the art of taking many related sums

TIME: Thursday 21 January, 16.15–17.00

PLACE: Room B119, Exactum, Kumpula

SPEAKER: Jukka Kohonen

TITLE: Fast zeta transform in semimodular lattices -- the art of taking many related sums

ABSTRACT:

Many algebraic and combinatorial problems involve partially ordered sets or "posets", for example, the collection of subsets of a given set. A lattice is a kind of a poset. The structure can be visualized as a directed acyclic graph (DAG). Each element of a lattice may have an associated number or "value", and one wishes to take sums of these values over many different large collections of elements efficiently. This simultaneous computation of the different sums is called the zeta transform. Counting problems in combinatorics are often of this type.

I will describe some recent advances in the algorithmics of this problem. For certain kinds of lattice and posets we now know zeta transform algorithms that are as fast as theoretically possible, namely, exactly e elementary additions if the lattice or poset has e edges. I will also discuss some open problems, such as: Are there any lattices where the zeta transform is very difficult? There are lattices where 2e additions are needed, but is there an upper bound?

More information about Helsinki Algorithms Seminar.