Asymptotics of Fingerprinting and Group Testing: Capacity-Achieving Log-Likelihood Decoders
arXiv:1404.2825 · doi:10.1186/s13635-015-0026-8
Abstract
We study the large-coalition asymptotics of fingerprinting and group testing, and derive explicit decoders that provably achieve capacity for many of the considered models. We do this both for simple decoders (fast but suboptimal) and for joint decoders (slow but optimal), and both for informed and uninformed settings. For fingerprinting, we show that if the pirate strategy is known, the Neyman-Pearson-based log-likelihood decoders provably achieve capacity, regardless of the strategy. The decoder built against the interleaving attack is further shown to be a universal decoder, able to deal with arbitrary attacks and achieving the uninformed capacity. This universal decoder is shown to be closely related to the Lagrange-optimized decoder of Oosterwijk et al. and the empirical mutual information decoder of Moulin. Joint decoders are also proposed, and we conjecture that these also achieve the corresponding joint capacities. For group testing, the simple decoder for the classical model is shown to be more efficient than the one of Chan et al. and it provably achieves the simple group testing capacity. For generalizations of this model such as noisy group testing, the resulting simple decoders also achieve the corresponding simple capacities.
arXiv comment14 pages, 2 figures
References in corpus (12)
- Boolean Compressed Sensing and Noisy Group Testing
- Note on Noisy Group Testing: Asymptotic Bounds and Belief Propagation Reconstruction
- Group Testing with Probabilistic Tests: Theory, Design and Application
- Non-adaptive Group Testing: Explicit bounds and novel algorithms
- Optimal symmetric Tardos traitor tracing schemes
- Towards joint decoding of binary Tardos fingerprinting codes
- On the Saddle-point Solution and the Large-Coalition Asymptotics of Fingerprinting Games
- Dynamic Tardos Traitor Tracing Schemes
- Asymptotics of Fingerprinting and Group Testing: Tight Bounds from Channel Capacities
- Efficient Probabilistic Group Testing Based on Traitor Tracing
- Discrete Distributions in the Tardos Scheme, Revisited
- Dynamic Traitor Tracing Schemes, Revisited