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

Previous Article
ERA-MS Home
This Volume
Next Article
On Totally integrable magnetic billiards on constant curvature surface

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

Abstract
Related Papers

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.
[2]	A. Arias and J. D. Farmer, On the structure of tensor products of $l_p$-spaces, Pacific J. Math., 175 (1996), 13-37.
[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.
[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.
[5]	J. Bourgain, New Banach space properties of the disc algebra and $H^{\infty}$, Acta Math., 152 (1984), 1-48.
[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.
[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.
[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.
[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.
[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.
[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).
[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.
[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).
[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.
[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.
[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.
[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.
[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).
[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.
[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.
[21]	G. Pisier, Counterexamples to a conjecture of Grothendieck, Acta. Math., 151 (1983), 181-208.
[22]	G. Pisier, Factorization of operator valued analytic functions, Adv. Math., 93 (1992), 61-125.
[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.
[24]	R. A. Ryan, "Introduction to Tensor Products of Banach Spaces," Springer Monographs in Mathematics. Springer-Verlag London Ltd., London, 2002.\MRSHORT{1888309}
[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.
[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).
[27]	D. P. Woodruff, New lower bounds for general locally decodable codes, Electronic Colloquium on Computational Complexity (ECCC), 14 (2007), 006.
[28]	S. Yekhanin, Towards 3-query locally decodable codes of subexponential length, J. ACM, 55 (2008), pp16.
[29]	S. Yekhanin, Locally decodable codes, Found. Trends Theor. Comput. Sci., 7 (2011), 1-117.

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.
[2]	A. Arias and J. D. Farmer, On the structure of tensor products of $l_p$-spaces, Pacific J. Math., 175 (1996), 13-37.
[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.
[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.
[5]	J. Bourgain, New Banach space properties of the disc algebra and $H^{\infty}$, Acta Math., 152 (1984), 1-48.
[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.
[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.
[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.
[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.
[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.
[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).
[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.
[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).
[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.
[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.
[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.
[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.
[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).
[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.
[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.
[21]	G. Pisier, Counterexamples to a conjecture of Grothendieck, Acta. Math., 151 (1983), 181-208.
[22]	G. Pisier, Factorization of operator valued analytic functions, Adv. Math., 93 (1992), 61-125.
[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.
[24]	R. A. Ryan, "Introduction to Tensor Products of Banach Spaces," Springer Monographs in Mathematics. Springer-Verlag London Ltd., London, 2002.\MRSHORT{1888309}
[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.
[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).
[27]	D. P. Woodruff, New lower bounds for general locally decodable codes, Electronic Colloquium on Computational Complexity (ECCC), 14 (2007), 006.
[28]	S. Yekhanin, Towards 3-query locally decodable codes of subexponential length, J. ACM, 55 (2008), pp16.
[29]	S. Yekhanin, Locally decodable codes, Found. Trends Theor. Comput. Sci., 7 (2011), 1-117.

[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 and 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]	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
[10]	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
[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]	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]	Michel Lavrauw, Geertrui Van de Voorde. Locally repairable codes with high availability based on generalised quadrangles. Advances in Mathematics of Communications, 2022, 16 (1) : 73-81. doi: 10.3934/amc.2020099
[14]	Jinghong Liu, Yinsuo Jia. Gradient superconvergence post-processing of the tensor-product quadratic pentahedral finite element. Discrete and 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 and 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

Other articles
by authors

on AIMS
Jop Briët Assaf Naor Oded Regev
on Google Scholar
Jop Briët Assaf Naor Oded Regev

[Back to Top]