TY - GEN
T1 - Set-Codes with Small Intersections and Small Discrepancies
AU - Gabrys, Ryan
AU - Dau, H.
AU - Colbourn, C. J.
AU - Milenkovic, O.
N1 - Funding Information:
Acknowledgment. The authors gratefully acknowledge discussions with Joao Ribeiro, Imperial College, London. The work was supported by the NSF grants CCF 1526875, 1816913, and 1813729 and the DARPA Molecular Informatics program.
Publisher Copyright:
© 2019 IEEE.
PY - 2019/7
Y1 - 2019/7
N2 - We are concerned with the problem of designing large families of subsets over a common labeled ground set that have small pairwise intersections and the property that the maximum discrepancy of the label values within each of the sets is less than or equal to one. Our results, based on transversal designs, factorizations of packings and Latin rectangles, show that by jointly constructing the sets and labeling scheme, one can achieve optimal family sizes for many parameter choices. Probabilistic arguments akin to those used for pseudorandom generators lead to significantly suboptimal results when compared to the proposed combinatorial methods. The design problem considered is motivated by applications in molecular data storage.
AB - We are concerned with the problem of designing large families of subsets over a common labeled ground set that have small pairwise intersections and the property that the maximum discrepancy of the label values within each of the sets is less than or equal to one. Our results, based on transversal designs, factorizations of packings and Latin rectangles, show that by jointly constructing the sets and labeling scheme, one can achieve optimal family sizes for many parameter choices. Probabilistic arguments akin to those used for pseudorandom generators lead to significantly suboptimal results when compared to the proposed combinatorial methods. The design problem considered is motivated by applications in molecular data storage.
UR - http://www.scopus.com/inward/record.url?scp=85073169842&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85073169842&partnerID=8YFLogxK
U2 - 10.1109/ISIT.2019.8849651
DO - 10.1109/ISIT.2019.8849651
M3 - Conference contribution
AN - SCOPUS:85073169842
T3 - IEEE International Symposium on Information Theory - Proceedings
SP - 2359
EP - 2363
BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019
Y2 - 7 July 2019 through 12 July 2019
ER -