AI & ML
Symmetry Breaking over Multiway Channels
arXiv math.IT0 views
arXiv:2611.09466v1 Announce Type: new 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 $J$ users: each user observes only a private output and must choose a number in $\{1,\dots,J\}$, and the symmetry is broken if the $J$ numbers are distinct. Using a R\'enyi 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 $J$, 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.
Source:https://arxiv.org/abs/2611.09466PreviousUniversal Decoding for Gaussian MIMO-ISI: Spherical Ensembles and Symmetric NeighborhoodsNextCapacity of Generic Symmetric Distributed Linear Computation: The Geometry of Relations
Related posts
Nvidia investigating reports that CEO Jensen Huang was targeted by Chinese intelligence
0Phys.org Tech
Under fire over AI, effective altruism wants to tell its own story
0Phys.org Tech

'I am deeply sorry': Jensen Huang affair with suspected Chinese spy sees Nvidia open investigation into its CEO — but what happens next?
0TechRadar
What free AI training in Nepal can teach you before you pay for a class
0dev.to

Agents draft. People decide.
0dev.to UX

โค้ดเพิ่ม 400% แต่คุณไม่ได้เร็วขึ้น 400%: GitHub ชี้คอขวดใหม่อยู่ที่การรีวิว
0dev.to GitHub