Dana is NOT average
summary
Average-case LCAs for random inputs give concrete gains: k-spanner constructions on G(n,p) achieve size/stretch tradeoffs impossible in the worst case while cutting query complexity from known worst-case bounds (Ω(√n) lower, best prior ≈n^{2/3}) down to polylog time in many regimes. A simple local generator returns an Erdos–Rényi graph together with a maximal independent set in sublinear time. Practical tricks include randomized sparsification to 2n edges (Or Zamir idea) and a four-round distributed-to-local reduction that makes the constructions efficient and consistent.
AI-written summary · about