**Dynamic Part**

- Part of the focus is that as data changes, some computation on that data changes slowly over time, he discusses using a dynamic approach which does not recompute from scratch
- Can make an intractable problem tractable, example in dynamic points forming convex hulls goes from years to seconds

- Says dynamic algorithms designed for particular problems generally lags 10 years after static
- Domains that allow dynamic algorithms are stable, which means that similar inputs yield similar computations (in terms of actual execution)
- Idea is to represent execution as data structures that change over time
- Idea is based on combination of computational models of Turing and Church, a tree that records all the processing performed

- Idea is that it can be figured out what change in input causes changes in what parts of the execution tree, and only the modified part needs to be recomputed
- Running time is proportional to the stability of the problem, how much execution is shared
- Get two orders of magnitude saving in some cases
- Run [specially annotated, and specially restructured] code through a special compiler that produces a self-adjusting executable
- Because the computation is so fast (orders of magnitude), it has allowed for the solving of some open problems:
- live computation of convex hulls in higher dimensions on dynamic data
- Dynamic meshing: triangulate a dynamically changing 3d mesh s.t. no triangle has small angles (because small angles cause floating pt instability). Here the result is close to optimal (not manipluation of a shape, but deletion and random rea-dding of pts)
- Probabilistic inference

- Most of these results just leverage an existing result, figuring out that its stable, and then making it dynamic

**Parallelism Part**

- Basic point is that the overhead involved in parallelizing code is actually significant, finding the tradeoff where parallelization actually pays off is called the Granularity-Control Problem
- Have some methods that try to resolve the issue, speedups are significant, but not linear in number of additional cores

**Dynamic Parallel**

- Dynamic and parallel issues are “duals” of the same problem
- Can get the benefit of both by programming for just one
- Looking at doing Map-Reduce by this method, needed to make it stable with a small change, then implemented it in Hadoop
- Results for Hadoop just makes it faster, no end used changes needed.