Linear forms over semirings: algorithmic applications and complexity results

Lecturer : 
Janne Korhonen
Event type: 
HIIT seminar
Event time: 
2013-11-01 10:15 to 11:00
Exactum, B119
Linear forms over semirings: algorithmic applications and complexity results
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.

Last updated on 24 Oct 2013 by Brandon Malone - Page created on 24 Oct 2013 by Brandon Malone