Parameterized Algorithms and Complexity for Function Merging with Branch Reordering
summary
Shows that allowing function merging with branch reordering makes the optimization NP-hard, then gives parameterized algorithms: a constructive FPT algorithm running in time 2^{O(bd)} n^2 for parameters branching factor and nesting depth (b1,b2,d1,d2), plus a second algorithm 2^{O(b d2)} n^7 that drops one depth parameter. Proofs use graph encodings of control flow, an on-the-fly alignment DP over reorderings, and a reduction to weighted pushdown reachability to get the faster bound.
AI-written summary · about
chapters (9)
- 0:00Function merging intro
- 1:05Selector parameter basics
- 2:11Sequence alignment approach
- 4:41Branch reordering for alignment
- 6:06Parameterized algorithms
- 7:29Branching factor and depth
- 9:57Algorithm technical details
- 13:52Summary and future work
- 14:14Q&A on branch elimination
related talks
25mRecursive Program Synthesis using Paramorphisms
15mScaling Optimization Over Uncertainty via Compilation
32mA Finite Alternation Result for Reversible Boolean Circuits
47mHardness Amplification and the Approximate Degree of Constant-Depth Circuits
17mSatisfiability Algorithms Based on Concentrated Shrinkage
15mSealing Pointer-Based Optimizations Behind Pure Functions
23mDeep Fusion for Efficient Nested Recursive Computations
37mA Tour of Program Optimization