Tight Information Complexity of the Coin Problem in the Broadcast Model

arXiv:2608.02776 · cs.IT, cs.CC, math.ST, stat.ML · Submitted 2026-08-03 · Read on arXiv

Hadi Kazemi, Varun Jog

cs.IT, cs.CC, math.ST, stat.ML

Submitted: 2026-08-03

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Core — 10× in this paper · explained in 2 episodes
• Sample Complexity — 10× in this paper · explained in 20 episodes
• Communication Complexity — 9× in this paper · explained in 3 episodes
• Mutual Information — 7× in this paper · explained in 2 episodes
• Annual Symposium on Foundations of Computer Science — 3× in this paper
• Differential Privacy — 3× in this paper · explained in 5 episodes
• Combinatorial Optimization — 2× in this paper · explained in 2 episodes
• BQP — 1× in this paper · explained in 2 episodes
• Composition — 1× in this paper · explained in 2 episodes
• Differentially Private — 1× in this paper · explained in 3 episodes
• Editor — 1× in this paper · explained in 2 episodes
• Kullback–Leibler Divergence — 1× in this paper · explained in 2 episodes
• Robustness — 1× in this paper · explained in 6 episodes

Sources

• A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
• Large Deviation Methods for Approximate Probabilistic Inference

Related papers

• Task-Sufficient Contraction: Source Selection for Machine Information Interfaces
• Language Modeling is Monotone Compression
• 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