Guiding Dynamic Programing via Structural Probability for Accelerating Programming by Example
summary
MaxFlash combines dynamic programming (PROSE-style witness functions and caching) with structural probability from Euphony, using a topdown prediction model to encode context and attaching lowerbounds via iteratively deepening search, branch-and-bound, and a heuristic upperbound. It enforces finding the most probable program per subproblem to enable reuse across example and lowerbound dimensions. Evaluated on 205 string and 39 matrix tasks, it reports significant speed-ups and lower memory than six baselines; Transformation.Text solves more benchmarks but MaxFlash is faster and more memory-efficient on common tasks.
AI-written summary · about
chapters (13)
- 0:00Intro
- 0:21Programming by Example
- 1:24Challenge: Scalability
- 2:12Background: Dynamic Programming
- 4:08Background: Structural Probability • Idea: Whether a program is probable can be predicted from its structure.
- 6:25Topdown Prediction Model (TPM)
- 8:39Example: Search Algorithms
- 11:39Challenge2: Ineffective Reuse Mechanism
- 12:37Casel: Subproblems Only Differ on Lowerbounds
- 13:48Case2: Subproblems Only Differ on Examples
- 14:42Evaluation Setup
- 15:27Result: Compare with Synthesizers
- 16:16Summary
related talks
37mDynamic programming at ease - with Grammars, Algebras, Products
21mFlashProfile - A Framework for Synthesizing Data Profiles
01h 10mModels and Programs: Better Together
20mStatic Posterior Inference of Bayesian Probabilistic Programming via Polynomial Solving
47mThe State of the Art for Probabilistic Programming
17mProgrammatic Strategy Synthesis: Resolving Nondeterminism in Probabilistic Progr...
31mProbabilistic Programming: The What, Why and How
14mMulti-Language Probabilistic Programming