Low-Density Parity-Check Codes And Spatial Coupling For Quantitative Group Testing
summary
Replaces BCH constraint nodes with single parity-check codes inside a sparse graph GT scheme, adds spatial coupling, and runs density evolution plus finite-length simulations to show concrete gains: LDPC-based construction needs notably fewer tests than the prior generalized LDPC/BCH design, coupling memory steadily improves recovery, and simulated miss‑detection curves match the predicted density evolution thresholds. Includes a proof of threshold saturation for the coupled recursion.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 0:47What is group testing
- 3:00Codes on graphs and LDPC
- 5:52Sparse graph codes prior work
- 7:21Quantitative group testing motivation
- 10:17Performance comparison
- 12:04Decoder simplification
- 13:51Density evolution analysis
- 16:18Threshold analysis fixed rate
- 17:44Spatial coupling benefits
- 19:14Threshold saturation universality
- 21:05Proof of threshold saturation
- 23:59Potential function limits
- 25:26Open questions capacity
- 26:11Summary and future directions
- 26:57Q&A
related talks
11mExploiting Combined Locality for Wide-Stripe Erasure Coding in Distributed Storage
18mAutomated distribution of quantum circuits via hypergraph partitioning
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
01h 02mConditional Hardness for Massively Parallel Computing (MPC) Via Distributed Lower Bounds
31mMulti-version Coding and Shared Memory Emulation
39mBroadcasting on Directed Acyclic Graphs
10mQuery, Communication and Discrepancy
16mDispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks