betaFeedback

WorksComputer Science

Symmetry Breaking over Multiway Channels

Abstract

Identical users running the same algorithm must often break their symmetry and agree on distinct roles, as in leader election, naming, and resource allocation. We study anonymous symmetry breaking over a discrete memoryless multiway channel invariant under permutations of its JJ users: each user observes only a private output and must choose a number in {1,…,J}\{1,\dots,J\}, and the symmetry is broken if the JJ numbers are distinct. Using a Rényi change of measure, we derive a finite-blocklength converse on the error probability of every symmetric causal protocol, including adaptive and randomized ones. For achievability, block coding with random names reduces the problem to all-source multicast, for which we derive a Gallager random-coding exponent for every fixed JJ, and a cut-set bound that limits the exponent of the probability that two names coincide or are decoded wrongly. Interactive role controllers instead let the users contend for identifiers directly: we give their exact error probability, an achievable exponent given by a spectral radius when some outputs certify a role, and a floor for finite-state controllers when every output has positive probability, and we introduce generalized musical chairs. On a noisy bandit channel motivated by multiplayer multi-armed bandits, with noiseless collisions and arms of a common mean below one, interactive schemes provably exceed the limit of name decoding, and numerical estimates suggest the same with noisy collisions. For two users, noiseless collisions, one informative arm and a silent arm, the optimal error probability is determined up to a factor of two.

Introduction

Anonymous agents must often agree on distinct roles before any higher-level distributed task can begin. This symmetry-breaking step appears as leader election, naming, rendezvous, and channel or resource allocation. The agents may be radio devices or identical software programs (for instance, copies of the same AI model started from the same prompt) that must accomplish a task jointly without a coordinator. These problems tend to be harder when every agent starts from the same prior information, executes the same algorithm, and observes only a private noisy response to the joint actions. Shared randomness does not by itself break the symmetry, since all users see the same random value. Independent private randomness creates different tentative identifiers, but two users may still draw the same one, and they have to find out through the channel whether or not this has happened.

Our main motivation is the decentralized multiplayer multi-armed bandit problem. In this model, JJ players repeatedly choose among KK arms and observe private rewards. The players label the arms consistently, and they act in synchronized time slots, so that they share a common clock but no common identity. Simultaneous use of the same arm causes a collision and suppresses the corresponding rewards. Algorithms with strong regret guarantees use collisions to assign roles and exchange statistics [1, 2, 3, 4]; see [5] for a recent survey. State-of-the-art algorithms typically start with an initialization phase in which the players obtain distinct ranks, and the simplest rule to accomplish this is called musical chairs [6]: each player selects a random arm until they receive a nonzero reward, and then keeps selecting that arm, since without a nonzero reward proves that nobody else pulled it. Random ranks are also used to break the symmetry in [7], and initialization without collision information is studied in [8]. The resulting channel model was formalized as the bandit channel in [9]. Unlike a conventional multiple-access channel, each player is simultaneously a transmitter and a receiver, its own action is known as receiver side information, and interference is useful because it carries information about the actions of the other players.

Two architectures come to mind for symmetry breaking over such a channel. In the first, each user draws a long random name and transmits the codeword of a common codebook indexed by its name; every user then decodes the names of the others, and ranking the names gives distinct identifiers unless two names coincide—an event of exponentially small probability in the number of bits used to encode the name—or decoding fails. This turns symmetry breaking into all-source multicast over a multiway channel. The two-user case is naturally related to Shannon’s two-way channel [10], for which a complete single-letter capacity characterization is unavailable in general [11], [12]. With more than two users, each receiver must recover every other user’s message. A tractable inner bound is nevertheless obtained by independent random coding and simultaneous decoding: at a fixed receiver, the other J−1J-1 codewords form a multiple-access channel with the receiver’s own codeword as side information. In [9], two players communicate over the bandit channel with a common codebook and inputs that do not depend on the outputs: the random-coding exponent and the achievable rate are derived, and Shannon’s outer bound for the two-way channel is evaluated as an upper bound on the capacity. In [13], block coding with random names breaks the symmetry

