2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | A.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
