×

Superimposed codes and threshold group testing. (English) Zbl 1309.94185

Aydinian, Harout (ed.) et al., Information theory, combinatorics, and search theory. In memory of Rudolf Ahlswede. Berlin: Springer (ISBN 978-3-642-36898-1/pbk). Lecture Notes in Computer Science 7777, 509-533 (2013).
Summary: We discuss superimposed codes and non-adaptive group testing designs arising from the potentialities of compressed genotyping models in molecular biology. The given paper was motivated by the 30th anniversary of the D’yachkov-Rykov recurrent upper bound on the rate of superimposed codes published in 1982 [Probl. Peredachi Inf. 18, No. 3, 7–13 (1982; Zbl 0507.94013)]. We were also inspired by recent results obtained for non-adaptive threshold group testing which develop the theory of superimposed codes.
For the entire collection see [Zbl 1259.94005].

MSC:

94B60 Other types of codes
92B15 General biostatistics
94A15 Information theory (general)
94C12 Fault detection; testing in circuits and networks

Citations:

Zbl 0507.94013
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahlswede, R., Deppe, C., Lebedev, V.: Bounds for threshold and majority group testing. In: 2011 IEEE International Symposium on Information Theory, Sankt-Peterburg, pp. 69–73 (2011) · Zbl 1377.68222 · doi:10.1109/ISIT.2011.6034222
[2] Ahlswede, R., Wegener, I.: Suchprobleme, Teubner (1979), MIR russ. edition (1981), Wiley engl. edition (1987) · doi:10.1007/978-3-322-91203-9
[3] Chen, H.B., Fu, H.L.: Nonadaptive algorithms for threshold group testing. Discrete Applied Mathematics 157, 1581–1585 (2009) · Zbl 1186.68436 · doi:10.1016/j.dam.2008.06.003
[4] Cheraghchi, M.: Improved constructions for non-adaptive threshold group testing. In: Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), arXiv:1002.2244 (2010) · Zbl 1288.68107
[5] Copperersmith, D., Shearer, J.: New bounds for union-free families of sets. The Electronic Journal of Combinatorics 5(1), R39 (1998)
[6] Csizár, I., Körner, J.: Information Theory: Coding Theorems for Discrete Memoryless Systems. Academiai Kiado, Budapest (1981) · Zbl 0568.94012
[7] Damaschke, P.: Threshold group testing. In: General Theory of Information Transfer and Combinatorics, pp. 707–718. Kluwer Academic Publishers (2006) · Zbl 1158.68490 · doi:10.1007/11889342_45
[8] De Bonis, A., Vaccaro, U.: Optimal algorithms for group testing problems, and new bounds on generalized superimposed codes. IEEE Trans. Inf. Theory 52(10), 4673–4680 (2006) · Zbl 1320.94056 · doi:10.1109/TIT.2006.881740
[9] Dorfman, R.: The detection of defective members of large populations. The Annals of Mathematical Statistics 14(4), 436–440 (1943) · doi:10.1214/aoms/1177731363
[10] D’yachkov, A.G.: Superimposed designs and codes for non-adaptive search of mutually obscuring defectives. In: 2003 IEEE International Symposium on Information Theory, Yokohama, p. 134 (2003) · doi:10.1109/ISIT.2003.1228148
[11] D’yachkov, A.G.: Lectures on Designing Screening Experiments. Lecture Note Series 10, Monograph, p. 112, Combinatorial and Computational Mathematics Center, Pohang University of Science and Technology (POSTECH) (February 2004)
[12] D’yachkov, A.G., Macula, A.J., Torney, D.C., Vilenkin, P.A.: Two models of non-adaptive group testing for designing screening experiments. In: Advances in Model Oriented Design and Analysis: Proceedings of the 6th International Workshop on Model Oriented Design and Analysis, Puchberg/Schneeberg, Austria, June 25-29, pp. 63–75. Physica-Verlag, Heidelberg (2001)
[13] D’yachkov, A., Macula, A., Torney, D., Vilenkin, P.: Families of finite sets in which no intersection of ł sets is covered by the union of s others. Journal of Combinatorial Theory, Series A 99, 195–218 (2002) · Zbl 1020.94027 · doi:10.1006/jcta.2002.3257
[14] D’yachkov, A.G., Macula, A.J., 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–282. Kluwer Academic Publishers (2000) · Zbl 1034.94015 · doi:10.1007/978-1-4757-6048-4_22
[15] D’yachkov, A.G., Macula, A.J., Rykov, V.V.: New constructions of superimposed codes. IEEE Trans. Inf. Theory 46(1), 284–290 (2000) · Zbl 0999.94044 · doi:10.1109/18.817530
[16] D’yachkov, A.G., Rashad, A.M.: Universal decoding for random design of screening experiments. Microelectronics and Reliability 29(6), 965–971 (1989) · doi:10.1016/0026-2714(89)90022-X
[17] D’yachkov, A.G., Rykov, V.V.: Bounds on the length of disjunct codes. Problemy Peredachi Informatsii 18(3), 7–13 (1982) (in Russian)
[18] D’yachkov, A.G., Rykov, V.V.: A survey of superimposed code theory. Problems of Control and Inf. Theory 12(4), 229–242 (1983)
[19] D’yachkov, A.G., Rykov, V.V.: Generalized superimposed codes and their application to random multiple access. In: Proc. of the 6th International Symposium on Information Theory, Part 1, Taschkent (1984)
[20] D’yachkov, A.G., Rykov, V.V.: On a model of associative memory. Problemy Peredachi Inform 24(3), 107–110 (1988) (in Russian) · Zbl 0663.68093
[21] D’yachkov, A.G., Rykov, V.V., Rashad, A.M.: Superimposed distance codes. Problems of Control and Inform. Theory 18(4), 237–250 (1989)
[22] D’yachkov, A.G., Rykov, V.V.: The capacity of the boolean associative memory. In: Proc. of the 5th International Conference on Artificial Neural Networks, Churchill Colledge, Cambridge, UK, pp. 158–160 (1997) · doi:10.1049/cp:19970719
[23] D’yachkov, A.G., Rykov, V.V.: Optimal superimposed codes and designs for Rényi’s search model. Journal of Statistical Planning and Inference 100, 281–302 (2002) · Zbl 0998.94043 · doi:10.1016/S0378-3758(01)00140-9
[24] D’yachkov, A.G., Vilenkin, P.A., Yekhanin, S.M.: Upper bounds on the rate of superimposed (s,)-codes, based on Engel’s inequality. In: Proceedings of the 8th International Workshop Algebraic and Combinatorial Coding Theory, Tsarskoe Selo, Russia, pp. 95–99 (2002)
[25] Du, D.-Z., Hwang, F.K.: Combinatorial group testing and its applications. World Scientific, Singapore (1993) · Zbl 0867.90060 · doi:10.1142/1936
[26] Emad, A., Milenkovic, O.: Semi-quantitative group testing. Arxiv-1202.2887 (2011) · Zbl 1359.94845
[27] Erlich, Y., Gordon, A., Brand, M., Hannon, G., Mitra, P.: Compressed genotyping. IEEE Trans. Inf. Theory 56(2), 706–723 (2010) · Zbl 1366.92078 · doi:10.1109/TIT.2009.2037043
[28] Kautz, W.H., Singleton, R.C.: Nonrandom Binary Superimposed Codes. IEEE Trans. Inf. Theory 10(4), 363–377 (1964) · Zbl 0133.12402 · doi:10.1109/TIT.1964.1053689
[29] Kim, H., Lebedev, V.S.: On the optimality of trivial (w,r) cover-free codes. Probl. Inf. Transm. 40(3), 195–201 (2004) · Zbl 1088.94028 · doi:10.1023/B:PRIT.0000044255.42299.4f
[30] Kim, H., Lebedev, V.S.: On optimal superimposed codes. Journal of Combinatorial Designs 12(2), 79–91 (2004) · Zbl 1051.94013 · doi:10.1002/jcd.10056
[31] Lebedev, V.S.: An asymptotic upper bound on the rate of (w,r)-cover-free codes. Probl. Inf. Transm. 39(4), 317–323 (2003) · Zbl 1096.94534 · doi:10.1023/B:PRIT.0000011270.09033.8f
[32] Lebedev, V.S.: Some tables for (w, r) superimposed codes. In: Proceedings of the 8th International Workshop, Algebraic and Combinatorial Coding Theory, Tsarskoe Selo, Russia, pp. 185–189 (2002)
[33] Lebedev, V.S.: Separating codes and a new combinatorial search model. Probl. Inf. Transm. 46(1), 1–6 (2010) · Zbl 1241.94040 · doi:10.1134/S0032946010010011
[34] MacWilliams, F.J., Sloane, N.J.A.: The theory of error-correcting codes. North Holland (1977) · Zbl 0369.94008
[35] Maljutov, M.B.: On planning screening experiments. In: Proceedings of the IEEE-USSR Joint Workshop on Information Theory, pp. 144–147. Inst. Electr. Electron. Engrs., New York (1976)
[36] Maljutov, M.B., Mateev, P.S.: The design of screening experiments with a nonsymmetric response function. Dokl. Akad. Nauk SSSR 244(1), 42–46 (1979)
[37] Maljutov, M.B., Mateev, P.S.: Design of screening experiments with a nonsymmetric response function. Mat. Zametki 27(1), 109–127 (1980) · Zbl 0449.62002
[38] Nguyen Quang, A., Zeisel, T.: Bounds on constant weight binary syperimposed codes. Probl. of Control and Inform. Theory 17(4), 223–230 (1988) · Zbl 0652.94021
[39] Rashad, A.M.: Random coding bounds on the rate for list-decoding superimposed codes. Problems of Control and Inform. Theory 19(2), 141–149 (1990) · Zbl 0707.94025
[40] Rényi, A.: On a problem of information theory. MTA Mat. Kut. Int. Kozl., 6B, 505–516 (1961) · Zbl 0126.35605
[41] Shannon, C.E.: A mathematical theory of communication. Bell System Technical Journal 27, 379–423 & 623–656 (1948) · Zbl 1154.94303
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.