{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,24]],"date-time":"2025-06-24T06:30:18Z","timestamp":1750746618223,"version":"3.41.0"},"reference-count":74,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,11,11]],"date-time":"2024-11-11T00:00:00Z","timestamp":1731283200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"European Research Council","award":["810115-DYNASNET"],"award-info":[{"award-number":["810115-DYNASNET"]}]},{"DOI":"10.13039\/501100001381","name":"National Research Foundation Singapore","doi-asserted-by":"crossref","award":["NRF2021-QEP2-02-P05"],"award-info":[{"award-number":["NRF2021-QEP2-02-P05"]}],"id":[{"id":"10.13039\/501100001381","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>\n            We prove a hypercontractive inequality for matrix-valued functions defined over large alphabets. In order to do so, we prove a generalization of the powerful 2-uniform convexity inequality for trace norms of Ball, Carlen, Lieb\u00a0(Inventiones Mathematicae\u201994). Using our hypercontractive\u00a0inequality, we present upper and lower bounds for the communication complexity of the Hidden Hypermatching problem defined over large alphabets. We then consider streaming algorithms for approximating the value of Unique Games on a hypergraph with\n            <jats:italic>t<\/jats:italic>\n            -size hyperedges. By using our communication lower bound, we show that every streaming algorithm in the adversarial model achieving an\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\((r-\\varepsilon)\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -approximation of this value requires\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\Omega (n^{1-2\/t})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            quantum space, where\n            <jats:italic>r<\/jats:italic>\n            is the alphabet size. We next present a lower bound for locally decodable codes (\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {LDC}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            )\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {Z}_r^n\\rightarrow \\mathbb {Z}_r^N\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            over large alphabets with recoverability probability at least\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(1\/r + \\varepsilon\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . Using hypercontractivity, we give an exponential lower bound\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(N= 2^{\\Omega (\\varepsilon ^4 n\/r^4)}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            for 2-query (possibly non-linear)\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {LDC}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            s over\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathbb {Z}_r\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            and using the non-commutative Khintchine inequality we prove an improved lower bound of\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(N= 2^{\\Omega (\\varepsilon ^2 n\/r^2)}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            .\n          <\/jats:p>","DOI":"10.1145\/3688824","type":"journal-article","created":{"date-parts":[[2024,8,27]],"date-time":"2024-08-27T10:15:10Z","timestamp":1724753710000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6014-6624","authenticated-orcid":false,"given":"Srinivasan","family":"Arunachalam","sequence":"first","affiliation":[{"name":"IBM, Yorktown Heights, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8265-7334","authenticated-orcid":false,"given":"Joao F.","family":"Doriguello","sequence":"additional","affiliation":[{"name":"Alfr\u00e9d R\u00e9nyi Institute of Mathematics, Budapest, Hungary"},{"name":"Centre for Quantum Technologies, National University of Singapore, Singapore Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,11]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","unstructured":"Scott Aaronson. 2018. PDQP\/qpoly=All. arXiv preprint arXiv:1805.08577 (2018). DOI:10.48550\/arXiv.1805.08577","DOI":"10.48550\/arXiv.1805.08577"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213560"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","unstructured":"Noga Alon Yossi Matias and Mario Szegedy. 1999. The space complexity of approximating the frequency moments. J. Comput. System Sci. 58 1 (1999) 137\u2013147. DOI:10.1006\/jcss.1997.1545","DOI":"10.1006\/jcss.1997.1545"},{"key":"e_1_3_4_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.19"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","unstructured":"Keith Ball Eric A. Carlen and Elliott H. Lieb. 1994. Sharp uniform convexity and smoothness inequalities for trace norms. Inventiones Mathematicae 115 1 (01 Dec.1994) 463\u2013482. DOI:10.1007\/BF01231769","DOI":"10.1007\/BF01231769"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007379"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","unstructured":"Robert Beals Harry Buhrman Richard Cleve Michele Mosca and Ronald de Wolf. 2001. Quantum lower bounds by polynomials. J. ACM 48 4 (Jul.2001) 778\u2013797. DOI:10.1145\/502090.502097","DOI":"10.1145\/502090.502097"},{"key":"e_1_3_4_9_2","doi-asserted-by":"crossref","unstructured":"William Beckner. 1975. Inequalities in Fourier analysis. Annals of Mathematics 102 1 (1975) 159\u2013182. DOI:http:\/\/www.jstor.org\/stable\/1970980","DOI":"10.2307\/1970980"},{"key":"e_1_3_4_10_2","doi-asserted-by":"publisher","unstructured":"Richard Beigel Lance Fortnow and William Gasarch. 2006. A tight lower bound for restricted PIR protocols. Computational Complexity 15 1 (01 May2006) 82\u201391. DOI:10.1007\/s00037-006-0208-3","DOI":"10.1007\/s00037-006-0208-3"},{"key":"e_1_3_4_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.45"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.28"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","unstructured":"Aline Bonami. 1970. \u00c9tude des coefficients de Fourier des fonctions de \\(L^p(G)\\) . Annales de l\u2019Institut Fourier 20 2 (1970) 335\u2013402. DOI:10.5802\/aif.357","DOI":"10.5802\/aif.357"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.20"},{"key":"e_1_3_4_15_2","doi-asserted-by":"publisher","unstructured":"Eric A. Carlen and Elliott H. Lieb. 1993. Optimal hypercontractivity for Fermi fields and related non-commutative integration inequalities. Communications in Mathematical Physics 155 1 (01 Jul.1993) 27\u201346. DOI:10.1007\/BF02100048","DOI":"10.1007\/BF02100048"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","unstructured":"Victoria M. Chayes. 2020. Matrix rearrangement inequalities revisited. arXiv preprint arXiv:2009.04032 (2020). DOI:10.48550\/arXiv.2009.04032","DOI":"10.48550\/arXiv.2009.04032"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451038"},{"key":"e_1_3_4_18_2","first-page":"203","volume-title":"27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010 (Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science)","author":"Chen Victor","year":"2010","unstructured":"Victor Chen, Elena Grigorescu, and Ronald de Wolf. 2010. Efficient and error-correcting data structures for membership and polynomial evaluation. In 27th International Symposium on Theoretical Aspects of Computer Science - STACS 2010 (Proceedings of the 27th Annual Symposium on the Theoretical Aspects of Computer Science), Jean-Yves Marion and Thomas Schwentick (Eds.). Inria Nancy Grand Est & Loria, Nancy, France, 203\u2013214. DOI:https:\/\/inria.hal.science\/inria-00455571"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","unstructured":"Benny Chor Eyal Kushilevitz Oded Goldreich and Madhu Sudan. 1998. Private information retrieval. J. ACM 45 6 (nov1998) 965\u2013981. DOI:10.1145\/293347.293350","DOI":"10.1145\/293347.293350"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519983"},{"key":"e_1_3_4_21_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00117"},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00039"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","unstructured":"William J. Davis D. J. H. Garling and Nicole Tomczak-Jaegermann. 1984. The complex convexity of quasi-normed linear spaces. Journal of Functional Analysis 55 1 (1984) 110\u2013150. DOI:10.1016\/0022-1236(84)90021-1","DOI":"10.1016\/0022-1236(84)90021-1"},{"key":"e_1_3_4_24_2","doi-asserted-by":"crossref","unstructured":"Irit Dinur and Samuel Safra. 2005. On the hardness of approximating minimum vertex cover. Annals of Mathematics 162 1 (2005) 439\u2013485. DOI:http:\/\/www.jstor.org\/stable\/3597377","DOI":"10.4007\/annals.2005.162.439"},{"key":"e_1_3_4_25_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2020.1"},{"key":"e_1_3_4_26_2","first-page":"14","volume-title":"COLT 2010 - The 23rd Conference on Learning Theory","author":"Duchi John C.","year":"2010","unstructured":"John C. Duchi, Shai Shalev-Shwartz, Yoram Singer, and Ambuj Tewari. 2010. Composite objective mirror descent. In COLT 2010 - The 23rd Conference on Learning Theory. 14\u201326. DOI:https:\/\/www.learningtheory.org\/colt2010\/papers\/057Duchi.pdf"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","unstructured":"Zeev Dvir. 2011. On matrix rigidity and locally self-correctable codes. Computational Complexity 20 2 (01 Jun.2011) 367\u2013388. DOI:10.1007\/s00037-011-0009-1","DOI":"10.1007\/s00037-011-0009-1"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","unstructured":"Zeev Dvir and Sivakanth Gopi. 2016. 2-Server PIR with subpolynomial communication. J. ACM 63 4 Article 39 (Sep.2016) 15 pages. DOI:10.1145\/2968443","DOI":"10.1145\/2968443"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060678"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","unstructured":"Edward Farhi Jeffrey Goldstone Sam Gutmann and Michael Sipser. 1998. Limit on the speed of quantum computation in determining parity. Phys. Rev. Lett. 81 (Dec.1998) 5442\u20135444. Issue 24. DOI:10.1103\/PhysRevLett.81.5442","DOI":"10.1103\/PhysRevLett.81.5442"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250866"},{"key":"e_1_3_4_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.41"},{"key":"e_1_3_4_33_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2002.1004353"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","unstructured":"Oded Goldreich Howard Karloff Leonard J. Schulman and Luca Trevisan. 2006. Lower bounds for linear locally decodable codes and privat e information retrieval. Computational Complexity 15 3 (01 Oct.2006) 263\u2013296. DOI:10.1007\/s00037-006-0216-3","DOI":"10.1007\/s00037-006-0216-3"},{"key":"e_1_3_4_35_2","volume-title":"Locality in Coding Theory","author":"Gopi Sivakanth","year":"2018","unstructured":"Sivakanth Gopi. 2018. Locality in Coding Theory. Ph. D. Dissertation. Princeton University. DOI:https:\/\/www.proquest.com\/dissertations-theses\/locality-coding-theory\/docview\/2128009409\/se-2?accountid=14496"},{"key":"e_1_3_4_36_2","doi-asserted-by":"crossref","unstructured":"Leonard Gross. 1975. Logarithmic Sobolev inequalities. American Journal of Mathematics 97 4 (1975) 1061\u20131083. DOI:http:\/\/www.jstor.org\/stable\/2373688","DOI":"10.2307\/2373688"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2019.5"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2017.8"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","unstructured":"Olof Hanner. 1956. On the uniform convexity of \\({L}_p\\) and \\(l_p\\) . Arkiv f\u00f6r Matematik 3 3 (01 Feb.1956) 239\u2013244. DOI:10.1007\/BF02589410","DOI":"10.1007\/BF02589410"},{"key":"e_1_3_4_40_2","unstructured":"G. H. Hardy J. E. Littlewood and G. P\u00f3lya. 1952. Inequalities. Cambridge University Press 10 (1952) 169."},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","unstructured":"Carl W. Helstrom. 1969. Quantum detection and estimation theory. Journal of Statistical Physics 1 2 (01 Jun.1969) 231\u2013252. DOI:10.1007\/BF01007479","DOI":"10.1007\/BF01007479"},{"key":"e_1_3_4_42_2","doi-asserted-by":"crossref","unstructured":"Shlomo Hoory Nathan Linial and Avi Wigderson. 2006. Expander graphs and their applications. Bull. Amer. Math. Soc. 43 4 (2006) 439\u2013561. DOI:https:\/\/ams.org\/journals\/bull\/2006-43-04\/S0273-0979-06-01126-8\/","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","unstructured":"Steven R. Howard Aaditya Ramdas Jon McAuliffe and Jasjeet Sekhon. 2020. Time-uniform Chernoff bounds via nonnegative supermartingales. Probability Surveys 17 (2020) 257\u2013317. DOI:10.1214\/18-PS321","DOI":"10.1214\/18-PS321"},{"key":"e_1_3_4_44_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24676-3_26"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21923"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00054"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.84"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.112"},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316364"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335315"},{"key":"e_1_3_4_51_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780560"},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","unstructured":"Subhash Khot Guy Kindler Elchanan Mossel and Ryan O\u2019Donnell. 2007. Optimal inapproximability results for MAX\u2013CUT and Other 2-Variable CSPs? SIAM J. Comput. 37 1 (2007) 319\u2013357. DOI:10.1137\/S0097539705447372","DOI":"10.1137\/S0097539705447372"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0107213"},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","unstructured":"James R. Lee and Assaf Naor. 2004. Embedding the diamond graph in \\(L_p\\) and dimension reduction in \\(L_1\\) . Geometric & Functional Analysis GAFA 14 4 (01 Aug.2004) 745\u2013747. DOI:10.1007\/s00039-004-0473-8","DOI":"10.1007\/s00039-004-0473-8"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","unstructured":"Nathan Linial Yishay Mansour and Noam Nisan. 1993. Constant depth circuits Fourier transform and learnability. J. ACM 40 3 (Jul.1993) 607\u2013620. DOI:10.1145\/174130.174138","DOI":"10.1145\/174130.174138"},{"key":"e_1_3_4_56_2","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro. 2011. A new exponential separation between quantum and classical one-way communication complexity. Quantum Info. Comput. 11 7\u20138 (Jul.2011) 574\u2013591. DOI:10.5555\/2230916.2230919","DOI":"10.5555\/2230916.2230919"},{"key":"e_1_3_4_57_2","doi-asserted-by":"publisher","unstructured":"Ashley Montanaro. 2012. Some applications of hypercontractive inequalities in quantum information theory. J. Math. Phys. 53 12 (122012) 122206. DOI:10.1063\/1.4769269","DOI":"10.1063\/1.4769269"},{"key":"e_1_3_4_58_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2017.50"},{"key":"e_1_3_4_59_2","doi-asserted-by":"publisher","unstructured":"Ilan Newman. 1991. Private vs. common random bits in communication complexity. Inform. Process. Lett. 39 2 (1991) 67\u201371. DOI:10.1016\/0020-0190(91)90157-D","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"e_1_3_4_60_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45726-7_4"},{"key":"e_1_3_4_61_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782"},{"key":"e_1_3_4_62_2","doi-asserted-by":"publisher","unstructured":"Alessandro Panconesi and Aravind Srinivasan. 1997. Randomized distributed edge coloring via an extension of the Chernoff\u2013Hoeffding bounds. SIAM J. Comput. 26 2 (1997) 350\u2013368. DOI:10.1137\/S0097539793250767","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_3_4_63_2","doi-asserted-by":"crossref","unstructured":"Iosif Pinelis. 1994. Optimum bounds for the distributions of martingales in Banach spaces. The Annals of Probability 22 4 (1994) 1679\u20131706. DOI:http:\/\/www.jstor.org\/stable\/2244912","DOI":"10.1214\/aop\/1176988477"},{"key":"e_1_3_4_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.10"},{"key":"e_1_3_4_65_2","unstructured":"Yaoyun Shi Xiaodi Wu and Wei Yu. 2012. Limits of quantum one-way communication by matrix Hypercontractive Inequality. DOI:https:\/\/cs.umd.edu\/xwu\/papers\/GHM_v4.pdf"},{"key":"e_1_3_4_66_2","unstructured":"Nicole Tomczak-Jaegermann. 1974. The moduli of smoothness and convexity and the Rademacher averages of the trace classes \\({S}_{p}\\) \\((1\\le p\\lt \\infty)\\) . Studia Mathematica 50 2 (1974) 163\u2013182. DOI:https:\/\/eudml.org\/doc\/urn:eudml:doc:217886"},{"key":"e_1_3_4_67_2","doi-asserted-by":"publisher","unstructured":"Luca Trevisan. 2004. Some applications of coding theory in computational complexity. arXiv preprint cs\/0409044 (2004). DOI:10.48550\/arXiv.cs\/0409044","DOI":"10.48550\/arXiv.cs\/0409044"},{"key":"e_1_3_4_68_2","doi-asserted-by":"publisher","unstructured":"Joel A. Tropp. 2015. An introduction to matrix concentration inequalities. Foundations and Trends\u00ae in Machine Learning 8 1-2 (2015) 1\u2013230. DOI:10.1561\/2200000048","DOI":"10.1561\/2200000048"},{"key":"e_1_3_4_69_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.2"},{"key":"e_1_3_4_70_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781316848142"},{"key":"e_1_3_4_71_2","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_115"},{"key":"e_1_3_4_72_2","doi-asserted-by":"crossref","unstructured":"Ronald de Wolf. 2008. A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing (2008) 1\u201320. DOI:https:\/\/theoryofcomputing.org\/articles\/gs001\/","DOI":"10.4086\/toc.gs.2008.001"},{"key":"e_1_3_4_73_2","doi-asserted-by":"crossref","unstructured":"Pawe\u0142 Wolff. 2007. Hypercontractivity of simple random variables. Studia Mathematica 3 180 (2007) 219\u2013236. DOI:https:\/\/eudml.org\/doc\/284523","DOI":"10.4064\/sm180-3-3"},{"key":"e_1_3_4_74_2","doi-asserted-by":"publisher","unstructured":"Sergey Yekhanin. 2012. Locally decodable codes. Foundations and Trends\u00ae in Theoretical Computer Science 6 3 (2012) 139\u2013255. DOI:10.1561\/0400000030","DOI":"10.1561\/0400000030"},{"key":"e_1_3_4_75_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-30545-0_18"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3688824","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3688824","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:04:09Z","timestamp":1750291449000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3688824"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,11]]},"references-count":74,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3688824"],"URL":"https:\/\/doi.org\/10.1145\/3688824","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2024,11,11]]},"assertion":[{"value":"2023-06-13","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-07-02","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}