Synthesizing Efficient Memoization Algorithms
summary
Automated synthesizer takes a MiniZinc-style declarative spec and produces a top-down memoization algorithm by extracting subproblems and synthesizing two smaller functions: local objective function and memoization partition function, plus their updaters. Synthesis mixes deductive and inductive techniques, minimizes the range of the MPF to control efficiency, and generates executable code; evaluated on 42 benchmarks and successfully synthesizes 39/42 problems, outperforming prior baselines with artifacts available.
AI-written summary · about
chapters (13)
- 0:00Memoization for combinatorial optimization
- 1:23Exhaustive search fails for COPs
- 2:05Dynamic programming efficient solution
- 3:33Challenges in memoization synthesis
- 4:58Defining subproblems from search trees
- 7:03Conditions for subproblem equivalence
- 8:28Local objective functions
- 9:09Memoization partition functions
- 10:15Template for efficient memoization
- 10:56Overcoming synthesis challenges
- 11:38Implementation and evaluation
- 12:00Results on real-world COPs
- 12:23Q&A
related talks
01h 05mFrom meta frameworks and transformations to distributed computing and more
22mCounterexample-Guided Inference of Modular Specifications
20mMISAAL: Synthesis-Based Automatic Generation of Efficient and Retargetable(…)
31mLetting users do the undecidable: lessons from program synthesis
25mRecursive Program Synthesis using Paramorphisms
20mAutomating Pruning in Top-Down Enumeration for Program Synthesis Problems with(…)
29mTowards Bottom-Up Enumeration in miniKanren via Pruning and Memoization
20mOptimal Program Synthesis via Abstract Interpretation