R. Zhang is with INRIA, France. R. Combes and S. Yang are with CentraleSupélec, Paris-Saclay University, France. This paper is supported by the CHIST-ERA Wireless AI 2022 call MLDR project (ANR-23-CHR4-0005), partially funded by AEI and NCN under projects PCI2023-145958-2 and 2023/05/Y/ST7/00004, respectively. This paper was presented in part at the 2025 IEEE Information Theory Workshop (ITW), Sydney, Australia, September–October 2025, and at the 2026 IEEE International Symposium on Information Theory (ISIT), Guangzhou, China, June–July 2026. between two players on that channel, with codebooks that time-share between input laws; its error exponent is derived under maximum-likelihood and universal decoding, and the regret of the resulting initialization phase of a bandit algorithm is bounded, with a minimax lower bound. The two-user, noiseless case of our block-coding results with a single input law is therefore in [9], [13] (see Section VI-C), and so is the value of our name-decoding ceiling for two users and arms with equal means (Proposition 15). The change-of-measure converses, block coding and the cut-set bound for J≥3J \ge3 users, the ceiling on the name-decoding exponent, the interactive role controllers and noisy collisions are not in [9], [13], and universal decoding and regret are not treated here. In the second architecture, the users contend directly for the identifiers in [J]:={1,…,J}[J] := \{1,\ldots,J\}. A user keeps its tentative identifier as long as its outputs suggest that nobody else holds it, and draws a new one otherwise, as in musical chairs. No name is decoded: the channel itself resolves the conflicts.

In this paper, we consider the problem of determining how fast the probability of error of symmetry breaking can decay with the number of channel uses, for every strategy. For those two architectures we quantify their error exponents, and we show that, on the noisy bandit channel below, the second architecture can exceed every name-decoding exponent of the first, that is, every exponent of the probability that two names coincide or are decoded wrongly: provably with noiseless collisions, and according to numerical estimates with noisy ones.

We consider a memoryless channel whose law is unchanged when the users are permuted: permuting the inputs of the users permutes their outputs in the same way, and the outputs may be arbitrarily correlated given the inputs. All users apply the same strategy: the input of a user may depend on its own past outputs, the users may use common and private randomness, and each user outputs a number in [J][J]. The symmetry is broken if the JJ numbers are distinct. Section II gives the formal definition.

We then specialize to a noisy bandit channel, in which arm xx yields a Bernoulli reward with probability μx\mu_x when it is pulled by a single user and with probability εx\varepsilon_x when it is shared. The case εx=0\varepsilon_x = 0 for every arm is the bandit channel of [9], where a reward certifies that the user was alone on its arm. Allowing εx>0\varepsilon_x > 0 is not meant as a detailed model of collisions, although a collision does not need to suppress every reward, for instance with capture in wireless systems or imperfect collision detection, and nonzero rewards on collisions are also considered in multiplayer bandits [14]. It is the simplest departure from certified outputs: the outputs stay binary and conditionally independent, the channel stays symmetric, and only a collision can change the law of an output—but a reward no longer proves that the user was alone. For εx=0\varepsilon_x = 0, a single observation can certify a role, musical chairs and its generalization apply, and, for two users, the converse can be tight. For 0<μx<10 < \mu_x < 1 and 0<εx<10 < \varepsilon_x < 1, every output has positive probability, no observation is conclusive, the users have to accumulate evidence over many uses, and a gap remains between the converses and the schemes. When εx=μx\varepsilon_x = \mu_x for every xx, collisions are invisible and symmetry breaking is impossible.

The objective of assigning distinct names to initially indistinguishable processes is classical in distributed computing [15], [16]. Under the names naming and initialization, randomized wireless networking protocols assign identifiers to anonymous stations in single- and multichannel collision models [17], [18]. More recent work treats anonymous beeping networks, where a listening node learns only whether at least one neighbor beeped [19], [20], also with noisy beeps [21]. That literature primarily optimizes rounds, energy, random bits, and success probability for particular distributed models. Indistinguishability arguments give lower bounds for contention resolution over collision channels [22], [23], and optimal protocols are known for two parties [24]; the collision channel without feedback [25] is an information-theoretic model of uncoordinated access in which the users have distinct protocol sequences. Our symmetry-breaking criterion is the same underlying task, but the object of study is its reliability as a function of the number of channel uses nn over a general noisy multiway channel.

