{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T20:35:23Z","timestamp":1754598923929,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T00:00:00Z","timestamp":1656028800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T00:00:00Z","timestamp":1656028800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2022,8]]},"DOI":"10.1007\/s10623-022-01073-9","type":"journal-article","created":{"date-parts":[[2022,6,24]],"date-time":"2022-06-24T15:07:47Z","timestamp":1656083267000},"page":"1721-1734","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Modular Subset-Sum Problem and the size of deletion correcting codes"],"prefix":"10.1007","volume":"90","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3301-0232","authenticated-orcid":false,"given":"Khodakhast","family":"Bibak","sequence":"first","affiliation":[]},{"given":"Behrouz","family":"Zolfaghari","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,24]]},"reference":[{"key":"1073_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai M.: Generating hard instances of lattice problems (extended abstract), In: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing (STOC 1996), pp. 99\u2013108 (1996).","DOI":"10.1145\/237814.237838"},{"key":"1073_CR2","doi-asserted-by":"crossref","unstructured":"AlAziz Md.M., Alhadidi D., Mohammed N.: Secure approximation of edit distance on genomic data. BMC Med. Genom. 10, Article Number: 41 (2017).","DOI":"10.1186\/s12920-017-0279-9"},{"key":"1073_CR3","doi-asserted-by":"crossref","unstructured":"Axiotis K., Backurs A., Jin C., Tzamos C., Wu H.: Fast modular subset sum using linear sketching. In: Proceedings of the thirtieth annual ACM-SIAM symposium on discrete algorithms (SODA 2019), pp. 58\u201369 (2019).","DOI":"10.1137\/1.9781611975482.4"},{"key":"1073_CR4","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1016\/j.ejc.2013.05.009","volume":"34","author":"E Balandraud","year":"2013","unstructured":"Balandraud E., Girard B., Griffiths S., Hamidoune Y.: Subset sums in abelian groups. Eur. J. Combin. 34, 1269\u20131286 (2013).","journal-title":"Eur. J. Combin."},{"key":"1073_CR5","doi-asserted-by":"crossref","unstructured":"Bansal N., Garg S., Nederlof J., Vyas N.: Faster space-efficient algorithms for subset sum, $$k$$-sum, and related problems. SIAM J. Comput. 47, 1755\u20131777 (2018).","DOI":"10.1137\/17M1158203"},{"key":"1073_CR6","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1002\/nav.3800030107","volume":"3","author":"R Bellman","year":"1956","unstructured":"Bellman R.: Notes on the theory of dynamic programming IV-Maximization over discrete sets. Naval Res. Logist. Q. 3, 67\u201370 (1956).","journal-title":"Naval Res. Logist. Q."},{"key":"1073_CR7","doi-asserted-by":"publisher","first-page":"2387","DOI":"10.1007\/s10623-020-00787-y","volume":"88","author":"K Bibak","year":"2020","unstructured":"Bibak K.: Deletion correcting codes meet the Littlewood\u2013Offord problem. Des. Codes Cryptogr. 88, 2387\u20132396 (2020).","journal-title":"Des. Codes Cryptogr."},{"key":"1073_CR8","doi-asserted-by":"publisher","first-page":"1809","DOI":"10.1109\/TCOMM.2018.2886354","volume":"67","author":"K Bibak","year":"2019","unstructured":"Bibak K., Milenkovic O.: Explicit formulas for the weight enumerators of some classes of deletion correcting codes. IEEE Trans. Commun. 67, 1809\u20131816 (2019).","journal-title":"IEEE Trans. Commun."},{"key":"1073_CR9","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1016\/j.nuclphysb.2016.07.028","volume":"910","author":"K Bibak","year":"2016","unstructured":"Bibak K., Kapron B.M., Srinivasan V.: Counting surface-kernel epimorphisms from a co-compact Fuchsian group to a cyclic group with motivations from string theory and QFT. Nucl. Phys. B 910, 712\u2013723 (2016).","journal-title":"Nucl. Phys. B"},{"key":"1073_CR10","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1016\/j.jnt.2016.07.018","volume":"171","author":"K Bibak","year":"2017","unstructured":"Bibak K., Kapron B.M., Srinivasan V., Tauraso R., T\u00f3th L.: Restricted linear congruences. J. Number Theory 171, 128\u2013144 (2017).","journal-title":"J. Number Theory"},{"key":"1073_CR11","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1142\/S0129054118500089","volume":"29","author":"K Bibak","year":"2018","unstructured":"Bibak K., Kapron B.M., Srinivasan V., T\u00f3th L.: On an almost-universal hash function family with applications to authentication and secrecy codes. Int. J. Found. Comput. Sci. 29, 357\u2013375 (2018).","journal-title":"Int. J. Found. Comput. Sci."},{"key":"1073_CR12","doi-asserted-by":"publisher","first-page":"1893","DOI":"10.1007\/s10623-017-0428-3","volume":"86","author":"K Bibak","year":"2018","unstructured":"Bibak K., Kapron B.M., Srinivasan V.: Unweighted linear congruences with distinct coordinates and the Varshamov\u2013Tenengolts codes. Des. Codes Cryptogr. 86, 1893\u20131904 (2018).","journal-title":"Des. Codes Cryptogr."},{"key":"1073_CR13","doi-asserted-by":"publisher","first-page":"3438","DOI":"10.1109\/TIT.2021.3049627","volume":"67","author":"K Cai","year":"2021","unstructured":"Cai K., Chee Y.M., Gabrys R., Kiah H.M., Nguyen T.T.: Correcting a single indel\/edit for DNA-based data storage: linear-time encoders and order-optimality. IEEE Trans. Inf. Theory 67, 3438\u20133451 (2021).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1073_CR14","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1109\/TIT.2021.3122798","volume":"68","author":"K Cai","year":"2022","unstructured":"Cai K., Kiah H.M., Nguyen T.T., Yaakob E.: Coding for sequence reconstruction for single edits. IEEE Trans. Inf. Theory 68, 66\u201379 (2022).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1073_CR15","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1016\/S0019-9958(81)90645-8","volume":"48","author":"Ph Delsarte","year":"1981","unstructured":"Delsarte Ph., Piret Ph.: Spectral enumerators for certain additive-error-correcting codes over integer alphabets. Inf. Contr. 48, 193\u2013210 (1981).","journal-title":"Inf. Contr."},{"key":"1073_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"R Durbin","year":"1998","unstructured":"Durbin R., Eddy S.R., Krogh A., Mitchison G.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge (1998)."},{"key":"1073_CR17","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/s11139-013-9478-y","volume":"35","author":"CF Fowler","year":"2014","unstructured":"Fowler C.F., Garcia S.R., Karaali G.: Ramanujan sums as supercharacters. Ramanujan J. 35, 205\u2013241 (2014).","journal-title":"Ramanujan J."},{"key":"1073_CR18","doi-asserted-by":"publisher","first-page":"2550","DOI":"10.1109\/TIT.2017.2778143","volume":"64","author":"R Gabrys","year":"2018","unstructured":"Gabrys R., Yaakobi E., Milenkovic O.: Codes in the Damerau distance for deletion and adjacent transposition correction. IEEE Trans. Inf. Theory 64, 2550\u20132570 (2018).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1073_CR19","unstructured":"Gabrys R., Guruswami V., Ribeiro J.L., Wu K.: Beyond single-deletion correcting codes: substitutions and transpositions. arXiv: 2112.09971 (2021)."},{"key":"1073_CR20","first-page":"249","volume":"19","author":"BD Ginzburg","year":"1967","unstructured":"Ginzburg B.D.: A certain number-theoretic function which has an application in coding theory (Russian). Problemy Kibernet. 19, 249\u2013252 (1967).","journal-title":"Problemy Kibernet."},{"key":"1073_CR21","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1109\/18.971760","volume":"48","author":"ASJ Helberg","year":"2002","unstructured":"Helberg A.S.J., Ferreira H.C.: On multiple insertion\/deletion correcting codes. IEEE Trans. Inf. Theory 48, 305\u2013308 (2002).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1073_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(81)90432-0","volume":"49","author":"T Helleseth","year":"1981","unstructured":"Helleseth T., Kl\u00f8ve T.: On group-theoretic codes for asymmetric channels. Inf. Control. 49, 1\u20139 (1981).","journal-title":"Inf. Control."},{"key":"1073_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-642-13190-5_12","volume-title":"Advances in Cryptology (EUROCRYPT 2010)","author":"N Howgrave-Graham","year":"2010","unstructured":"Howgrave-Graham N., Joux A.: New generic algorithms for hard knapsacks. In: Gilbert H. (ed.) Advances in Cryptology (EUROCRYPT 2010), vol. 6110, pp. 235\u2013256. Lecture Notes in Computer Science. Springer, Berlin (2010)."},{"key":"1073_CR24","volume-title":"An Introduction to Bioinformatics Algorithms","author":"NC Jones","year":"2004","unstructured":"Jones N.C., Pevzner P.A.: An Introduction to Bioinformatics Algorithms. MIT Press, Cambridge (2004)."},{"key":"1073_CR25","unstructured":"Jurafsky D., Martin J.H.: Speech and Language Processing: An Introduction to Natural Language Processing, Computational Linguistics, and Speech Recognition, third edition draft (2018)."},{"key":"1073_CR26","series-title":"The IBM Research Symposia Series","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"RM Karp","year":"1972","unstructured":"Karp R.M.: Reducibility among combinatorial problems. In: Miller R.E., Thatcher J.W., Bohlinger J.D. (eds.) Complexity of Computer Computations, pp. 85\u2013103. The IBM Research Symposia Series. Springer, Boston (1972)."},{"key":"1073_CR27","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer H., Pferschy U., Pisinger D.: Knapsack Problems. Springer, Berlin (2004)."},{"key":"1073_CR28","doi-asserted-by":"crossref","unstructured":"Kl\u00f8ve T.: Error correcting codes for the asymmetric channel. Department of Informatics, University of Bergen, Norway, Technical Report (1995).","DOI":"10.1007\/978-1-4615-2309-3_1"},{"key":"1073_CR29","unstructured":"Kluyver J.C.: Some formulae concerning the integers less than $$n$$ and prime to $$n$$. Proc. R. Neth. Acad. Arts Sci. (KNAW) 9, 408\u2013414 (1906)."},{"key":"1073_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3329863","volume":"15","author":"K Koiliaris","year":"2019","unstructured":"Koiliaris K., Xu C.: Faster pseudopolynomial time algorithms for subset sum. ACM Trans. Algorithms 15, 1\u201320 (2019).","journal-title":"ACM Trans. Algorithms"},{"key":"1073_CR31","doi-asserted-by":"publisher","first-page":"2682","DOI":"10.1109\/TIT.2016.2541139","volume":"62","author":"TA Le","year":"2016","unstructured":"Le T.A., Nguyen H.D.: New multiple insertion\/deletion correcting codes for non-binary alphabets. IEEE Trans. Inf. Theory 62, 2682\u20132693 (2016).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1073_CR32","unstructured":"Levenshtein V.I.: Binary codes capable of correcting deletions, insertions, and reversals (in Russian), Dokl. Akad. Nauk SSSR 163, 845\u2013848. English translation in Soviet Physics Dokl. 10 (1966), 707\u2013710 (1965)."},{"key":"1073_CR33","doi-asserted-by":"crossref","unstructured":"Lyubashevsky V., Palacio A., Segev G.: Public-key cryptographic primitives provably as secure as subset sum, Theory of Cryptography Conference (TCC 2010), Lecture Notes in Computer Science, vol 5978. Springer, Berlin, pp. 382\u2013400 (2010).","DOI":"10.1007\/978-3-642-11799-2_23"},{"key":"1073_CR34","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809071","volume-title":"Introduction to Information Retrieval","author":"CD Manning","year":"2008","unstructured":"Manning C.D., Raghavan P., Sch\u00fctze H.: Introduction to Information Retrieval. Cambridge University Press, Cambridge (2008)."},{"key":"1073_CR35","volume-title":"Knapsack Problems: Algorithms and Computer Implementations","author":"S Martello","year":"1990","unstructured":"Martello S., Toth P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester (1990)."},{"key":"1073_CR36","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/S0019-9958(80)90082-0","volume":"44","author":"RJ McEliece","year":"1980","unstructured":"McEliece R.J., Rodemich E.R.: The Constantin-Rao construction for binary asymmetric error-correcting codes. Inf. Control. 44, 187\u2013196 (1980).","journal-title":"Inf. Control."},{"key":"1073_CR37","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1109\/SURV.2010.020110.00079","volume":"12","author":"H Mercier","year":"2010","unstructured":"Mercier H., Bhargava V.K., Tarokh V.: A survey of error-correcting codes for channels with symbol synchronization errors. IEEE Commun. Surv. Tutor. 12, 87\u201396 (2010).","journal-title":"IEEE Commun. Surv. Tutor."},{"key":"1073_CR38","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s00037-007-0234-9","volume":"16","author":"D Micciancio","year":"2007","unstructured":"Micciancio D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions. Comput. Complex. 16, 365\u2013411 (2007).","journal-title":"Comput. Complex."},{"key":"1073_CR39","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1214\/08-PS141","volume":"6","author":"M Mitzenmacher","year":"2009","unstructured":"Mitzenmacher M.: A survey of results for deletion channels and related synchronization channels. Probab. Surv. 6, 1\u201333 (2009).","journal-title":"Probab. Surv."},{"key":"1073_CR40","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G Navarro","year":"2001","unstructured":"Navarro G.: A guided tour to approximate string matching. ACM Comput. Surv. 33, 31\u201388 (2001).","journal-title":"ACM Comput. Surv."},{"key":"1073_CR41","doi-asserted-by":"crossref","unstructured":"Olson J.: An addition theorem modulo $$p$$. J. Combin. Theory 5, 45\u201352 (1968).","DOI":"10.1016\/S0021-9800(68)80027-4"},{"key":"1073_CR42","first-page":"259","volume":"22","author":"S Ramanujan","year":"1918","unstructured":"Ramanujan S.: On certain trigonometric sums and their applications in the theory of numbers. Trans. Camb. Philos. Soc. 22, 259\u2013276 (1918).","journal-title":"Trans. Camb. Philos. Soc."},{"key":"1073_CR43","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1109\/TIT.2013.2279674","volume":"60","author":"SM Sadegh Tabatabaei Yazdi","year":"2014","unstructured":"Sadegh Tabatabaei Yazdi S.M., Dolecek L.: A deterministic polynomial-time protocol for synchronizing from deletions. IEEE Trans. Inf. Theory 60, 397\u2013409 (2014).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1073_CR44","doi-asserted-by":"publisher","first-page":"1971","DOI":"10.1109\/TIT.2017.2661747","volume":"63","author":"C Schoeny","year":"2017","unstructured":"Schoeny C., Wachter-Zeh A., Gabrys R., Yaakobi E.: Codes correcting a burst of deletions or insertions. IEEE Trans. Inf. Theory 63, 1971\u20131985 (2017).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1073_CR45","first-page":"273","volume-title":"Codes and Designs, Ohio State University, May 2000 (Ray-Chaudhuri Festschrift)","author":"NJA Sloane","year":"2002","unstructured":"Sloane N.J.A.: On single-deletion-correcting codes. In: Arasu K.T., Seress A. (eds.) Codes and Designs, Ohio State University, May 2000 (Ray-Chaudhuri Festschrift), pp. 273\u2013291. Walter de Gruyter, Berlin (2002)."},{"key":"1073_CR46","volume-title":"Enumerative Combinatorics","author":"RP Stanley","year":"2012","unstructured":"Stanley R.P.: Enumerative Combinatorics. Cambridge University Press, Cambridge (2012)."},{"key":"1073_CR47","unstructured":"Stanley R.P., Yoder M.F.: A study of Varshamov codes for asymmetric channels, Jet Propulsion Laboratory, Technical Report 32-1526, Vol. XIV , 117\u2013123 (1973)."},{"key":"1073_CR48","doi-asserted-by":"publisher","first-page":"1737","DOI":"10.1007\/s10208-016-9326-8","volume":"16","author":"E Szemer\u00e9di","year":"2016","unstructured":"Szemer\u00e9di E.: Structural approach to subset sum problems. Found. Comput. Math. 16, 1737\u20131749 (2016).","journal-title":"Found. Comput. Math."},{"key":"1073_CR49","unstructured":"Varshamov R.R., Tenengolts G.M.: A code which corrects single asymmetric errors (in Russian), Avtomat. iTelemeh. 26, 288\u2013292. English translation in Automat. Remote Control 26, 286\u2013290 (1965)."},{"key":"1073_CR50","doi-asserted-by":"publisher","first-page":"5670","DOI":"10.1109\/TIT.2015.2466635","volume":"61","author":"R Venkataramanan","year":"2015","unstructured":"Venkataramanan R., Swamy V.N., Ramchandran K.: Low-complexity interactive algorithms for synchronization from deletions, insertions, and substitutions. IEEE Trans. Inf. Theory 61, 5670\u20135689 (2015).","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01073-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-022-01073-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-022-01073-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,30]],"date-time":"2022-07-30T19:26:28Z","timestamp":1659209188000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-022-01073-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,24]]},"references-count":50,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["1073"],"URL":"https:\/\/doi.org\/10.1007\/s10623-022-01073-9","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"type":"print","value":"0925-1022"},{"type":"electronic","value":"1573-7586"}],"subject":[],"published":{"date-parts":[[2022,6,24]]},"assertion":[{"value":"21 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 June 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 June 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}