Tight Information Complexity of the Coin Problem in the Broadcast Model

• URL: http://arxiv.org/abs/2608.02776v1
• Date: Mon, 03 Aug 2026 18:21:26 GMT
• Title: Tight Information Complexity of the Coin Problem in the Broadcast Model
• Abstract summary: We study distributed testing of $mathrmBer()$ versus $mathrmBer()$ in the broadcast, or shared-blackboard, model.<n>For protocols with constant advantage, we characterise up to universal constant factors the information complexity under either hypothesis for every pair $$.
• Score: 0.21485350418225238
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study distributed testing of $\mathrm{Ber}(α)$ versus $\mathrm{Ber}(β)$ in the broadcast, or shared-blackboard, model. For protocols with constant advantage, we characterise up to universal constant factors the information complexity under either hypothesis for every pair $β<α$. The characterisation shows that the two information costs can be quite different and identifies three parameter regimes, with optimal protocols based respectively on clean samples, a noisy binary symmetric channel, and an asymmetric $Z$-channel. The lower bounds rely on a novel mixed Hellinger--Jensen--Shannon inequality that may be of independent interest. We also characterise the constant-advantage information complexity of testing arbitrary discrete distributions via an optimisation problem over channels, and show that binary-output channels suffice. We obtain bounds for bounded likelihood-ratio distributions, and give general upper bounds in terms of $χ^2$ divergence. As applications, we recover the broadcast-model set-disjointness lower bound, and derive stronger lower bounds in the multi-pass streaming setting for some problems considered in prior work.

Related papers

• Distributed Monogamy of Entanglement limits Quantum Channel Simulation [2.277447144331876]
  We introduce fractional extendibility, which gives a finer characterization of the quantum correlation that is leaked to the environment.<n>We also establish the distributed monogamy of entanglement: for any state on $AB_Bdots B_n$, the maximum average probability of extracting an EPR pair from a random subset of $k leq n/2$ systems among the $B_i$'s is the fraction $k/n$.
  arXiv  Detail & Related papers  (2026-07-09T15:26:41Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• The Sample Complexity of Uniform Approximation for Multi-Dimensional CDFs and Fixed-Price Mechanisms [25.375074054942434]
  We study the sample complexity of learning a uniform approximation of an $n$-dimensional cumulative distribution function.<n>We provide tight sample complexity bounds and novel regret guarantees for learning fixed-price mechanisms in small markets.
  arXiv  Detail & Related papers  (2026-02-11T13:55:37Z)
• Rate optimal learning of equilibria from data [63.14746189846806]
  We close theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity.<n>For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, MAIL-WARM.<n>We provide numerical results that support our theory and illustrate, in environments such as grid worlds, where Behavior Cloning fails to learn.
  arXiv  Detail & Related papers  (2025-10-10T12:28:35Z)
• Semidefinite programming relaxations and debiasing for MAXCUT-based clustering [1.9761774213809036]
  We consider the problem of partitioning a small data sample of size $n$ drawn from a mixture of 2 sub-gaussian distributions in $mathbbRp$.<n>We use semidefinite programming relaxations of an integer quadratic program that is formulated as finding the maximum cut on a graph.
  arXiv  Detail & Related papers  (2024-01-16T03:14:24Z)
• Simple Binary Hypothesis Testing under Local Differential Privacy and Communication Constraints [8.261182037130407]
  We study simple binary hypothesis testing under both local differential privacy (LDP) and communication constraints. We qualify our results as either minimax optimal or instance optimal.
  arXiv  Detail & Related papers  (2023-01-09T18:36:49Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  We prove a Lipschitzness lower bound $Omega(sqrtn/p)$ of robustness of interpolating neural network parameters on arbitrary distributions. We then show the potential benefit of overparametrization for smooth data when $n=mathrmpoly(d)$. We disprove the potential existence of an $O(1)$-Lipschitz robust interpolating function when $n=exp(omega(d))$.
  arXiv  Detail & Related papers  (2022-02-23T16:10:23Z)
• Acceleration in Distributed Optimization Under Similarity [72.54787082152278]
  We study distributed (strongly convex) optimization problems over a network of agents, with no centralized nodes. An $varepsilon$-solution is achieved in $tildemathcalrhoObig(sqrtfracbeta/mu (1-)log1/varepsilonbig)$ number of communications steps. This rate matches (up to poly-log factors) for the first time lower complexity communication bounds of distributed gossip-algorithms applied to the class of problems of interest.
  arXiv  Detail & Related papers  (2021-10-24T04:03:00Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)
• Robustly Learning any Clusterable Mixture of Gaussians [55.41573600814391]
  We study the efficient learnability of high-dimensional Gaussian mixtures in the adversarial-robust setting. We provide an algorithm that learns the components of an $epsilon$-corrupted $k$-mixture within information theoretically near-optimal error proofs of $tildeO(epsilon)$. Our main technical contribution is a new robust identifiability proof clusters from a Gaussian mixture, which can be captured by the constant-degree Sum of Squares proof system.
  arXiv  Detail & Related papers  (2020-05-13T16:44:12Z)
• From Information Theory Puzzles in Deletion Channels to Deniability in Quantum Cryptography [0.0]
  We first conjecture on the basis of experimental data that the entropy of the posterior is minimized by the constant strings. We then establish a connection between covert communication and deniability to propose DC-QKE. We present an efficient coercion-resistant and quantum-secure voting scheme, based on fully homomorphic encryption.
  arXiv  Detail & Related papers  (2020-03-25T22:20:47Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.