Szepesvari lists 5 TCS results that actually got faster in practice, from LSH to max-flow
CsabaSzepesvari · x · 2026-10-13
Responding to Yoav Goldberg's question about which celebrated TCS results of the past decade deliver real speedups on practical inputs, Csaba Szepesvari compiled (with Gemini's help) a list: cross-polytope LSH for approximate nearest neighbors (2015), approximate Gaussian elimination for Laplacians (2016), wavefront alignment (2020), ribbon-filters for approximate membership (2021), and the almost-linear time max-flow algorithm (2022).
More from Research
- World model research: more data won't suffice—squeeze more from it; even intuitive physics is still out of reach — mangahomanga · 2026-10-13
- Indie dev builds own serving library to train SVG model, finds evolution loses to SGD — cephaloform · 2026-10-13
- Harvard & NTT Research: cooperating AI agent populations hit an Allee-effect takeoff threshold — Hidenori8Tanaka · 2026-10-13
- RT-Super trains tumor segmentation from radiology reports, lifting Dice from 16 to 30 without masks — maier_ak · 2026-10-13
- Princeton's QUEEN: a 4B model that plays grandmaster-level chess and explains its moves in plain language — jiqizhixin · 2026-10-13
- Oxford shows neural nets can be encrypted inside model weights, surviving 500 SFT steps — zainhas · 2026-10-13