# American Institute of Mathematical Sciences

2012, 19: 120-130. doi: 10.3934/era.2012.19.120

## Locally decodable codes and the failure of cotype for projective tensor products

 1 Centrum Wiskunde & Informatica (CWI), Science Park 123, 1098 SJ Amsterdam, Netherlands 2 Courant Institute, New York University, 251 Mercer Street, New York NY 10012, United States 3 École normale supérieure, Département d'informatique, 45 rue d'Ulm, Paris, France

Received  August 2012 Revised  October 2012 Published  November 2012

It is shown that for every $p\in (1,\infty)$ there exists a Banach space $X$ of finite cotype such that the projective tensor product $l_p\hat\otimes X$ fails to have finite cotype. More generally, if $p_1,p_2,p_3\in (1,\infty)$ satisfy $\frac{1}{p_1}+\frac{1}{p_2}+\frac{1}{p_3}\le 1$ then $l_{p_1}\hat\otimes l_{p_2} \hat\otimes l_{p_3}$ does not have finite cotype. This is proved via a connection to the theory of locally decodable codes.
Citation: Jop Briët, Assaf Naor, Oded Regev. Locally decodable codes and the failure of cotype for projective tensor products. Electronic Research Announcements, 2012, 19: 120-130. doi: 10.3934/era.2012.19.120
 [1] F. Albiac and N. J. Kalton, "Topics in Banach space theory,", 233 of Graduate Texts in Mathematics, 233 (2006). Google Scholar [2] A. Arias and J. D. Farmer, On the structure of tensor products of $l_p$-spaces,, Pacific J. Math., 175 (1996), 13. Google Scholar [3] A. Beimel, Y. Ishai, E. Kushilevitz and I. Orlov, Share conversion and private information retrieval,, in, (2012), 258. Google Scholar [4] A. Ben-Aroya, O. Regev and R. de Wolf, A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs,, in, (2008), 477. Google Scholar [5] J. Bourgain, New Banach space properties of the disc algebra and $H^{\infty}$,, Acta Math., 152 (1984), 1. Google Scholar [6] J. Bourgain, On martingales transforms in finite-dimensional lattices with an appendix on the $K$-convexity constant,, Math. Nachr., 119 (1984), 41. doi: 10.1002/mana.19841190104. Google Scholar [7] J. Bourgain and G. Pisier, A construction of $\mathcal L_{\infty }$-spaces and related Banach spaces,, Bol. Soc. Brasil. Mat., 14 (1983), 109. Google Scholar [8] Q. Bu, Observations about the projective tensor product of Banach spaces. II. $L^p(0,1)\hat\otimes X,\ 1,, Quaest. Math., 25 (2002), 209. doi: 10.2989/16073600209486010. Google Scholar [9] Q. Bu and J. Diestel, Observations about the projective tensor product of Banach spaces. I.$l^p\hat\otimesX,\ 1,, Quaest. Math., 24 (2001), 519. doi: 10.1080/16073606.2001.9639238. Google Scholar [10] Q. Bu and P. N. Dowling, Observations about the projective tensor product of Banach spaces. III. $L^p[0,1]\hat\otimes X,\ 1,, Quaest. Math., 25 (2002), 303. doi: 10.2989/16073600209486017. Google Scholar [11] J. Diestel, J. Fourie and J. Swart, The projective tensor product. I,, in, 321 (2003), 37. Google Scholar [12] J. Diestel, J. H. Fourie and J. Swart, "The Metric Theory of Tensor Products,", American Mathematical Society, (2008). Google Scholar [13] K. Efremenko, 3-query locally decodable codes of subexponential length,, in, (2009), 39. Google Scholar [14] V. Grolmusz, Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs,, Combinatorica, 20 (2000), 71. doi: 10.1007/s004930070032. Google Scholar [15] A. Grothendieck, Résumé de la théorie métrique des produits tensoriels topologiques,, Bol. Soc. Mat. São Paulo, 8 (1953), 1. Google Scholar [16] J. Katz and L. Trevisan, On the efficiency of local decoding procedures for error-correcting codes,, in, (2000), 80. Google Scholar [17] I. Kerenidis and R. de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument,, J. Comput. System Sci., 69 (2004), 395. doi: 10.1016/j.jcss.2004.04.007. Google Scholar [18] D. R. Lewis, Duals of tensor products,, in, 604 (1977), 57. Google Scholar [19] B. Maurey and G. Pisier, Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach,, Studia Math., 58 (1976), 45. Google Scholar [20] G. Pisier, Un théorème sur les opérateurs linéaires entre espaces de Banach qui se factorisent par un espace de Hilbert,, Ann. Sci., 13 (1980), 23. Google Scholar [21] G. Pisier, Counterexamples to a conjecture of Grothendieck,, Acta. Math., 151 (1983), 181. Google Scholar [22] G. Pisier, Factorization of operator valued analytic functions,, Adv. Math., 93 (1992), 61. Google Scholar [23] G. Pisier, Random series of trace class operators,, in, (1992), 29. Google Scholar [24] R. A. Ryan, "Introduction to Tensor Products of Banach Spaces,", Springer Monographs in Mathematics. Springer-Verlag London Ltd., (2002). Google Scholar [25] N. Tomczak-Jaegermann, The moduli of smoothness and convexity and the Rademacher averages of trace classes$S_p(1\leq p<\infty )$,, Studia Math., 50 (1974), 163. Google Scholar [26] L. Trevisan, Some applications of coding theory in computational complexity,, in, 13 (2004), 347. Google Scholar [27] D. P. Woodruff, New lower bounds for general locally decodable codes,, Electronic Colloquium on Computational Complexity (ECCC), 14 (2007). Google Scholar [28] S. Yekhanin, Towards 3-query locally decodable codes of subexponential length,, J. ACM, 55 (2008). Google Scholar [29] S. Yekhanin, Locally decodable codes,, Found. Trends Theor. Comput. Sci., 7 (2011), 1. Google Scholar show all references ##### References:  [1] F. Albiac and N. J. Kalton, "Topics in Banach space theory,", 233 of Graduate Texts in Mathematics, 233 (2006). Google Scholar [2] A. Arias and J. D. Farmer, On the structure of tensor products of$l_p$-spaces,, Pacific J. Math., 175 (1996), 13. Google Scholar [3] A. Beimel, Y. Ishai, E. Kushilevitz and I. Orlov, Share conversion and private information retrieval,, in, (2012), 258. Google Scholar [4] A. Ben-Aroya, O. Regev and R. de Wolf, A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs,, in, (2008), 477. Google Scholar [5] J. Bourgain, New Banach space properties of the disc algebra and$H^{\infty}$,, Acta Math., 152 (1984), 1. Google Scholar [6] J. Bourgain, On martingales transforms in finite-dimensional lattices with an appendix on the$K$-convexity constant,, Math. Nachr., 119 (1984), 41. doi: 10.1002/mana.19841190104. Google Scholar [7] J. Bourgain and G. Pisier, A construction of$\mathcal L_{\infty }$-spaces and related Banach spaces,, Bol. Soc. Brasil. Mat., 14 (1983), 109. Google Scholar [8] Q. Bu, Observations about the projective tensor product of Banach spaces. II.$L^p(0,1)\hat\otimes X,\ 1,, Quaest. Math., 25 (2002), 209. doi: 10.2989/16073600209486010. Google Scholar [9] Q. Bu and J. Diestel, Observations about the projective tensor product of Banach spaces. I. $l^p\hat\otimesX,\ 1,, Quaest. Math., 24 (2001), 519. doi: 10.1080/16073606.2001.9639238. Google Scholar [10] Q. Bu and P. N. Dowling, Observations about the projective tensor product of Banach spaces. III.$L^p[0,1]\hat\otimes X,\ 1,, Quaest. Math., 25 (2002), 303. doi: 10.2989/16073600209486017. Google Scholar [11] J. Diestel, J. Fourie and J. Swart, The projective tensor product. I,, in, 321 (2003), 37. Google Scholar [12] J. Diestel, J. H. Fourie and J. Swart, "The Metric Theory of Tensor Products,", American Mathematical Society, (2008). Google Scholar [13] K. Efremenko, 3-query locally decodable codes of subexponential length,, in, (2009), 39. Google Scholar [14] V. Grolmusz, Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs,, Combinatorica, 20 (2000), 71. doi: 10.1007/s004930070032. Google Scholar [15] A. Grothendieck, Résumé de la théorie métrique des produits tensoriels topologiques,, Bol. Soc. Mat. São Paulo, 8 (1953), 1. Google Scholar [16] J. Katz and L. Trevisan, On the efficiency of local decoding procedures for error-correcting codes,, in, (2000), 80. Google Scholar [17] I. Kerenidis and R. de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument,, J. Comput. System Sci., 69 (2004), 395. doi: 10.1016/j.jcss.2004.04.007. Google Scholar [18] D. R. Lewis, Duals of tensor products,, in, 604 (1977), 57. Google Scholar [19] B. Maurey and G. Pisier, Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach,, Studia Math., 58 (1976), 45. Google Scholar [20] G. Pisier, Un théorème sur les opérateurs linéaires entre espaces de Banach qui se factorisent par un espace de Hilbert,, Ann. Sci., 13 (1980), 23. Google Scholar [21] G. Pisier, Counterexamples to a conjecture of Grothendieck,, Acta. Math., 151 (1983), 181. Google Scholar [22] G. Pisier, Factorization of operator valued analytic functions,, Adv. Math., 93 (1992), 61. Google Scholar [23] G. Pisier, Random series of trace class operators,, in, (1992), 29. Google Scholar [24] R. A. Ryan, "Introduction to Tensor Products of Banach Spaces,", Springer Monographs in Mathematics. Springer-Verlag London Ltd., (2002). Google Scholar [25] N. Tomczak-Jaegermann, The moduli of smoothness and convexity and the Rademacher averages of trace classes $S_p(1\leq p<\infty )$,, Studia Math., 50 (1974), 163. Google Scholar [26] L. Trevisan, Some applications of coding theory in computational complexity,, in, 13 (2004), 347. Google Scholar [27] D. P. Woodruff, New lower bounds for general locally decodable codes,, Electronic Colloquium on Computational Complexity (ECCC), 14 (2007). Google Scholar [28] S. Yekhanin, Towards 3-query locally decodable codes of subexponential length,, J. ACM, 55 (2008). Google Scholar [29] S. Yekhanin, Locally decodable codes,, Found. Trends Theor. Comput. Sci., 7 (2011), 1. Google Scholar
 [1] Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Addendum. Advances in Mathematics of Communications, 2011, 5 (3) : 543-546. doi: 10.3934/amc.2011.5.543 [2] H. M. Hastings, S. Silberger, M. T. Weiss, Y. Wu. A twisted tensor product on symbolic dynamical systems and the Ashley's problem. Discrete & Continuous Dynamical Systems - A, 2003, 9 (3) : 549-558. doi: 10.3934/dcds.2003.9.549 [3] Jesús Carrillo-Pacheco, Felipe Zaldivar. On codes over FFN$(1,q)$-projective varieties. Advances in Mathematics of Communications, 2016, 10 (2) : 209-220. doi: 10.3934/amc.2016001 [4] Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127 [5] Sara D. Cardell, Joan-Josep Climent. An approach to the performance of SPC product codes on the erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 11-28. doi: 10.3934/amc.2016.10.11 [6] David Clark, Vladimir D. Tonchev. A new class of majority-logic decodable codes derived from polarity designs. Advances in Mathematics of Communications, 2013, 7 (2) : 175-186. doi: 10.3934/amc.2013.7.175 [7] Susanne Pumplün, Andrew Steele. The nonassociative algebras used to build fast-decodable space-time block codes. Advances in Mathematics of Communications, 2015, 9 (4) : 449-469. doi: 10.3934/amc.2015.9.449 [8] Susanne Pumplün. How to obtain division algebras used for fast-decodable space-time block codes. Advances in Mathematics of Communications, 2014, 8 (3) : 323-342. doi: 10.3934/amc.2014.8.323 [9] Fernando Hernando, Diego Ruano. New linear codes from matrix-product codes with polynomial units. Advances in Mathematics of Communications, 2010, 4 (3) : 363-367. doi: 10.3934/amc.2010.4.363 [10] Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119 [11] Jinghong Liu, Yinsuo Jia. Gradient superconvergence post-processing of the tensor-product quadratic pentahedral finite element. Discrete & Continuous Dynamical Systems - B, 2015, 20 (2) : 495-504. doi: 10.3934/dcdsb.2015.20.495 [12] Kathryn Haymaker, Beth Malmskog, Gretchen L. Matthews. Locally recoverable codes with availability t≥2 from fiber products of curves. Advances in Mathematics of Communications, 2018, 12 (2) : 317-336. doi: 10.3934/amc.2018020 [13] Carlos Munuera, Wanderson Tenório, Fernando Torres. Locally recoverable codes from algebraic curves with separated variables. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020019 [14] Fernando Hernando, Tom Høholdt, Diego Ruano. List decoding of matrix-product codes from nested codes: An application to quasi-cyclic codes. Advances in Mathematics of Communications, 2012, 6 (3) : 259-272. doi: 10.3934/amc.2012.6.259 [15] Christine A. Kelley, Deepak Sridhara, Joachim Rosenthal. Zig-zag and replacement product graphs and LDPC codes. Advances in Mathematics of Communications, 2008, 2 (4) : 347-372. doi: 10.3934/amc.2008.2.347 [16] Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010 [17] Steve Limburg, David Grant, Mahesh K. Varanasi. Higher genus universally decodable matrices (UDMG). Advances in Mathematics of Communications, 2014, 8 (3) : 257-270. doi: 10.3934/amc.2014.8.257 [18] Kristian Bjerklöv, Russell Johnson. Minimal subsets of projective flows. Discrete & Continuous Dynamical Systems - B, 2008, 9 (3&4, May) : 493-516. doi: 10.3934/dcdsb.2008.9.493 [19] Jungkai A. Chen and Meng Chen. On projective threefolds of general type. Electronic Research Announcements, 2007, 14: 69-73. doi: 10.3934/era.2007.14.69 [20] Liliana Trejo-Valencia, Edgardo Ugalde. Projective distance and $g$-measures. Discrete & Continuous Dynamical Systems - B, 2015, 20 (10) : 3565-3579. doi: 10.3934/dcdsb.2015.20.3565

2018 Impact Factor: 0.263