LFCS seminar: Rasmus IbsenJensen: Faster algorithms for program analysis
What 


When 
Mar 14, 2016 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
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 treewidth 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 treewidth 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 meanpayoff 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 http://rasmus.ibsenjensen.com for the papers). No prior knowledge about the discussed topic is necessary to follow the talk.
Brief Bio: Rasmus IbsenJensen 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 treewidth graphs and theoretical evolutionary biology.