Linear forms over semirings: algorithmic applications and complexity results

Event type: 
HIIT seminar
Event time: 
01.11.2013 - 10:15 - 11:00
Lecturer : 
Janne Korhonen
Place: 
Exactum, B119
Description: 
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.
24.10.2013 - 09:25 Brandon Malone
24.10.2013 - 09:25 Brandon Malone