Noisy group testing via spatial coupling

DOI10.1017/S0963548324000336MaRDI QIDQ6880007zbMATH OpenFDO

Authors Amin Coja-Oghlan, Max Hahn-Klimroth, Lukas Hintze, Dominik Kaaser, Lena Krieg, Maurice Rolvien, Olga Scheftelowitsch

Publication date 29 December 2025

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1017/S0963548324000336

zbMATH Keywords

efficient algorithmsgroup testinginferencerandom graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Statistical aspects of information-theoretic topics (62B10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Combinatorics in computer science (68R05)

Cites work

• A Method for Detecting All Defective Members in a Population by Group Testing
• Approximating CVP to within almost-polynomial factors is NP-hard
• Balls and bins: A study in negative dependence
• Decoding From Pooled Data: Phase Transitions of Message Passing
• Decoding from pooled data: sharp information-theoretic bounds
• Group testing: an information theory perspective
• Improved Bounds for Noisy Group Testing With Constant Tests per Item
• Individual Testing Is Optimal for Nonadaptive Group Testing in the Linear Regime
• Information, Physics, and Computation
• Information-Theoretic and Algorithmic Thresholds for Group Testing
• Information-theoretic thresholds from the cavity method
• Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
• Noisy Adaptive Group Testing via Noisy Binary Search
• Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
• Optimal group testing
• Phase transitions in group testing
• Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation
• The Capacity of Bernoulli Nonadaptive Group Testing
• The collected works of Wassily Hoeffding. Ed. by N. I. Fisher and P. K. Sen
• Threshold Saturation for Spatially Coupled LDPC and LDGM Codes on BMS Channels

This page was built for publication: Noisy group testing via spatial coupling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6880007)