- Previous Article
- ERA-MS Home
- This Volume
-
Next Article
On Totally integrable magnetic billiards on constant curvature surface
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 |
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
[Back to Top]