New Lower Bounds for Weak Superimposed Codes

Abstract

Weak <inline-formula><tex-math notation="LaTeX">$(t,T)$</tex-math></inline-formula>-superimposed codes were introduced for noisy multimedia fingerprinting to determine the exact size of a coalition (up to <inline-formula><tex-math notation="LaTeX">$t$</tex-math></inline-formula> malicious users) under bounded adversarial noise <inline-formula><tex-math notation="LaTeX">$\Vert \epsilon \Vert \leq \frac{\sqrt{T}} {2\sqrt{2}t^{2}}$</tex-math></inline-formula>, where <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula> is the least number of positions that contain a signal from exactly one user among the coalition. It is a specialized variant of classical superimposed codes in binary multi-access channels, which are widely recognized in the literature as disjunct matrices in group testing or cover-free families in combinatorial set systems. Existing results on weak superimposed codes are limited to the lower bound on the largest asymptotic code rate and randomized constructions. In this paper, we derive a new general lower bound on the largest code rate of weak <inline-formula><tex-math notation="LaTeX">$(t,T)$</tex-math></inline-formula>-superimposed codes for all integers <inline-formula><tex-math notation="LaTeX">$t\geq 2$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$T\geq 1$</tex-math></inline-formula> by the Lovász local lemma. Moreover, we show that our result improves the best known lower bound on the largest asymptotic code rate of weak <inline-formula><tex-math notation="LaTeX">$(t,T)$</tex-math></inline-formula>-superimposed codes for infinitely many pairs of <inline-formula><tex-math notation="LaTeX">$t$</tex-math></inline-formula> and <inline-formula><tex-math notation="LaTeX">$T$</tex-math></inline-formula>.