Distributed Statistical Estimation of Matrix Products with Applications
summary
Estimates ℓp norms of C = A·B for binary and integer inputs with explicit communication and round counts: gives a two‑round protocol achieving 1+ε for ℓp (p≥0) using ≈ n/ε bits and a constant‑round algorithm for ℓ∞ that achieves 2+ε using ≈ n^{1.5}/ε bits (binary case; general integers need ≈ n^2/κ^2 for κ‑approx). Proves matching and nonmatching lower bounds (one‑way vs multi‑round separations), gives heavy‑hitters bounds, and leaves gaps between upper and lower bounds.
AI-written summary · about
chapters (13)
- 0:00Start
- 0:10The Distributed Computation Model
- 0:32Statistics of Matrix Products: p-Norms
- 2:09Application of set-intersection join
- 2:44Statistics of Matrix Products: Heavy Hitters
- 3:34Our Main Results - lp (p = [0,2])
- 6:03Our Main Results - Heavy Hitters
- 6:36Previous Results
- 11:06A lower bound (Van Gucht, Williams, Woodruff, Z. '15)
- 11:51A lower bound (cont.)
- 16:41The open problem
- 25:26A Lower Bound for fx (cont.)
- 26:56Concluding Remarks
related talks
27mHow to Compress Asymmetric Communication
27mSparsity and Privacy in Distributed Matrix Multiplication
28mCommunication Avoiding Algorithms for Linear Algebra and Beyond
01h 20mAn Introduction to Distributed, Massively Parallel, and Local Computation Algorithms
52mFine-Grained Complexity and Algorithm Design for Graph Reachability and Distance Problems
29mImplementing Randomized Matrix Algorithms in Parallel and Distributed Environments
47mMassively Parallel Evaluation of Relational Queries I
27mConsensus Division in an Arbitrary Ratio