Synthesizing Efficient Memoization Algorithms

Explore an innovative approach to automatically generate correct and efficient memoization algorithms from declarative specifications in this 18-minute video presentation from OOPSLA2 2023. Discover how researchers from Peking University tackle the challenges of synthesizing complex memoization algorithms by introducing local objective functions and memoization partition functions. Learn about their novel synthesis algorithm that combines deductive and inductive methods to solve tasks too complex for existing synthesizers. Examine the evaluation of their approach using 42 real-world benchmarks from Leetcode and the National Olympiad in Informatics in Provinces-Junior, demonstrating successful synthesis for 39 out of 42 problems. Gain insights into program synthesis, memoization algorithms, and their practical applications in algorithmic programming contests.

[OOPSLA23] Synthesizing Efficient Memoization Algorithms