Algorithms and Hardness for Multidimensional Range Updates and Queries

on YouTube ↗39m

" summary

Shows that multidimensional range updates flatten via a kd-style reduction to 1D giving ~Õ(√p) per operation and proves matching conditional lower bounds (no O(n^{0.5−ε})) under the OMv conjecture; reduces 3SUM to show near-quadratic hardness for richer update sets. Introduces a dynamic trellis decomposition and static-to-dynamic reductions that convert set-update+sum to inversion/triangle counting, yielding truly subquadratic algorithms (≈n^{1.47}) and extensions giving ≈n^{1.75} for more operations.

AI-written summary · about

" chapters (10)

1. 0:00Intro
2. 0:20Orthogonal range problems
3. 2:21Range updates and queries
4. 7:56Prior Work
5. 18:113SUM Hardness: + query, {+, max} update
6. 22:28Partitioning into Trellises
7. 25:47Separating dimensions For max query + update
8. 29:31Reducing to static trellised instances
9. 31:57+ query, set update: Inversion Counting
10. 33:57Equivalences and reductions