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

Jop Briët; Assaf Naor; Oded Regev

doi:10.3934/era.2012.19.120

Article Contents

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

This volume Previous Article On Totally integrable magnetic billiards on constant curvature surface Next Article

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

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

Received: July 31, 2012

Revised: September 30, 2012

Published: December 2011

Abstract Related Papers Cited by

Abstract

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: 46B28.

Citation:

Related Papers

Cited by

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.