Linear forms over semirings: algorithmic applications and complexity results

Title

Linear forms over semirings: algorithmic applications and complexity results

 

Abstract

Based on work included in my upcoming PhD thesis, I will discuss various topics related to the evaluation of linear transformations (or equivalently, matrix-vector multiplications) over different types of rings and semirings. The work is motivated by applications in counting and optimisation algorithms for hard problems. Specifically, we consider a setting where we have a fixed linear map, and ask what happens when we change the semiring we operate over; different choices of semiring both allow different kinds of applications and change the complexity of evaluation. In this talk, I will

   1) cover the motivations and background that lead to this line of research,

   2) present a faster-than-trivial algorithm for counting maximum weight k-paths in a graph, based on a fast semiring linear transform, and

   3) discuss complexity results giving some insight into what semiring properties are useful for fast algorithms and when.

I will focus on the high-level picture and avoid most of the technical details; despite the somewhat abstract setting, the talk requires no prior knowledge on the topic.

 

About the Presenter

Janne H. Korhonen is a PhD student at the New Paradigms in Computing group at HIIT / University of Helsinki. He has master's degree in mathematics, and will most likely defend his PhD thesis "Graph and Hypergraph Decompositions for Exact Algorithms" in January next year.