American Institute of Mathematical Sciences

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

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

Jop Briët 1, , Assaf Naor 2, and  Oded Regev 3,

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.
Keywords: projective tensor product, locally decodable codes..
Mathematics Subject Classification: Primary: 46B07; Secondary: 46B2.
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
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

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

Tools

Metrics

  • PDF downloads (16)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences