Explicit Non-Adaptive Combinatorial Group Testing Schemes
| dc.creator | Porat, Ely | |
| dc.creator | Rothschild, Amir | |
| dc.date | 2007-12-22 | |
| dc.date | 2008-04-29 | |
| dc.date.accessioned | 2026-07-07T09:35:25Z | |
| dc.date.available | 2026-07-07T09:35:25Z | |
| dc.description | Group testing is a long studied problem in combinatorics: A small set of $r$ ill people should be identified out of the whole ($n$ people) by using only queries (tests) of the form "Does set X contain an ill human?". In this paper we provide an explicit construction of a testing scheme which is better (smaller) than any known explicit construction. This scheme has $\bigT{\min[r^2 \ln n,n]}$ tests which is as many as the best non-explicit schemes have. In our construction we use a fact that may have a value by its own right: Linear error-correction codes with parameters $[m,k,δm]_q$ meeting the Gilbert-Varshamov bound may be constructed quite efficiently, in $\bigT{q^km}$ time. | |
| dc.description | 15 pages, accepted to ICALP 2008 | |
| dc.identifier | https://arxiv.org/abs/0712.3876 | |
| dc.identifier | http://arxiv.org/abs/0712.3876 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/159826 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Explicit Non-Adaptive Combinatorial Group Testing Schemes | |
| dc.type | text |