Vi anser att följande "effektivt decodable" icke adaptiv grupp testning problem. Det finns en okänd sträng x  till {0, 1} n med som mest d de i den. Vi är tillåtna att testa någon delmängd S  på [n] av indexen. Svaret på testet visar om xi = 0 för alla i  på S eller inte. Målet är att utforma så få tester som möjligt (säg, t tester) så att x kan identifieras så snabbt som möjligt (säg, poly(t)-tid). Effektivt decodable icke-adaptiv grupp testning har tillämpningar inom många områden, inklusive dataström algoritmer och data kriminalteknik. En icke-adaptiv gruppteststrategi kan representeras av en t × n-matris, som är staplandet av alla karakteristiska vektorer i testerna. Det är välkänt att om denna matris är d-disjunkt, då alla testresultat motsvarar unikt en okänd ingång sträng. Dessutom vet vi hur man konstruerar d-disjunkt matriser med t = O(d 2 log n) effektivt. Men, dessa matriser hittills bara tillåter en "avkodning" tid av O (nt), som kan vara exponentiellt större än poly(t) för relativt små värden av d. Detta papper presenterar en slumpmässighet effektiv konstruktion av d-disjunkt matriser med t = O(d 2 log n) som kan avkodas i tid poly(d) · t log 2 t + O(t 2 ). Såvitt vi vet är detta det första resultatet som uppnår en effektiv avkodningstid och matchar den mest kända O(d 2 log n) som är bunden till antalet tester. Vi derandomiserar också konstruktionen, vilket resulterar i en polynomisk tidsdeterministisk konstruktion av sådana matriser när d = O(log n/ log log n). En viktig byggsten i vår konstruktion är begreppet (d, )-lista disjunkt matriser, som representerar den mer allmänna "lista grupp testning" problem vars mål är att producera mindre än d + positioner i x, inklusive alla (på de flesta d) positioner som har en i dem. Lista disjunkt matriser visar sig vara intressanta objekt i sin egen rätt och ansågs också självständigt av [Cheraghchi, FCT 2009]. Vi presenterar kopplingar mellan diskonterade matriser, expanderare, dispergerare och disjunktmatriser. Lista disjunkt matriser har tillämpningar för att konstruera (d, )-parsitet separator strukturer [Ganguly, ISAAC 2008] och för att bygga toleranta testare för Reed-Solomon koder i dataströmsmodellen.
Slutligen föreslås en slumpmässig effektiv konstruktion av diskonterade matriser i REF med en avkodningstid på OðpðB och Á B log 2 B, OðB 2, där B 1⁄4 OðK 2 log S påvisar ett polynom.
Efficiently decodable non-adaptive group testing
{'venue': "SODA '10", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}