Lightning Talks by Simons Institute Fellows
summary
History-independence claims give canonical memory layouts for dictionaries that match usual performance via random priorities and extend to external memory B‑trees and concurrent shared‑memory models, with applications to worst‑case oblivious algorithms and a breakthrough on list‑labeling. Elliptic PDE learning proves intrinsic data efficiency, recovering Green’s functions with only log^5(1/ε) operator products via hierarchical matrix structure and an adjoint-free preconditioning method (Laplace–Beltrami) that yields algebraic versus exponential rates. Predictors for Byzantine faults cut rounds proportionally to predictor error (still t < n/3). Reconfigurable optical circuit switches support periodic schedules trading latency for congestion; Google and Microsoft prototypes exist. Algebraic complexity shows a log n parallel algorithm for polynomial GCD (improving log^2), while the Euclidean remainder sequence’s parallel complexity remains open.
AI-written summary · about
chapters (7)
- 0:00Welcome
- 1:12History-independent data structures
- 12:12Matrix recovery and operator learning
- 27:03Byzantine agreement with predictions
- 43:39Routing on reconfigurable networks
- 58:26Euclidean algorithm complexity
- 1:09:30Q&A
related talks
30mA Tale of Shared Memory Concurrency in Programming Languages
01h 13mTalk by I-Ting Angelina Lee (Washington University in St. Louis)
01h 11mProgramming language memory models: Problems, solutions, and directions
06mLightning Talk: A Compiler Optimization and the 2-Adic Numbers
07mLightning Talk Slot #2: An SSA-based Register Allocator for GHC
19mPanel: Compilation Frameworks
11mLightning Talks
15mSealing Pointer-Based Optimizations Behind Pure Functions