The closely related leader-election task asks each user to output a bit, with success when exactly one user outputs 1 and becomes the leader while other users become followers; stronger formulations additionally require identifying or communicating with the elected leader [26]. A symmetry-breaking protocol also solves the task of leader election if the user whose identifier is 1 elects itself as the leader by outputting 1, so that an election failure is contained in a symmetry-breaking failure. For J=2J = 2 the tasks are exactly equivalent, since an election bit LjL_j is mapped back to the identifier 2−Lj2 - L_j without additional observations. For J>2J > 2, symmetry breaking requires all JJ identifiers to be different, whereas election may leave the followers indistinguishable. Neither criterion additionally requires a certificate or common knowledge of success.

Both tasks are special cases of a population version of symmetry breaking. Given LL states and a population vector N=(N1,…,NL)\mathbf{N} = (N_1,\ldots,N_L) with N1+⋯+NL=JN_1+\cdots+N_L = J, the users succeed when exactly NlN_l of them choose state ll, for every l∈[L]l \in[L]. Our task is N=(1,…,1)\mathbf{N} = (1,\ldots,1), and leader election is N=(1,J−1)\mathbf{N} = (1,J-1). Our task is the finest of these: if every user maps its identifier through a fixed map from [J][J] to [L][L] that sends exactly NlN_l identifiers to state ll, for instance one that splits the ranks into consecutive blocks of sizes N1,…,NLN_1,\ldots,N_L, a protocol for N=(1,…,1)\mathbf{N} = (1,\ldots,1) becomes a protocol for N\mathbf{N} with no larger error probability. Every achievability result of this paper therefore holds for every population vector, and so do the converses of Section III, for every population vector with at least two positive entries (Proposition 2). Apart from this, the rest of the paper treats N=(1,…,1)\mathbf{N} = (1,\ldots,1) only.

The differences between symmetry breaking and two related information-theoretic problems are worth mentioning. Coordination capacity includes task assignment without duplication, for which the target law is uniform over the permutations of the tasks [27]. Its terminals, however, have fixed labels and use terminal-dependent mappings over prescribed communication links. Unsourced random access instead gives statistically identical transmitters a common codebook and asks one central receiver to recover an unordered message list [28]. Here there is no central observer: every anonymous user is simultaneously a transmitter and a receiver, sees a different private output, and must infer its own place in a common ordering. The distinction is already visible before communication. If CC is common randomness and ΠC\Pi_C is a random permutation, labeled terminals may set their values to ΠC(j)\Pi_C(j), which is collision-free, whereas identical anonymous maps of CC produce the same value for every user. Private randomness can create different tentative names, but the channel must let the users determine their relative order consistently.

Our converse is a change-of-measure argument in the spirit of the meta-converse [29] and of its Rényi form [30]; with noninteracting references, its exponent has the form of Haroutunian’s sphere-packing bound for channels with feedback [31]. Change-of-measure lower bounds that hold for adaptive strategies are also standard in bandit problems [32, 33].

Finally, when there are more arms than players, the goal of the players should be to cycle through the arms in a fair fashion while avoiding collisions. This task is sometimes called orthogonalization [1] and can be reduced to symmetry breaking as well.

To summarize, the symmetry-breaking objective is ubiquitous in distributed systems; our emphasis is its information-theoretic reliability. To the best of our knowledge, the present work is the first Shannon-theoretic treatment of anonymous symmetry breaking over a general noisy symmetric multiway channel, with private receiver observations, identical causal strategies, general converses, reliability exponents, and both coding and interactive achievability.

Contributions

