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, Springer, New York, 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-37.  Google Scholar

[3]

A. Beimel, Y. Ishai, E. Kushilevitz and I. Orlov, Share conversion and private information retrieval, in "Proc. 27th IEEE Conf. on Computational Complexity (CCC'12)" (2012), 258-268. 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 "49th Annual IEEE Symposium on Foundations of Computer Science" (2008), 477-486. Available at http://arxiv.org/abs/0705.3806. Google Scholar

[5]

J. Bourgain, New Banach space properties of the disc algebra and $H^{\infty}$, Acta Math., 152 (1984), 1-48.  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-53. 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-123.  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-227. 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-533. 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-310. doi: 10.2989/16073600209486017.  Google Scholar

[11]

J. Diestel, J. Fourie and J. Swart, The projective tensor product. I, in "Trends in Banach Spaces and Operator Theory (Memphis, TN, 2001)" 321 of Contemp. Math., 37-65. Amer. Math. Soc., Providence, RI, (2003).  Google Scholar

[12]

J. Diestel, J. H. Fourie and J. Swart, "The Metric Theory of Tensor Products," American Mathematical Society, Providence, RI, 2008. Grothendieck's résumé revisited.  Google Scholar

[13]

K. Efremenko, 3-query locally decodable codes of subexponential length, in "STOC'09-Proceedings of the 2009 ACM International Symposium on Theory of Computing" 39-44. ACM, New York, (2009).  Google Scholar

[14]

V. Grolmusz, Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs, Combinatorica, 20 (2000), 71-85. 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-79.  Google Scholar

[16]

J. Katz and L. Trevisan, On the efficiency of local decoding procedures for error-correcting codes, in "Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing" 80-86 (electronic), New York, (2000). ACM.  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-420. doi: 10.1016/j.jcss.2004.04.007.  Google Scholar

[18]

D. R. Lewis, Duals of tensor products, in "Banach spaces of analytic functions (Proc. Pelczynski Conf., Kent State Univ., Kent, Ohio, 1976" 57-66. Lecture Notes in Math., 604. Springer, Berlin, (1977).  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-90.  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., École Norm. Sup. (4), 13 (1980), 23-43.  Google Scholar

[21]

G. Pisier, Counterexamples to a conjecture of Grothendieck, Acta. Math., 151 (1983), 181-208.  Google Scholar

[22]

G. Pisier, Factorization of operator valued analytic functions, Adv. Math., 93 (1992), 61-125.  Google Scholar

[23]

G. Pisier, Random series of trace class operators, in "Proceedings Cuarto CLAPEM Mexico 1990. Contribuciones en probabilidad y estadistica matematica" (1992), 29-42. Available at http://arxiv.org/abs/1103.2090. Google Scholar

[24]

R. A. Ryan, "Introduction to Tensor Products of Banach Spaces," Springer Monographs in Mathematics. Springer-Verlag London Ltd., London, 2002.\MRSHORT{1888309} 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-182.  Google Scholar

[26]

L. Trevisan, Some applications of coding theory in computational complexity, in "Complexity of Computations and Proofs" 13 of Quad. Mat., 347-424. Dept. Math., Seconda Univ. Napoli, Caserta, (2004).  Google Scholar

[27]

D. P. Woodruff, New lower bounds for general locally decodable codes, Electronic Colloquium on Computational Complexity (ECCC), 14 (2007), 006. Google Scholar

[28]

S. Yekhanin, Towards 3-query locally decodable codes of subexponential length, J. ACM, 55 (2008), pp16.  Google Scholar

[29]

S. Yekhanin, Locally decodable codes, Found. Trends Theor. Comput. Sci., 7 (2011), 1-117. Google Scholar

show all references

References:
[1]

F. Albiac and N. J. Kalton, "Topics in Banach space theory," 233 of Graduate Texts in Mathematics, Springer, New York, 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-37.  Google Scholar

[3]

A. Beimel, Y. Ishai, E. Kushilevitz and I. Orlov, Share conversion and private information retrieval, in "Proc. 27th IEEE Conf. on Computational Complexity (CCC'12)" (2012), 258-268. 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 "49th Annual IEEE Symposium on Foundations of Computer Science" (2008), 477-486. Available at http://arxiv.org/abs/0705.3806. Google Scholar

