Ahstract-Grupptestningsproblemet är att identifiera en popu lation av K defekta objekt från en uppsättning n objekt genom att poola grupper av objekt. Resultatet av ett test för en grupp av poster är positivt om någon av posterna i gruppen är defekt och negativ på annat sätt. Målet är att omdömesgillt gruppera undergrupper av objekt så att defekta objekt kan återvinnas på ett tillförlitligt sätt med hjälp av det minsta antalet tester, samtidigt som de har en låg komplexitet dekoder. Vi beskriver SAFFRON (Sparse-grAph codes Framework För gROup testiNg), ett icke-adaptivt grupptestsystem som återvinner minst en (1-E)-fraktion (för godtyckligt små E > 0) av K defekta objekt med hög sannolikhet med m = 6C (E) K log2 n tester, där C (E) är en exakt karakteriserad konstant som endast beror på E. Till exempel, det kan bevisligen återställa minst (1-lO-G)K defekta objekt med m----'68K log2 n tester. Den beräkningsmässiga komplexiteten hos avkodningsalgoritmen är O(Klogn), vilket är den optimala ordningen. Vidare beskriver vi en systematisk metod för att stärka SAFFRON så att det tillförlitligt kan återställa uppsättningen K defekta objekt även i närvaro av felaktiga eller bullriga testresultat. Vi föreslår också Singleton-Only-SAFFRON, en variant av SAFFRON, som återställer alla K defekta objekt med m = 2e(1 + a)K log K log2 n tester med sannolikhet 1 -0 ( " ), där en > 0 är en konstant. Vårt viktigaste intellektuella bidrag innefattar den banbrytande användningen av kraftfulla metoder för densitetsutveckling av modern kodningsteori (t.ex. sparse-graph-koder) för effektiv utformning av grupptester och prestandaanalys.
Ett annat ramverk där målet är att återställa minst en (1 − )-fraktion (för godtyckligt små > 0) av den defekta uppsättningen med hög sannolikhet studerades i REF där författarna gav ett system med orderoptimala O(d log N ) tester och beräknings komplexitet.
SAFFRON: A fast, efficient, and robust framework for group testing based on sparse-graph codes
{'venue': '2016 IEEE International Symposium on Information Theory (ISIT)', 'journal': '2016 IEEE International Symposium on Information Theory (ISIT)', 'mag_field_of_study': ['Computer Science', 'Mathematics']}