The main contributions are summarized as follows.

  1. Formulation. We cast anonymous symmetry breaking as a Shannon-theoretic problem for JJ users over a general symmetric memoryless channel, with the error probability of the best strategy and its reliability exponent as the quantities of interest (Section II).

  1. A converse for every strategy. We prove finite-blocklength converses on the probability of error for every symmetric causal strategy, including adaptive ones and those using arbitrary common and private randomness (Section III). We compare the channel with a reference under which the identifiers of mm users are conditionally i.i.d. given a latent variable, so that they collide with probability at least that of i.i.d. uniform draws. A Rényi change of measure transfers this probability to the true channel, at a cost that is the nn-th power of a one-step quantity of a nonnegative kernel defining the reference. The bound is optimized over the Rényi order and the kernel. Two instances are explicit: a noninteracting reference, whose exponent reduces to a KL-radius formula, and a common-output reference, which keeps only the trajectories on which the selected users receive identical outputs and is effective when collisions are detected without noise. The converses extend to every population vector with at least two positive entries. In the examples we evaluate kernels with m=2m=2 selected users only, and the exponents of the resulting bounds do not depend on JJ beyond the distinction between J=2J=2 and J≥3J \ge3.

  1. Block coding and the limit of name decoding. A shared random codebook and independent private names reduce achievability to all-source multicast, and the error probability is at most the probability that two names coincide, plus the multicast decoding error. For arbitrary fixed JJ, we prove a Gallager random-coding exponent for the error probability of symmetry breaking, which for i.i.d. inputs is positive if and only if I(X−j;Yj∣Xj)>0I(X_{-j};Y_j \mid X_j)>0, and is at most 1JI(X−j;Yj∣Xj)\frac{1}{J}I(X_{-j};Y_j \mid X_j). A multiway cut-set bound shows that no name-decoding scheme, block or interactive, has a name-decoding exponent above log⁡J/(J−1)\log J/(J-1). Symmetry breaking itself is not subject to this limit: for J=2J=2, a channel whose output pair is uniform on {(0,1),(1,0)}\{(0,1),(1,0)\} for any input breaks the symmetry in a single use, although it carries no information (Section IV).

  1. Interactive schemes. We introduce role controllers (§ 5), in which each user runs a probabilistic automaton, in the spirit of the finite-memory automata studied for hypothesis testing and the two-armed bandit [34, 35, 36]: it holds a tentative identifier and a state updated from its own outputs. Their error probability is the exact probability of a failure state of a Markov chain on the joint states, and every symmetric causal strategy, block coding in particular, is a role controller. When some output certifies that a role is not shared, a finite-state controller achieves an error exponent of at least −log⁡-\log of a spectral radius, with equality under a condition that holds in the cases we evaluate. When every output has positive probability, no time-invariant finite-state controller has a vanishing error probability, as time-invariant finite memory keeps the error of hypothesis testing away from zero [35]. On the noisy bandit channel with JJ arms of common parameters, a state set of bounded size with maps that vary with time does give a vanishing error probability, by a device of Cover [34], but whether it can give a positive exponent is open. We analyze confidence controllers, which accumulate evidence in a counter whose range grows with nn. We also introduce generalized musical chairs, a finite-state scheme in which a user avoids the roles on which it recently failed. It contains musical chairs as the special case of no exclusion.

  1. The noisy bandit channel. We define a noisy bandit channel with one pair of reward probabilities per arm (μx\mu_x for a user alone on arm xx, εx\varepsilon_x for each user sharing it), for which we obtain explicit converses, in closed form for arms with equal parameters, the Gallager function of block coding, and the exponents of the interactive schemes (Section VI). For two users, one informative arm and a silent arm (an arm that never yields a reward, μ2=ε2=0\mu_2=\varepsilon_2=0), and noiseless collisions ε1=0\varepsilon_1=0, the converse and one-arm musical chairs match, and the error exponent is −log⁡(1−μ1/2)-\log(1-\mu_1/2); for two users and two noiseless arms of mean one, musical chairs matches the converse as well. With noiseless collisions, musical chairs

provably exceeds every name-decoding exponent, for every number JJ of users and JJ arms of a common mean below one. With noisy collisions, our numerical estimates indicate that the confidence controllers also exceed it, but we have no proof that their exponent is positive (Table I). Generalized musical chairs goes further: for three users and three noiseless arms of mean μ=1\mu= 1, its exponent is more than twice that of musical chairs. How the optimal exponent depends on JJ is left open. The remainder of the paper is organized as follows. Section II introduces the general channel and the symmetry-breaking problem, and Section III proves the converses. Section IV develops block coding and the limits of name decoding, and Section V the interactive schemes. Section VI applies the results to the noisy bandit channel and compares the schemes with the converses, and Section VII concludes. Proofs that would interrupt the main flow are presented in the appendices.

Symmetric Channels and the Symmetry-Breaking Problem

Notation

