Parameterized Algorithms in Static Analysis

PhD Qualifying Examination


Title: "Parameterized Algorithms in Static Analysis"

by

Miss Giovanna KOBUS CONRADO


Abstract:

Parameterized complexity analyzes problems and instances along multiple 
parameters on the input or output, allowing for more efficient solutions when 
an instance has a smaller inherent difficulty. Some standard and well-studied 
parameters that model that difficulty in sparse graphs are pathwidth, treewidth 
and treedepth, which intuitively model the degree to which a given graph 
resembles a path, tree, or star, respectively.

A control-flow graph of a program is a graph representation of all its 
execution paths. Many static analysis and compiler optimization tasks are 
reduced to graph problems over control-flow graphs, but it is often the case 
that such problems has no efficient general solution. Therefore, ample research 
is focused on formalizing the structure of control-flow graphs, and then 
exploiting it to design faster algorithms for them.

In this work, I will describe graph sparsity parameters, how they relate to 
control-flow graphs, and how parameterization allows for more efficient 
algorithms in static analysis and compiler optimization.


Date:                   Friday, 28 April 2023

Time:                   2:00pm - 4:00pm

Venue:                  Room 5562
                         Lifts 27/28

Committee Members:      Dr. Amir Goharshady (Supervisor)
                         Dr. Sunil Arya (Chairperson)
 			Prof. Pedro Sander
 			Prof. Ke Yi


**** ALL are Welcome ****