[5]

J. Bourgain, New Banach space properties of the disc algebra and $H^{\infty}$, Acta Math., 152 (1984), 1-48.  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-53. 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-123.  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-227. 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-533. 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-310. doi: 10.2989/16073600209486017.  Google Scholar

[11]

J. Diestel, J. Fourie and J. Swart, The projective tensor product. I, in "Trends in Banach Spaces and Operator Theory (Memphis, TN, 2001)" 321 of Contemp. Math., 37-65. Amer. Math. Soc., Providence, RI, (2003).  Google Scholar

[12]

J. Diestel, J. H. Fourie and J. Swart, "The Metric Theory of Tensor Products," American Mathematical Society, Providence, RI, 2008. Grothendieck's résumé revisited.  Google Scholar

[13]

K. Efremenko, 3-query locally decodable codes of subexponential length, in "STOC'09-Proceedings of the 2009 ACM International Symposium on Theory of Computing" 39-44. ACM, New York, (2009).  Google Scholar

[14]

V. Grolmusz, Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs, Combinatorica, 20 (2000), 71-85. 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-79.  Google Scholar

[16]

J. Katz and L. Trevisan, On the efficiency of local decoding procedures for error-correcting codes, in "Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing" 80-86 (electronic), New York, (2000). ACM.  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-420. doi: 10.1016/j.jcss.2004.04.007.  Google Scholar

[18]

D. R. Lewis, Duals of tensor products, in "Banach spaces of analytic functions (Proc. Pelczynski Conf., Kent State Univ., Kent, Ohio, 1976" 57-66. Lecture Notes in Math., 604. Springer, Berlin, (1977).  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-90.  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., École Norm. Sup. (4), 13 (1980), 23-43.  Google Scholar

[21]

G. Pisier, Counterexamples to a conjecture of Grothendieck, Acta. Math., 151 (1983), 181-208.  Google Scholar

[22]

G. Pisier, Factorization of operator valued analytic functions, Adv. Math., 93 (1992), 61-125.  Google Scholar

[23]

G. Pisier, Random series of trace class operators, in "Proceedings Cuarto CLAPEM Mexico 1990. Contribuciones en probabilidad y estadistica matematica" (1992), 29-42. Available at http://arxiv.org/abs/1103.2090. Google Scholar

[24]

R. A. Ryan, "Introduction to Tensor Products of Banach Spaces," Springer Monographs in Mathematics. Springer-Verlag London Ltd., London, 2002.\MRSHORT{1888309} 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-182.  Google Scholar

[26]

L. Trevisan, Some applications of coding theory in computational complexity, in "Complexity of Computations and Proofs" 13 of Quad. Mat., 347-424. Dept. Math., Seconda Univ. Napoli, Caserta, (2004).  Google Scholar

[27]

D. P. Woodruff, New lower bounds for general locally decodable codes, Electronic Colloquium on Computational Complexity (ECCC), 14 (2007), 006. Google Scholar

[28]

S. Yekhanin, Towards 3-query locally decodable codes of subexponential length, J. ACM, 55 (2008), pp16.  Google Scholar

[29]

S. Yekhanin, Locally decodable codes, Found. Trends Theor. Comput. Sci., 7 (2011), 1-117. 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]

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
[3]

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
[4]

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, 2003, 9 (3) : 549-558. doi: 10.3934/dcds.2003.9.549
[5]

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
[6]

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
[7]

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
[8]

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
[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]

Carlos Munuera, Wanderson Tenório, Fernando Torres. Locally recoverable codes from algebraic curves with separated variables. Advances in Mathematics of Communications, 2020, 14 (2) : 265-278. doi: 10.3934/amc.2020019
[12]

Michel Lavrauw, Geertrui Van de Voorde. Locally repairable codes with high availability based on generalised quadrangles. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020099
[13]

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
[14]

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
[15]

Jin Wang, Jun-E Feng, Hua-Lin Huang. Solvability of the matrix equation $ AX^{2} = B $ with semi-tensor product. Electronic Research Archive, 2021, 29 (3) : 2249-2267. doi: 10.3934/era.2020114
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2020 Impact Factor: 0.929

Tools

Metrics

  • PDF downloads (38)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences