6 papers
Parameterized Algorithms and Complexity for Function Merging with Branch Reordering
Amir K. Goharshady, Kerim Kochekov, Tian Shu +1
Binary size reduction is an increasingly important optimization objective for compilers. One emerging technique is function merging, where multiple similar functions are merged int…
Series-Parallel-Loop Decompositions of Control-flow Graphs
Xuran Cai, Amir Goharshady, S Hitarth +1
Control-flow graphs (CFGs) of structured programs are well known to exhibit strong sparsity properties. Traditionally, this sparsity has been modeled using graph parameters such as…
Efficient Algorithms for Partial Constraint Satisfaction Problems over Control-flow Graphs
Xuran Cai, Amir Goharshady
In this work, we focus on the Partial Constraint Satisfaction Problem (PCSP) over control-flow graphs (CFGs) of programs. PCSP serves as a generalization of the well-known Constrai…
Quantifier Elimination Meets Treewidth
Hao Wu, Jiyu Zhu, Amir Kafshdar Goharshady +3
In this paper, we address the complexity barrier inherent in Fourier-Motzkin elimination (FME) and cylindrical algebraic decomposition (CAD) when eliminating a block of (existentia…
Combinatorial Parameterized Algorithms for Chemical Descriptors based on Molecular Graph Sparsity
Giovanna K. Conrado, Amir K. Goharshady, Harshit J. Motwani +1
We present efficient combinatorial parameterized algorithms for several classical graph-based counting problems in computational chemistry, including (i) Kekule structures, (ii) th…
PolyQEnt: A Polynomial Quantified Entailment Solver
Krishnendu Chatterjee, Amir Kafshdar Goharshady, Ehsan Kafshdar Goharshady +4
Polynomial quantified entailments with existentially and universally quantified variables arise in many problems of verification and program analysis. We present PolyQEnt which is…