Decoding from Pooled Data: Sharp Information-Theoretic Bounds
From MaRDI portal
Publication:5025779
DOI10.1137/18M1183339zbMath1499.62045arXiv1611.09981OpenAlexW3098823937MaRDI QIDQ5025779
Lenka Zdeborová, Florent Krzakala, Aaditya Ramdas, Michael I. Jordan, Ahmed El Alaoui
Publication date: 3 February 2022
Published in: SIAM Journal on Mathematics of Data Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1611.09981
compressed sensingcategorical datarandom constraint satisfactionsatisfiability thresholdplanted models
Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Statistical aspects of information-theoretic topics (62B10)
Related Items
Optimal group testing, The committee machine: computational to statistical gaps in learning a two-layers neural network
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the chromatic number of random regular graphs
- On two random search problems
- Belief propagation on replica symmetric random factor graph models
- Universality in polytope phase transitions and message passing algorithms
- Exact matrix completion via convex optimization
- Analyzing Walksat on Random Formulas
- Proof of the Satisfiability Conjecture for Large k
- Quiet Planting in the Locked Constraint Satisfaction Problems
- Tight Bounds on the Threshold for Permuted k-Colorability
- Decoding by Linear Programming
- A Spectral Approach to Analysing Belief Propagation for 3-Colouring
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- A Better Algorithm for Random k-SAT
- A Combinatorial Proof of the All Minors Matrix Tree Theorem
- Algebraic Potential Theory on Graphs
- Phase Transitions in Group Testing
- Decoding From Pooled Data: Phase Transitions of Message Passing
- A statistical-mechanics approach to large-system analysis of CDMA multiuser detectors
- Walksat Stalls Well Below Satisfiability
- Group Testing With Random Pools: Optimal Two-Stage Algorithms
- Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
- Information-Theoretically Optimal Compressed Sensing via Spatial Coupling and Approximate Message Passing
- Gibbs states and the set of solutions of random constraint satisfaction problems
- For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution
- Stable signal recovery from incomplete and inaccurate measurements
- Convex Analysis
- Information Theory
- Compressed sensing
- The two possible values of the chromatic number of a random graph
- Satisfiability threshold for random regular \textsc{nae-sat}
- The condensation phase transition in random graph coloring
