Non-Adaptive Learning of Sparse Erd s--R'enyi Graphs via Affine Splitting

arXiv:2609.33704 · cs.IT, cs.LG, math.IT, math.PR · Submitted 2026-09-27 · Read on arXiv

cs.IT, cs.LG, math.IT, math.PR

Submitted: 2026-09-27

Updated: 2026-09-27

Terminology

• Hypergraph — 9× in this paper · explained in 2 episodes
• Sparsity — 7× in this paper · explained in 4 episodes
• Query Complexity — 3× in this paper · explained in 2 episodes
• Combinatorial Optimization — 1× in this paper · explained in 2 episodes
• In IEEE International Symposium on Information Theory — 1× in this paper

Sources

• A Fast Hierarchical Splitting Approach for Non-Adaptive Learning of Random Hypergraphs
• Quickly-Decodable Group Testing with Fewer Tests: Price-Scarlett and Cheraghchi-Nakos's Nonadaptive Splitting with Explicit Scalars

Related papers

• Clipped Affine Policy: Low-Complexity Near-Optimal Online Power Control for Energy Harvesting Communications over Fading Channels
• Discrepancy for Random Linear Codes
• A New Approach to Code Smoothing Bounds
• Contextual Memory-Enhanced Source Coding for Low-SNR Communications
• Symmetry-Enforced Quadratic Approximate-Degradability Bounds for Noisy Landau-Streater Channels
• Anonymous Shamir's Secret Sharing via Reed-Solomon Codes Against Permutations, Insertions, and Deletions