Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS seminar: Rasmus Ibsen-Jensen: Faster algorithms for program analysis

LFCS seminar: Rasmus Ibsen-Jensen: Faster algorithms for program analysis

— filed under:

  • LFCS Seminar
When Mar 14, 2016
from 04:00 PM to 05:00 PM
Where IF 4.31/4.33
Add event to calendar vCal

Faster algorithms for program analysis


The talk is about solving graph problems (focusing on graph problems that are often reduced to in program analysis) faster when the graphs are composed of control flow graphs of methods in programs. Using that control flow graphs of methods typically have constant tree-width we consider when the program (i) has a single method, (ii) has many methods or (iii) concurrent threads, each on a single method. In case (ii) and case (iii), we consider the algebraic path problem, which is a very general problem, with many interesting special cases, such as (1) reachability and shortest path (with positive and negative weights), (2) the IDE/IDFS frameworks of program analysis and (3) most probable path. Since the algebraic path problem has already been optimally solved for single methods/constant tree-width graphs, up to factors of log^* n, in case (i) we consider other weighted graph problems that has been reduced to in program analysis (but which are not special cases of the algebraic path problem), specifically finding the cycle with the least mean of weights (the minimum mean-payoff problem) and finding the minimum number c such that all prefix sums of the weights of runs are greater than -c (the minimum initial credit problem). In all cases, we give simple algorithms which are better than the state of the art in theory and practice. The talk is based on my POPL papers from the last two years and my CAV paper from last year (see e.g. my homepage at for the papers). No prior knowledge about the discussed topic is necessary to follow the talk.

Brief Bio: Rasmus Ibsen-Jensen is a Post Doc. at IST Austria since 2013. He has a MSc from Aarhus University 2011 and a Ph.d from Aarhus University 2013.  Most of his work is on algorithmic game theory (especially stochastic games), but also recently on algorithms for constant tree-width graphs and theoretical evolutionary biology.

Document Actions