Erasure-Resilient Sublinear-Time Graph Algorithms
summary
Defines queries on an alpha-erased graph (adjacency lists with adversarial missing entries) and measures performance over all completions; degree and neighbor queries return erased markers. Main claims: there is a phase transition at alpha = epsilon — if alpha >= epsilon testers need linear queries in n (and in sparse graphs linear in edges), while if alpha < epsilon one gets size-independent testers; an improved connectedness tester beats prior bounds when d̄ < sqrt(1/epsilon). For average-degree estimation: sqrt(n) queries yield a 1+epsilon+2alpha approximation, and a linear lower bound rules out (1+gamma)-approximation for any gamma < alpha.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:31Sublinear-time algorithms for graphs . Typical assumption: Query or sample access to graphs
- 1:24Partially erased graphs: Representation
- 2:25Erasure-resilient graph algorithms
- 5:38Erasure-resilient testing connectedness of graphs
- 9:25Estimating the average degree . In the special case of no erasures, studied by
- 10:53Estimating the average degree: Our results Estimating average degree of a-erased graphs
- 12:16Erasure-resilient connectedness tester for small a
- 13:57Detecting graphs that are far from connected
- 16:19Prior best connectedness tester
- 18:12Our connectedness tester
- 21:50Open problems
related talks
33mLinear and sublinear algorithms for graphlet sampling
35mDistributed Models for Private Analysis of Graph Data
01h 02mCounting Subgraphs in Sublinear Time
43mResizable Sketches
18mGraphAce: Secure Two-Party Graph Analysis Achieving Communication Efficiency
29mFactorized Graph Neural Networks (With Some Algebraic Cheating)
57mQuery Optimization and Evaluation 1: Output Size Bounds and Information Theory
44mEfficient Enumeration Algorithms via Circuits