{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T06:49:18Z","timestamp":1774680558235,"version":"3.50.1"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,2,12]],"date-time":"2013-02-12T00:00:00Z","timestamp":1360627200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2013,11]]},"DOI":"10.1007\/s00453-013-9754-7","type":"journal-article","created":{"date-parts":[[2013,2,11]],"date-time":"2013-02-11T11:09:41Z","timestamp":1360580981000},"page":"384-417","source":"Crossref","is-referenced-by-count":22,"title":["Improved Constructions for Non-adaptive Threshold Group Testing"],"prefix":"10.1007","volume":"67","author":[{"given":"Mahdi","family":"Cheraghchi","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,2,12]]},"reference":[{"key":"9754_CR1","volume-title":"Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"A. Ben-Aroya","year":"2009","unstructured":"Ben-Aroya, A., Ta-Shma, A.: Constructing small-bias sets from algebraic-geometric codes. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2009)"},{"key":"9754_CR2","first-page":"100","volume":"78","author":"A. Blass","year":"2002","unstructured":"Blass, A., Gurevich, Y., testing, P.: Bull. Eur. Assoc. Theor. Comput. Sci. 78, 100\u2013132 (2002)","journal-title":"Bull. Eur. Assoc. Theor. Comput. Sci."},{"issue":"1","key":"9754_CR3","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0888-7543(95)80078-Z","volume":"26","author":"W.J. Bruno","year":"1995","unstructured":"Bruno, W.J., Knill, E., Balding, D.J., Bruce, D.C., Doggett, N.A., Sawhill, W.W., Stallings, R.L., Whittaker, C.C., Torney, D.C.: Efficient pooling designs for library screening. Genomics 26(1), 21\u201330 (1995)","journal-title":"Genomics"},{"key":"9754_CR4","first-page":"659","volume-title":"Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC)","author":"M. Capalbo","year":"2002","unstructured":"Capalbo, M., Reingold, O., Vadhan, S., Wigderson, A.: Randomness conductors and constant-degree expansion beyond the degree\/2 barrier. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC), pp. 659\u2013668 (2002)"},{"key":"9754_CR5","doi-asserted-by":"crossref","first-page":"1581","DOI":"10.1016\/j.dam.2008.06.003","volume":"157","author":"H.-B. Chen","year":"2009","unstructured":"Chen, H.-B., Fu, H.-L.: Nonadaptive algorithms for threshold group testing. Discrete Appl. Math. 157, 1581\u20131585 (2009)","journal-title":"Discrete Appl. Math."},{"issue":"2\u20133","key":"9754_CR6","doi-asserted-by":"crossref","first-page":"121","DOI":"10.1007\/s10878-007-9067-3","volume":"14","author":"H.-B. Chen","year":"2007","unstructured":"Chen, H.-B., Du, D.-Z., Hwang, F.-K.: An unexpected meeting of four seemingly unrelated problems: graph testing, DNA complex screening, superimposed codes and secure key distribution. J. Comb. Optim. 14(2\u20133), 121\u2013129 (2007)","journal-title":"J. Comb. Optim."},{"issue":"3","key":"9754_CR7","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/s11590-007-0070-5","volume":"2","author":"H.-B. Chen","year":"2008","unstructured":"Chen, H.-B., Fu, H.-L., Hwang, F.-K.: An upper bound of the number of tests in pooling designs for the error-tolerant complex model. Optim. Lett. 2(3), 425\u2013431 (2008)","journal-title":"Optim. Lett."},{"issue":"2","key":"9754_CR8","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1089\/cmb.2007.0195","volume":"15","author":"Y. Cheng","year":"2008","unstructured":"Cheng, Y., Du, D.-Z.: New constructions of one- and two-stage pooling designs. J. Comput. Biol. 15(2), 195\u2013205 (2008)","journal-title":"J. Comput. Biol."},{"key":"9754_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1007\/978-3-642-03409-1_7","volume-title":"Proceedings of the 17th International Symposium on Fundamentals of Computation Theory (FCT)","author":"M. Cheraghchi","year":"2009","unstructured":"Cheraghchi, M.: Noise-resilient group testing: limitations and constructions. In: Proceedings of the 17th International Symposium on Fundamentals of Computation Theory (FCT). Lecture Notes in Computer Science, vol. 5699, pp. 62\u201373 (2009)"},{"key":"9754_CR10","unstructured":"Cheraghchi, M.: Applications of derandomization theory in coding. Ph.D. Thesis, EPFL, Lausanne, Switzerland (2010). Available online at http:\/\/eccc.hpi-web.de\/static\/books\/Applications_of_Derandomization_Theory_in_Coding\/"},{"key":"9754_CR11","volume-title":"Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP)","author":"M. Cheraghchi","year":"2010","unstructured":"Cheraghchi, M.: Improved constructions for non-adaptive threshold group testing. In: Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP) (2010). arXiv:1002.2244v3 [cs.DM]"},{"key":"9754_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/978-3-540-75520-3_15","volume-title":"Proceedings of the 15th European Symposium on Algorithm (ESA)","author":"R. Clifford","year":"2007","unstructured":"Clifford, R., Efremenko, K., Porat, E., Rothschild, A.: k-mismatch with don\u2019t cares. In: Proceedings of the 15th European Symposium on Algorithm (ESA). Lecture Notes in Computer Science, vol. 4698, pp. 151\u2013162 (2007)"},{"issue":"1","key":"9754_CR13","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1145\/1061318.1061325","volume":"30","author":"G. Cormode","year":"2005","unstructured":"Cormode, G., Muthukrishnan, S.: What\u2019s hot and what\u2019s not: tracking most frequent items dynamically. ACM Trans. Database Syst. 30(1), 249\u2013278 (2005)","journal-title":"ACM Trans. Database Syst."},{"key":"9754_CR14","first-page":"198","volume-title":"Proceedings of Information Sciences and Systems","author":"G. Cormode","year":"2006","unstructured":"Cormode, G., Muthukrishnan, S.: Combinatorial algorithms for compressed sensing. In: Proceedings of Information Sciences and Systems, pp. 198\u2013201 (2006)"},{"key":"9754_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"707","DOI":"10.1007\/11889342_45","volume-title":"General Theory of Information Transfer and Combinatorics","author":"P. Damaschke","year":"2006","unstructured":"Damaschke, P.: Threshold group testing. In: General Theory of Information Transfer and Combinatorics. Lecture Notes in Computer Science, vol. 4123, pp. 707\u2013718. Springer, Berlin (2006)"},{"key":"9754_CR16","doi-asserted-by":"crossref","first-page":"436","DOI":"10.1214\/aoms\/1177731363","volume":"14","author":"R. Dorfman","year":"1943","unstructured":"Dorfman, R.: The detection of defective members of large populations. Ann. Math. Stat. 14, 436\u2013440 (1943)","journal-title":"Ann. Math. Stat."},{"key":"9754_CR17","volume-title":"Combinatorial Group Testing and Its Applications","author":"D.-Z. Du","year":"2000","unstructured":"Du, D.-Z., Hwang, F.: Combinatorial Group Testing and Its Applications, 2nd edn. World Scientific, Singapore (2000)","edition":"2"},{"key":"9754_CR18","volume-title":"Pooling Designs and Nonadaptive Group Testing","author":"D.-Z. Du","year":"2006","unstructured":"Du, D.-Z., Hwang, F.-K.: Pooling Designs and Nonadaptive Group Testing. World Scientific, Singapore (2006)"},{"key":"9754_CR19","first-page":"7","volume":"11","author":"A.G. D\u2019yachkov","year":"1982","unstructured":"D\u2019yachkov, A.G., Rykov, V.V.: Bounds of the length of disjunct codes. Probl. Control Inf. Theory 11, 7\u201313 (1982)","journal-title":"Probl. Control Inf. Theory"},{"issue":"4","key":"9754_CR20","first-page":"237","volume":"18","author":"A.G. D\u2019yachkov","year":"1989","unstructured":"D\u2019yachkov, A.G., Rykov, V.V., Rashad, A.M.: Superimposed distance codes. Probl. Control Inf. Theory 18(4), 237\u2013250 (1989)","journal-title":"Probl. Control Inf. Theory"},{"key":"9754_CR21","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/978-1-4757-6048-4_22","volume-title":"Numbers, Information and Complexity","author":"A.J. D\u2019yachkov","year":"2000","unstructured":"D\u2019yachkov, A.J., an Macula, A.G., Rykov, V.V.: New applications and results of superimposed code theory arising from the potentialities of molecular biology. In: Numbers, Information and Complexity, pp. 265\u2013282 (2000)"},{"issue":"1","key":"9754_CR22","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1109\/18.817530","volume":"46","author":"A.J. D\u2019yachkov","year":"2000","unstructured":"D\u2019yachkov, A.J., an Macula, A.G., Rykov, V.V.: New constructions of superimposed codes. IEEE Trans. Inf. Theory 46(1), 284\u2013290 (2000)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9754_CR23","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1006\/jcta.2002.3257","volume":"99","author":"A. D\u2019yachkov","year":"2002","unstructured":"D\u2019yachkov, A., Vilenkin, P., Macula, A., Torney, D.: Families of finite sets in which no intersection of \u2113 sets is covered by the union of s others. J. Comb. Theory, Ser. A 99, 195\u2013218 (2002)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"9754_CR24","first-page":"357","volume-title":"Proceedings of Compression and Complexity of Sequences","author":"M. Farach","year":"1997","unstructured":"Farach, M., Kannan, S., Knill, E., Muthukrishnan, S.: Group testing problems with sequences in experimental molecular biology. In: Proceedings of Compression and Complexity of Sequences, pp. 357\u2013367 (1997)"},{"key":"9754_CR25","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s10878-006-9634-z","volume":"12","author":"H. Gao","year":"2006","unstructured":"Gao, H., Hwang, F.K., Thai, M.T., Wu, W., Znati, T.: Construction of d(H)-disjunct matrix for group testing in hypergraphs. J. Comb. Optim. 12, 297\u2013301 (2006)","journal-title":"J. Comb. Optim."},{"key":"9754_CR26","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BF01884295","volume":"121","author":"A. Garcia","year":"1995","unstructured":"Garcia, A., Stichtenoth, H.: A tower of Artin-Schreier extensions of function fields attaining the Drinfeld-Vl\u0103du\u0163 bound. Invent. Math. 121, 211\u2013222 (1995)","journal-title":"Invent. Math."},{"key":"9754_CR27","volume-title":"Proceedings of the 22nd IEEE Conference on Computational Complexity (CCC)","author":"V. Guruswami","year":"2007","unstructured":"Guruswami, V., Umans, C., Vadhan, S.: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. In: Proceedings of the 22nd IEEE Conference on Computational Complexity (CCC) (2007)"},{"key":"9754_CR28","first-page":"3","volume-title":"Data Compression Conference","author":"E.-S. Hong","year":"2000","unstructured":"Hong, E.-S., Ladner, R.E.: Group testing for image compression. In: Data Compression Conference, pp. 3\u201312 (2000)"},{"key":"9754_CR29","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1109\/TIT.1964.1053689","volume":"10","author":"W.H. Kautz","year":"1964","unstructured":"Kautz, W.H., Singleton, R.C.: Nonrandom binary superimposed codes. IEEE Trans. Inf. Theory 10, 363\u2013377 (1964)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9754_CR30","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1002\/jcd.10056","volume":"12","author":"H.K. Kim","year":"2004","unstructured":"Kim, H.K., Lebedev, V.: On optimal superimposed codes. J. Comb. Des. 12, 79\u201391 (2004)","journal-title":"J. Comb. Des."},{"issue":"1","key":"9754_CR31","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/BF01609876","volume":"3","author":"A.J. Macula","year":"1999","unstructured":"Macula, A.J.: Probabilistic nonadaptive group testing in the presence of errors and DNA library screening. Ann. Comb. 3(1), 61\u201369 (1999)","journal-title":"Ann. Comb."},{"key":"9754_CR32","volume-title":"The Theory of Error-Correcting Codes","author":"F.J. MacWilliams","year":"1977","unstructured":"MacWilliams, F.J., Sloane, N.J.: The Theory of Error-Correcting Codes. North Holand, Amsterdam (1977)"},{"key":"9754_CR33","first-page":"171","volume-title":"DIMACS Series on Discrete Math. and Theoretical Computer Science","author":"H.-Q. Ngo","year":"2000","unstructured":"Ngo, H.-Q., Du, D.-Z.: A survey on combinatorial group testing algorithms with applications to DNA library screening. In: DIMACS Series on Discrete Math. and Theoretical Computer Science, vol. 55, pp. 171\u2013182 (2000)"},{"key":"9754_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1007\/978-3-540-70575-8_61","volume-title":"Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP)","author":"E. Porat","year":"2008","unstructured":"Porat, E., Rothschild, A.: Explicit non-adaptive combinatorial group testing schemes. In: Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 5125, pp. 748\u2013759 (2008)"},{"key":"9754_CR35","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1109\/SFCS.1997.646148","volume-title":"Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS)","author":"J. Radhakrishan","year":"1997","unstructured":"Radhakrishan, J., Ta-Shma, A.: Tight bounds for depth-two superconcentrators. In: Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 585\u2013594 (1997)"},{"key":"9754_CR36","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511808968","volume-title":"Introduction to Coding Theory","author":"R.M. Roth","year":"2006","unstructured":"Roth, R.M.: Introduction to Coding Theory. Cambridge University Press, Cambridge (2006)"},{"key":"9754_CR37","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/0097-3165(94)90067-1","volume":"66","author":"Ruszink\u00f3","year":"1994","unstructured":"Ruszink\u00f3: On the upper bound of the size of the r-cover-free families. J. Comb. Theory, Ser. A 66, 302\u2013310 (1994)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"9754_CR38","volume-title":"Proceedings of Computational Systems Bioinformatics","author":"A. Schliep","year":"2003","unstructured":"Schliep, A., Torney, D., Rahmann, S.: Group testing with DNA chips: Generating designs and decoding experiments. In: Proceedings of Computational Systems Bioinformatics (2003)"},{"key":"9754_CR39","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1016\/S0012-365X(03)00287-5","volume":"279","author":"D.R. Stinson","year":"2004","unstructured":"Stinson, D.R., Wei, R.: Generalized cover-free families. Discrete Math. 279, 463\u2013477 (2004)","journal-title":"Discrete Math."},{"key":"9754_CR40","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1006\/jcta.1999.3036","volume":"90","author":"D.R. Stinson","year":"2000","unstructured":"Stinson, D.R., Wei, R., Zhu, L.: Some new bounds for cover-free families. J. Comb. Theory, Ser. A 90, 224\u2013234 (2000)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"9754_CR41","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1002\/mana.19821090103","volume":"109","author":"M.A. Tsfasman","year":"1982","unstructured":"Tsfasman, M.A., Vl\u0103du\u0163, S.G., Zink, Th.: Modular curves, Shimura curves, and Goppa codes better than the Varshamov-Gilbert bound. Math. Nachr. 109, 21\u201328 (1982)","journal-title":"Math. Nachr."},{"key":"9754_CR42","series-title":"Graduate Texts in Mathematics","first-page":"86","volume-title":"Introduction to Coding Theory","author":"J.H. Lint van","year":"1998","unstructured":"van Lint, J.H.: Introduction to Coding Theory, 3rd edn. Graduate Texts in Mathematics, p. 86. Springer, Berlin (1998)","edition":"3"},{"key":"9754_CR43","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1109\/TIT.1985.1057026","volume":"31","author":"J. Wolf","year":"1985","unstructured":"Wolf, J.: Born-again group testing: multiaccess communications. IEEE Trans. Inf. Theory 31, 185\u2013191 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"12","key":"9754_CR44","doi-asserted-by":"crossref","first-page":"1753","DOI":"10.1016\/j.dam.2006.02.006","volume":"154","author":"W. Wu","year":"2006","unstructured":"Wu, W., Huang, Y., Huang, X., Li, Y.: On error-tolerant DNA screening. Discrete Appl. Math. 154(12), 1753\u20131758 (2006)","journal-title":"Discrete Appl. Math."},{"key":"9754_CR45","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/978-0-387-69319-4_8","volume":"7","author":"W. Wu","year":"2008","unstructured":"Wu, W., Li, Y., Huang, C.H., Du, D.Z.: Molecular biology and pooling design. Data Min. Biomed. 7, 133\u2013139 (2008)","journal-title":"Data Min. Biomed."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9754-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9754-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9754-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:11Z","timestamp":1559123111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9754-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2,12]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["9754"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9754-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2,12]]}}}