Parameterized Algorithms for Verification and Compiler Optimization

PhD Thesis Proposal Defence


Title: "Parameterized Algorithms for Verification and Compiler Optimization"

by

Mr. Kerim KOCHEKOV


Abstract:

Parameterized complexity offers a principled way to tackle computationally 
hard problems by exploiting structural properties of inputs. This thesis 
applies this framework to program analysis and compiler optimization, 
focusing on graph-based representations of programs such as control-flow and 
call graphs.

On the program analysis side, I leverage structural parameters such as 
treewidth and treedepth to design fixed-parameter tractable algorithms within 
the Algebraic Program Analysis (APA) framework. I present an efficient 
on-demand APA approach that answers multiple source–target queries by 
combining tree decompositions with centroid decompositions, avoiding the 
treewidth blowup present in prior work and significantly improving runtime 
performance.

On the compiler optimization side, I study function merging for binary size 
reduction. I introduce a generalized formulation that allows 
semantic-preserving reordering of branches, enabling more flexible matching 
between functions. While this generalization makes the problem NP-hard, I 
analyze it using parameterized complexity and identify key parameters, 
including branching factor and nesting depth, that govern tractability.

Overall, this thesis demonstrates how exploiting structural parameters 
enables efficient algorithms for both program analysis and compiler 
optimization, bridging theory and practical performance improvements.


Date:                   Wednesday, 27 May 2026

Time:                   1:00pm - 2:00pm

Venue:                  Room 2129C
                        Lift 19

Committee Members:      Dr. Jiasi Shen (Supervisor)
                        Dr. Amir Goharshady (Co-supervisor, Oxford)
                        Dr. Mingxun Zhou (Chairperson)
                        Dr. Zihan Zhang