Peeling Algorithms
Talkat Parallel and Distributed Algorithms for Inference and Optimization (Simons Institute, Oct. 21–24, 2013) · 2013-10-21..10-24·
summary
Survey of peeling algorithms links Karp‑Sipser and pure literal ideas to practical tools like invertible Bloom lookup tables that store key/value XOR sums and list entries by peeling cells of count one. Thresholds determine success: 3‑hash IBLTs need about 1.2n cells to recover n items (empty two‑core), and parallel peeling finishes in order log log n rounds below the threshold but needs Ω(log n) above it. Implementation uses subtables to avoid locking, and double hashing empirically matches fully random hashes.
AI-written summary · about
chapters (25)
- 0:00Intro
- 0:54A Matching Peeling Argument
- 3:34A SAT Peeling Argument
- 4:59Random Graph Interpretation
- 5:38History
- 6:15A Peeling Paradigm
- 8:22Not Just for Theory
- 9:46Low Density Parity Check Codes
- 10:27Decoding by Peeling
- 11:19Decoding Step
- 11:45Decoding Results
- 14:06Peeling and Tabulation Hashing
- 15:06End Survey
- 15:32Stragglers' Problem
- 16:54Set Reconciliation Problem
- 17:56Functionality
- 18:43Possible Scenarios
- 21:00Get Performance
- 21:43Listing Example
- 22:49Listing Performance
- 25:46New Stuff: Parallel Peeling
- 28:01Parallel Peeling : Argument
- 29:33Parallel Peeling : Implementation
- 31:32New Stuff: Double Hashing
- 32:57Conclusion
related talks
58mExponential-Time Algorithms
28mTowards Practical Polar Codes With Low Scaling Exponent
57mCoding for Interactive Communication
29mOn disperser/lifting properties of the Index and Inner-Product functions
31mInterleaved Codes For Cryptography
59mWhat about Binary Search Trees?
26mCan we do better than git s Merkle DAG?
15mLESS is More for I/O-Efficient Repairs in Erasure-Coded Storage