Technical Program

Paper Detail

Paper IDA.5.1
Paper Title Group Testing with Runlength Constraints for Topological Molecular Storage
Authors Abhishek Agarwal, Olgica Milenkovic, Srilakshmi Pattabiraman, University of Illinois, Urbana-Champaign, United States; João Ribeiro, Imperial College London, United Kingdom
Session A.5: Combinatorial Coding Theory II
Presentation Lecture
Track Algebraic and Combinatorial Coding Theory
Manuscript  Click here to download the manuscript
Virtual Presentation  Click here to watch in the Virtual Symposium
Abstract Motivated by applications in topological DNA-based data storage, we introduce and study a novel setting of Non-Adaptive Group Testing (NAGT) with runlength constraints on the columns of the test matrix, in the sense that any two 1's must be separated by a run of at least d 0's. We describe and analyze a probabilistic construction of a runlength-constrained scheme in the zero-error and vanishing error settings, and show that the number of tests required by this construction is optimal up to logarithmic factors in the runlength constraint d and the number of defectives k in both cases. Our results reveal that runlength-constrained NAGT is not more restrictive than unconstrained NAGT when d=O(k), and that for almost all choices of d and k it is not more restrictive than NAGT with a column Hamming weight constraint only.

Plan Ahead


2021 IEEE International Symposium on Information Theory

11-16 July 2021 | Melbourne, Victoria, Australia

Visit Website!