Tracing Many Users With Almost No Rate Penalty
- Creators
- Alon, Noga
- Asodi, Vera
Abstract
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ó.
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.Files
Name | Size | Download all |
---|---|---|
md5:88e13caad41f9e4479e0ac8116fd51f7
|
157.3 kB | Preview Download |
Additional details
- Eprint ID
- 7351
- Resolver ID
- CaltechAUTHORS:ALOieeetit07
- Created
-
2007-02-02Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field