### Abstract

For integers n, r ≥ 2 and 1 ≤ k ≤ r, a family F of subsets of [n] = {1,⋯,n} is called k-out-of-r multiple-user tracing if, given the union of any ℓ ≤ r sets from the family, one can identify at least (min(k, ℓ) of them. This is a generalization of superimposed families (k = r) and of single-user tracing families (k = 1). The study of such families is motivated by problems in molecular biology and communication. In this correspondence, we study the maximum possible cardinality of such families, denoted by h(n, r, k), and show that there exist absolute constants c_{1}, c_{2}, c_{3}, c_{4} < 0 such that min(c_{1}/r, c_{3}/k^{2}) ≤ log h(n, r, k)/n ≤ min (c_{2}/r, c_{4} log k/k^{2}). In particular, for all k ≤ √r, log h(n, r, k)/n = θ(1/r). This improves an estimate of Laczay and Ruszinkó.

Original language | English (US) |
---|---|

Pages (from-to) | 437-439 |

Number of pages | 3 |

Journal | IEEE Transactions on Information Theory |

Volume | 53 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2007 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Information Systems
- Computer Science Applications
- Library and Information Sciences

### Keywords

- Multiple-user tracing codes
- Probabilistic construction of codes
- Superimposed codes

## Fingerprint Dive into the research topics of 'Tracing many users with almost no rate penalty'. Together they form a unique fingerprint.

## Cite this

*IEEE Transactions on Information Theory*,

*53*(1), 437-439. https://doi.org/10.1109/TIT.2006.887089