Alon, Noga and Asodi, Vera (2007) Tracing Many Users With Almost No Rate Penalty. IEEE Transactions on Information Theory, 53 (1). pp. 437439. ISSN 00189448. https://resolver.caltech.edu/CaltechAUTHORS:ALOieeetit07

PDF
See Usage Policy. 153Kb 
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:ALOieeetit07
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$ outof$r$ multipleuser 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 singleuser 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 CCR0324906, by the Ames Wolfensohn Fund, and by the State of New Jersey. Communicated by V. V. Vaishampayan, Associate Editor At Large. 
Subject Keywords:  Multipleuser tracing codes, probabilistic construction of codes, superimposed codes 
Issue or Number:  1 
Record Number:  CaltechAUTHORS:ALOieeetit07 
Persistent URL:  https://resolver.caltech.edu/CaltechAUTHORS:ALOieeetit07 
Alternative URL:  http://dx.doi.org/10.1109/TIT.2006.887089 
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  7351 
Collection:  CaltechAUTHORS 
Deposited By:  Archive Administrator 
Deposited On:  02 Feb 2007 
Last Modified:  02 Oct 2019 23:41 
Repository Staff Only: item control page