In this paper, we study bounds on the minimum length of ( k, n, d)-superimposed codes introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints. A ( k, n, d)-superimposed code of length t is a t × n binary matrix such that any two 1’s in each column are separated by a run of at least d 0’s, and such that for any column c and any other k−1 columns, there exists a row where c has 1 and all the remaining k−1 columns have 0. Agarwal et al. proved the existence of such codes with t = Θ( dk log( n/k) + k 2 log( n/k)). Here we investigate more in detail the coefficients in front of these two main terms as well as the role of lower order terms. We show that improvements can be obtained over the construction in [1] by using different constructions and by an appropriate exploitation of the Lovász Local Lemma in this context. Our findings also suggest O( n k ) randomized Las Vegas algorithms for the construction of such codes. We also extend our results to Two-Stage Group Testing algorithms with runlength constraints.

Achievable Rates and Algorithms for Group Testing with Runlength Constraints

Fiore, Stefano Della;Vaccaro, Ugo
2022-01-01

Abstract

In this paper, we study bounds on the minimum length of ( k, n, d)-superimposed codes introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints. A ( k, n, d)-superimposed code of length t is a t × n binary matrix such that any two 1’s in each column are separated by a run of at least d 0’s, and such that for any column c and any other k−1 columns, there exists a row where c has 1 and all the remaining k−1 columns have 0. Agarwal et al. proved the existence of such codes with t = Θ( dk log( n/k) + k 2 log( n/k)). Here we investigate more in detail the coefficients in front of these two main terms as well as the role of lower order terms. We show that improvements can be obtained over the construction in [1] by using different constructions and by an appropriate exploitation of the Lovász Local Lemma in this context. Our findings also suggest O( n k ) randomized Las Vegas algorithms for the construction of such codes. We also extend our results to Two-Stage Group Testing algorithms with runlength constraints.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4811071
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact