Fast zeta transforms
The zeta transform and its inverse, Möbius transform, play a central role in the combinatorics of partially ordered sets; indeed, many combinatorial identities are derived via the method of Möbius inversion. The complexity of computing these transforms has been a topic of some recent works in algorithm theory; for a few partially ordered sets, such as the subset lattice, fast algorithms are known. The topic of the master's thesis is to review the basic theory underlying these discoveries, focusing on an important class of partial orders, namely finite distributive lattices. For this class, two algorithms [1, 2] have been derived somewhat independently, and it is currently unclear which one enables faster implementation or whether the two are essentially the same.
See the following articles and the references therein.
- Fast zeta transforms for lattices with few irreducibles. Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen. 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), pp. 1436-1444, SIAM, 2012
- Bayesian structure discovery in Bayesian networks with less space. Pekka Parviainen and Mikko Koivisto. 13th Internat. Conf. on Artificial Intelligence and Statistics (AISTATS 2010), Volume 9 of JMLR: W&CP 9, pp. 589-596, 2010