For a positive integer mm, let [m]:={1,…,m}[m] := \{1,\ldots,m\}. For S⊆[J]S \subseteq[J], write XS:=(Xj:j∈S)X_S := (X_j : j \in S) and Sc:=[J]∖SS^c := [J] \setminus S. For j∈[J]j \in[J], write X−j:=X[J]∖{j}∈XJ−1X_{-j} := X_{[J]\setminus\{j\}} \in\mathcal{X}^{J-1}, with the indices in increasing order. For a finite set A\mathcal{A}, S⊆[J]S \subseteq[J], u∈A∣S∣u \in\mathcal{A}^{|S|} and v∈A∣Sc∣v \in\mathcal{A}^{|S^c|}, let u⊔Sv∈AJu \mathbin{\sqcup_S} v \in\mathcal{A}^J denote the vector zz with zS=uz_S = u and zSc=vz_{S^c} = v, the components of uu and vv being read in increasing index order. Thus x[J]=xS⊔SxScx_{[J]} = x_S \mathbin{\sqcup_S} x_{S^c} for every x[J]∈XJx_{[J]} \in\mathcal{X}^J. For a singleton, we abbreviate ⊔{j}\sqcup_{\{j\}} as ⊔j\sqcup_j, so that u⊔jv=(v1,…,vj−1,u,vj,…,vJ−1)u \sqcup_j v = (v_1,\ldots,v_{j-1},u,v_j,\ldots,v_{J-1}) for u∈Au \in\mathcal{A} and v∈AJ−1v \in\mathcal{A}^{J-1}, x[J]=xj⊔jx−jx_{[J]} = x_j \sqcup_j x_{-j}, and (u,v)↦u⊔jv(u,v) \mapsto u \sqcup_j v is a bijection A×AJ−1→AJ\mathcal{A} \times\mathcal{A}^{J-1} \to\mathcal{A}^J. A tuple written with a comma, such as (u,v)(u,v) or (xj,x−j)(x_j,x_{-j}), always denotes the plain concatenation of its entries. A superscript nn denotes a length-nn sequence and Xn[i]X^n[i] denotes its ii-th entry. All alphabets are finite, all logarithms are natural, and rates are measured in nats per channel use. For a finite set A\mathcal{A}, P(A)\mathcal{P}(\mathcal{A}) denotes the set of probability distributions on A\mathcal{A}. The binary entropy is denoted

h2(u):=−ulog⁡u−(1−u)log⁡(1−u),u∈[0,1].h_2(u) := -u \log u - (1-u)\log(1-u), \qquad u \in[0,1].

