M.Sc. Juha Harviainen defends his doctoral thesis "Advances in Sampling and Counting Bipartite Matchings and Directed Acyclic Graphs" on Friday the 27th of September 2024 at 13 o'clock in the University of Helsinki Physicum building, Auditorium E204 (Gustaf Hällströmin katu 2, 2nd floor). His opponent is Professor Mark Huber (Claremont McKenna College, USA) and custos Professor Mikko Koivisto (University of Helsinki). The defence will be held in English.
The thesis of Juha Harviainen is a part of research done in the Department of Computer Science and in the Sums of Products group at the University of Helsinki. His supervisor has been Professor Mikko Koivisto (University of Helsinki).
Advances in Sampling and Counting Bipartite Matchings and Directed Acyclic Graphs
When enumerating all objects of some set is computationally infeasible, sampling a subset of them provides a method for both analyzing their properties and approximating their total number or weight. Since sampling is inherently random, one often desires guarantees for the quality of the output, such as a promise that the samples are drawn exactly from a target distribution or that the relative error of an estimate is unlikely to be large.
In this thesis, we study sampling and weighted counting of bipartite matchings and directed acyclic graphs (DAGs). The total weight of perfect matchings of a bipartite graph equals the permanent of the corresponding adjacency matrix, a quantity whose exact computation is a notoriously hard problem. The first three papers of the thesis focus on approximating the permanent with Monte Carlo integration such that we obtain probabilistic guarantees for the accuracy of our estimate, with each paper resulting in at least an order-of-magnitude improvement over the previous state of the art. Combining the proposed methods provides even further speedups.
The remaining two papers relate to Bayesian networks, whose structure is a DAG. In particular, we are interested in the problems of sampling DAGs exactly from a given posterior distribution and computing posterior probabilities of structural features. We start by extending the study of these problems into a parameterized setting in which the sample space is constrained to simplify the computations. When the vertex cover number of the graphs is bounded, we observe both problems to become tractable. Finally, we develop a novel algorithm for sampling network structures exactly from the posterior in an unconstrained setting. This algorithm is asymptotically the fastest known, and we also verify its performance empirically.
Availability of the dissertation
An electronic version of the doctoral dissertation will be available in the University of Helsinki open repository Helda at http://urn.fi/URN:ISBN:978-952-84-0667-9.
Printed copies will be available on request from Juha Harviainen: juha.harviainen@helsinki.fi