A Taxonomy of Fixed Point Computation Problems for Algebraically-Defined Functions, and their Comput

on YouTube ↗01h 10m

" summary

Algorithms target least fixed points of max/min probabilistic polynomial systems (branching MDP Bellman equations). Strategy decomposes SCCs, removes variables with lfp 0 or 1 by spectral-radius tests on the Jacobian at the all-ones vector, then applies a generalized Newton iteration whose piecewise-linear step is solved by linear programming with careful rounding. Claim: after removing 0/1 coordinates, 4·(encoding size)+j Newton iterations yield j bits; overall gives a polynomial-time Turing-model algorithm, despite posSLP hardness for more general cases.

AI-written summary · about

" chapters (11)

1. 0:00Start
2. 18:20Multi-type Branching Processes (Kolmogorov 1940s)
3. 31:42What is Newton's worst case behavior for PPSs and MPSs?
4. 36:53High level picture of proof
5. 40:12Branching Markov Decision Processes
6. 44:30Newton iteration as a first-order (Taylor) approximation
7. 45:28Generalised Newton's method
8. 46:41Algorithm for max/minPPS
9. 47:54Branching Simple Stochastic Games
10. 48:21Conclusion
11. 49:55Open problems