References

  1. [1]E. Boursier and V. Perchet, “SIC-MMAB: Synchronisation involves communication in multiplayer multi-armed bandits,” in Proc. Adv. Neural Inf. Process. Syst. (NeurIPS 2019), vol. 32, 2019.arxiv.org/abs/1809.08151
  2. [2]C. Shi, W. Xiong, C. Shen, and J. Yang, “Decentralized multi-player multi-armed bandits with no collision information,” in Proc. 23rd Int. Conf. Artif. Intell. Statist. (AISTATS), vol. 108, 2020, pp. 1519–1528.arxiv.org/abs/2003.00162
  3. [3]P.-A. Wang, A. Proutiere, K. Ariu, Y. Jedra, and A. Russo, “Optimal algorithms for multiplayer multi-armed bandits,” in Proc. 23rd Int. Conf. Artif. Intell. Statist. (AISTATS), vol. 108, 2020, pp. 4120–4129.
  4. [4]W. Huang, R. Combès, and C. Trinh, “Towards optimal algorithms for multi-player bandits without collision sensing information,” in Proc. 35th Conf. Learn. Theory (COLT), vol. 178, 2022, pp. 1990–2012.arxiv.org/abs/2103.13059
  5. [5]E. Boursier and V. Perchet, “A survey on multi-player bandits,” J. Mach. Learn. Res., vol. 25, no. 137, pp. 1–45, 2024.
  6. [6]J. Rosenski, O. Shamir, and L. Szlak, “Multi-player bandits – a musical chairs approach,” in Proc. 33rd Int. Conf. Mach. Learn. (ICML), vol. 48, 2016, pp. 155–163.arxiv.org/abs/1512.02866
  7. [7]N. Anandkumar, N. Michael, A. K. Tang, and A. Swami, “Distributed algorithms for learning and cognitive medium access with logarithmic regret,” IEEE J. Sel. Areas Commun., vol. 29, no. 4, pp. 731–745, 2011.
  8. [8]G. Lugosi and A. Mehrabian, “Multi-player bandits without observing collision information,” Math. Oper. Res., vol. 47, no. 2, pp. 1247–1265, 2022.
  9. [9]R. Zhang, R. Combes, and S. Yang, “The bandit channel,” in Proc. 2025 IEEE Inf. Theory Workshop (ITW), 2025, pp. 1–7.
  10. [10]C. E. Shannon, “Two-way communication channels,” in Proc. 4th Berkeley Symp. Math. Statist. Probab., J. Neyman, Ed., vol. 1. Berkeley, CA, USA: Univ. California Press, 1961, pp. 611–644.
  11. [11]T. Han, “A general coding scheme for the two-way channel,” IEEE Trans. Inf. Theory, vol. 30, no. 1, pp. 35–44, 1984.DOI
  12. [12]G. Dueck, “The capacity region of the two-way channel can exceed the inner bound,” Inf. Control, vol. 40, no. 3, pp. 258–266, 1979.DOI
  13. [13]R. Zhang, H. Miyamoto, R. Combes, and S. Yang, “An efficient synchronization scheme for distributed bandits,” in Proc. 2026 IEEE Int. Symp. Inf. Theory (ISIT), 2026, pp. 1–6.DOI
  14. [14]A. Magesh and V. V. Veeravalli, “Decentralized heterogeneous multi-player multi-armed bandits with non-zero rewards on collisions,” IEEE Trans. Inf. Theory, vol. 68, no. 4, pp. 2622–2634, 2022.arxiv.org/abs/1910.09089
  15. [15]A. Itai and M. Rodeh, “Symmetry breaking in distributed networks,” Inf. Comput., vol. 88, no. 1, pp. 60–87, 1990.DOI
  16. [16]R. J. Lipton and A. Park, “The processor identity problem,” Inf. Process. Lett., vol. 36, no. 2, pp. 91–94, 1990.DOI
  17. [17]T. Hayashi, K. Nakano, and S. Olariu, “Randomized initialization protocols for packet radio networks,” in Proc. 13th Int. Parallel Process. Symp. and 10th Symp. Parallel Distrib. Process. (IPPS/SPDP), 1999, pp. 544–548.DOI
  18. [18]K. Nakano and S. Olariu, “Energy-efficient initialization protocols for single-hop radio networks with no collision detection,” IEEE Trans. Parallel Distrib. Syst., vol. 11, no. 8, pp. 851–863, 2000.DOI
  19. [19]B. S. Chlebus, G. De Marco, and M. Talo, “Naming a channel with beeps,” Fundam. Inform., vol. 153, no. 3, pp. 199–219, 2017.DOI
  20. [20]L. S. Aldawsari and T. Altman, “Naming in multichannel with beeps in the strong model,” Appl. Sci., vol. 10, no. 20, p. 7164, 2020.DOI
  21. [21]Y. Ashkenazi, R. Gelles, and A. Leshem, “Noisy beeping networks,” Inf. Comput., vol. 289, 2022, art. no. 104925.DOI
  22. [22]D. E. Willard, “Log-logarithmic selection resolution protocols in a multiple access channel,” SIAM J. Comput., vol. 15, no. 2, pp. 468–477, 1986.DOI
  23. [23]C. Newport, “Radio network lower bounds made easy,” in Proc. 28th Int. Symp. Distrib. Comput. (DISC), ser. Lecture Notes in Computer Science, F. Kuhn, Ed., vol. 8784. Berlin, Heidelberg, Germany: Springer, 2014, pp. 258–272.
  24. [24]D. Wang, “Optimal protocols for 2-party contention resolution,” in Proc. 23rd Int. Symp. Stabilization, Safety, Security Distrib. Syst. (SSS), ser. Lecture Notes in Computer Science, C. Johnen, E. M. Schiller, and S. Schmid, Eds., vol. 13046. Cham, Switzerland: Springer, 2021, pp. 456–468.arxiv.org/abs/2407.08845
  25. [25]J. L. Massey and P. Mathys, “The collision channel without feedback,” IEEE Trans. Inf. Theory, vol. 31, no. 2, pp. 192–204, 1985.DOI
  26. [26]M. Ghaffari and C. Newport, “Leader election in unreliable radio networks,” in Proc. 43rd Int. Colloq. Automata, Lang., Program. (ICALP), ser. LIPIcs, vol. 55. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2016, pp. 138:1–138:14.
  27. [27]P. Cuff, H. H. Permuter, and T. M. Cover, “Coordination capacity,” IEEE Trans. Inf. Theory, vol. 56, no. 9, pp. 4181–4206, 2010.DOI
  28. [28]Y. Polyanskiy, “A perspective on massive random-access,” in Proc. 2017 IEEE Int. Symp. Inf. Theory (ISIT), 2017, pp. 2523–2527.DOI
  29. [29]Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” IEEE Trans. Inf. Theory, vol. 56, no. 5, pp. 2307–2359, 2010.DOI
  30. [30]Y. Polyanskiy and S. Verdú, “Arimoto channel coding converse and Rényi divergence,” in Proc. 48th Annu. Allerton Conf. Commun., Control, Comput., 2010, pp. 1327–1333.
  31. [31]E. A. Haroutunian, “Lower bound for error probability in channels with feedback,” Probl. Inf. Transm., vol. 13, no. 2, pp. 36–44, 1977, translated from Prob. Peredachi Inf., vol. 13, no. 2, pp. 36–44, 1977.
  32. [32]E. Kaufmann, O. Cappé, and A. Garivier, “On the complexity of best-arm identification in multi-armed bandit models,” J. Mach. Learn. Res., vol. 17, no. 1, pp. 1–42, 2016.
  33. [33]A. Garivier, P. Ménard, and G. Stoltz, “Explore first, exploit next: The true shape of regret in bandit problems,” Math. Oper. Res., vol. 44, no. 2, pp. 377–399, 2019.
  34. [34]T. M. Cover, “Hypothesis testing with finite statistics,” Ann. Math. Statist., vol. 40, no. 3, pp. 828–835, 1969.DOI
  35. [35]M. E. Hellman and T. M. Cover, “Learning with finite memory,” Ann. Math. Statist., vol. 41, no. 3, pp. 765–782, 1970.DOI
  36. [36]T. M. Cover and M. E. Hellman, “The two-armed-bandit problem with time-invariant finite memory,” IEEE Trans. Inf. Theory, vol. 16, no. 2, pp. 185–195, 1970.DOI
  37. [37]R. G. Gallager, Information Theory and Reliable Communication. New York, NY, USA: Wiley, 1968.
  38. [38]G. H. Hardy, J. E. Littlewood, and G. Pólya, Inequalities, 2nd ed. Cambridge, U.K.: Cambridge Univ. Press, 1952.
  39. [39]T. van Erven and P. Harremoës, “Rényi divergence and Kullback–Leibler divergence,” IEEE Trans. Inf. Theory, vol. 60, no. 7, pp. 3797–3820, 2014.
  40. [40]P. J. C. Dickinson and L. Gijben, “On the computational complexity of membership problems for the completely positive cone and its dual,” Comput. Optim. Appl., vol. 57, no. 2, pp. 403–415, 2014.DOI
  41. [41]R. G. Gallager, “A perspective on multicaccess channels,” IEEE Trans. Inf. Theory, vol. 31, no. 2, pp. 124–142, 1985.
  42. [42]A. Nazari, A. Anastasopoulos, and S. S. Pradhan, “Error exponent for multiple-access channels: Lower bounds,” IEEE Trans. Inf. Theory, vol. 60, no. 9, pp. 5095–5115, 2014.arxiv.org/abs/1010.1303
  43. [43]A. El Gamal and Y.-H. Kim, Network Information Theory. Cambridge, U.K.: Cambridge Univ. Press, 2011.
  44. [44]S. H. Lim, Y.-H. Kim, A. El Gamal, and S.-Y. Chung, “Noisy network coding,” IEEE Trans. Inf. Theory, vol. 57, no. 5, pp. 3132–3152, 2011.
  45. [45]T. Berg, O. Ordentlich, and O. Shayevitz, “Statistical inference with limited memory: A survey,” IEEE J. Sel. Areas Inf. Theory, vol. 5, pp. 623–644, 2024.arxiv.org/abs/2312.15225

Paper details

vlnc:W_jzpeh7fj
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents