A Caltech Library Service

Tracing Many Users With Almost No Rate Penalty

Alon, Noga and Asodi, Vera (2007) Tracing Many Users With Almost No Rate Penalty. IEEE Transactions on Information Theory, 53 (1). pp. 437-439. ISSN 0018-9448.

See Usage Policy.


Use this Persistent URL to link to this item:


For integers $n, r geq 2$ and $1 leq k leq r$, a family ${cal F}$ of subsets of $[n] = {1,ldots,n}$ is called $k$ -out-of-$r$ multiple-user tracing if, given the union of any $ell leq r$ sets from the family, one can identify at least $min(k,ell)$ 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 $$minleft({c_1over r}, {c_3over k^2}right) leq {log h(n,r,k)over n} leq minleft({c_2over r}, {c_4 log k over k^2}right).$$ In particular, for all $k leq sqrt{r}, ,{log h(n,r,k)over n} =Theta(1/r)$. This improves an estimate of Laczay and Ruszinkó.

Item Type:Article
Additional Information:© Copyright 2007 IEEE. Reprinted with permission. Manuscript received April 21, 2006; revised October 12, 2006. This work was supported in part by the Israel Science Foundation, by a USA–Israeli BSF under Grant, by the National Science Foundation under Grant CCR-0324906, by the Ames Wolfensohn Fund, and by the State of New Jersey. Communicated by V. V. Vaishampayan, Associate Editor At Large.
Subject Keywords:Multiple-user tracing codes, probabilistic construction of codes, superimposed codes
Issue or Number:1
Record Number:CaltechAUTHORS:ALOieeetit07
Persistent URL:
Alternative URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:7351
Deposited By: Archive Administrator
Deposited On:02 Feb 2007
Last Modified:02 Oct 2019 23:41

Repository Staff Only: item control page