Multiple User Tracing Codes

For integers 2 les k les r, a set of binary codewords is a k-out-of-r multiple user tracing code, if from the bitwise "or" of at most r codewords one can determine at least k of them. Single user tracing codes (k = 1) were introduced by Csuros and Ruszinko (2005) and the order of magnitude of their rate was determined to be 1/r by Alon and Asodi. Here we continue this line of investigations for the case of tracing more than one user and prove that for any fixed k, the magnitude of the rate is exactly 1/r. We show further that for some non-constant k = k(r), the rate can be better than Omega(logr/r 2 ), which is an upper bound for the rate of the union free, or superimposed codes