Technical Program

Paper Detail

Paper Title Set-Codes with Small Intersections and Small Discrepancies
Paper IdentifierTH4.R4.3
Authors Ryan Gabrys, University of Illinois at Urbana-Champaign, United States; Hoang Dau, Monash University, Australia; Charlie Colbourn, Arizona State University, United States; Olgica Milenkovic, University of Illinois at Urbana-Champaign, United States
Session Codes and Set Systems
Location Odéon, Level 3
Session Time Thursday, 11 July, 16:40 - 18:00
Presentation Time Thursday, 11 July, 17:20 - 17:40
Manuscript  Click here to download the manuscript
Abstract 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.