We study the large-coalition asymptotics of fingerprinting and group testing and derive explicit decoders that\nprovably achieve capacity for many of the considered models. We do this both for simple decoders (which are fast but\ncommonly require larger code lengths) and for joint decoders (which may be slower but achieve the best code\nlengths). We further make the distinction between informed decoding, where the pirate strategy is exactly known,\nand uninformed decoding, and we design decoding schemes for both settings.\nFor fingerprinting, we show that if the pirate strategy is known, the Neyman-Pearson-based log-likelihood decoders\nprovably achieve capacity, regardless of the strategy. The decoder built against the interleaving attack is further\nshown to be a universal decoder, able to deal with arbitrary attacks and achieving the uninformed capacity. This\nuniversal decoder is shown to be closely related to the Lagrange-optimized decoder of Oosterwijk et al. and the\nempirical mutual information decoder of Moulin. Joint decoders are also proposed, and we conjecture that these also\nachieve the corresponding joint capacities.\nFor group testing, the simple decoder for the classical model is shown to be more efficient than the one of Chan et al.\nand it provably achieves the simple group testing capacity. For generalizations of this model such as noisy group\ntesting, the resulting simple decoders also achieve the corresponding simple capacities.
Loading....