Robust Shift-Invariant Superimposed Codes

This work presents an algorithmic and combinatorial framework designed to generalize classical superimposed codes for use in asynchronous and noisy environments. While traditional superimposed codes rely on precise codeword alignment to ensure successful transmission by any k out of n uncoordinated users over a multiple-access channel, the structures introduced here maintain this guarantee under two more demanding conditions: (1) arbitrary cyclic shifts, representing unsynchronized transmission frames among users, and (2) adversarial corruption affecting up to a 1 - α fraction of each user's transmissions (where 0 < α ≤ 1). To construct these codes, we develop an efficient randomized Las Vegas algorithm based on the Moser-Tardos algorithmic version of the Lovász Local Lemma. Our approach yields codes with a length of t = O((k2/α2.4)logn), which is the primary parameter of interest. Notably, this length nearly matches that of the most efficient known superimposed codes that tolerate adversarial errors but require perfect synchronization, demonstrating that robust shift-invariance can be achieved with minimal overhead.