Grupptest avser problemet med att identifiera (med hög sannolikhet) en (liten) undergrupp av D-defekter från en (stor) uppsättning N-poster via ett "litet" antal "poolade" tester (dvs. testerna har ett positivt resultat om även en av de punkter som testas i poolen är defekta, annars har de ett negativt resultat). För att underlätta presentationen i detta arbete fokuserar vi regimen när antalet defekter är sublinjära, dvs. D = O N 1−δ för vissa δ > 0. Provningarna kan vara ljudlösa eller bullriga och provningsförfarandet kan vara adaptivt (den pool som definierar ett test kan bero på resultatet av ett tidigare test) eller icke adaptivt (varje test utförs oberoende av resultatet av andra provningar). Ett rikt material av litteratur visar att testerna av D-log (N ) är information-teoretiskt nödvändiga och tillräckliga för grupptestningsproblemet, och ger algoritmer som uppnår denna prestanda. Det är dock först nyligen som rekonstruktionsalgoritmer med beräkningskomplexitet som är sublinjära i N har börjat undersökas (nytt arbete med [1], [2] [3] gav några av de första algoritmerna). I scenariot med adaptiva tester med bullriga resultat presenterar vi det första schemat som samtidigt är ordningsoptimalt (upp till små konstanta faktorer) i både antalet tester och avkodningskomplexet (O (D log(N )) i båda prestandamåtten). Det totala antalet steg i vår adaptiva algoritm är "liten" (O (log(D))). På samma sätt, i scenariot med icke-adaptiva tester med bullriga resultat, presenterar vi det första systemet som samtidigt är nära optimal i både antalet tester och avkodning komplexitet (via en algoritm som kräver O (D log(D) log(N )) tester och har en avkodning komplexitet av O(D(log N + log 2 D)). Slutligen presenterar vi en adaptiv algoritm som endast kräver 2 steg och för vilken både antalet tester och avkodningskomplexskalan som O(D(log N + log 2 D)). För alla tre inställningar sannolikheten för fel i våra algoritmer skalor som O (1/(poly(D)). 2 Ett något mer involverat informations-teoretiskt argument krävs om grupptestförfarandet tillåts misslyckas med "liten" sannolikhet. Men även i denna miljö, i huvudsak samma lägre gränser kan bevisas (upp till små konstant multiplikativa faktorer som kan bero på den tillåtna sannolikheten för fel) - t.ex. [13], [14]. 3 En annan smak vi inte fokuserar på i detta arbete motsvarar om utformningen av testförfarandet är deterministisk eller randomiserad. Nya arbeten - till exempel [15], [16] - ger beräkningseffektiva deterministiska mönster. I detta arbete fokuserar vi dock på "Monte Carlo" typ randomiserade designalgoritmer.
Cai m.fl. I REF föreslås Grotesque för icke-adaptiv grupptestning och adaptiv grupptestning.
GROTESQUE: Noisy Group Testing (Quick and Efficient)
{'venue': '2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton)', 'journal': '2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton)', 'mag_field_of_study': ['Mathematics', 'Computer Science']}