{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T16:33:09Z","timestamp":1789662789996,"version":"4.0.1"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>A matching vector (MV) family modulo $m$ is a pair of ordered lists $U=(u_1,\\ldots,u_t)$ and $V=(v_1,\\ldots,v_t)$ where $u_i$, $v_j \\in \\mathbb{Z}_m^n$ with the following inner product pattern: for any $i$, $\\langle u_i,v_i\\rangle=0$, and for any $i \\ne j$, $\\langle u_i,v_j\\rangle \\ne 0$. An MV family is called $q$-restricted if inner products $\\langle u_i,v_j\\rangle$ take at most $q$ different values. Our interest in MV families stems from their recent application in the construction of subexponential locally decodable codes (LDCs). There, $q$-restricted MV families are used to construct LDCs with $q$ queries, and there is special interest in the regime where $q$ is constant. When $m$ is a prime it is known that such constructions yield codes with exponential block length. However, for composite $m$ the behavior is dramatically different. A recent work by Efremenko [SIAM J. Comput., 40 (2011), pp. 1154--1178] (based on an approach initiated by Yekhanin [J. ACM, 55 (2008), pp. 1--16]) gives the first subexponential LDC with constant queries. It is based on a construction of an MV family of superpolynomial size by Grolmusz [Combinatorica, 20 (2000), pp. 71--86] modulo composite $m$. In this work, we prove two lower bounds on the block length of LDCs which are based on black box construction using MV families. When $q$ is constant (or sufficiently small), we prove that such LDCs must have a quadratic block length. When the modulus $m$ is constant (as it is in the construction of Efremenko) we prove a superpolynomial lower bound on the block-length of the LDCs, assuming a well-known conjecture in additive combinatorics, the polynomial Freiman--Ruzsa conjecture over $\\mathbb{Z}_m$.<\/jats:p>","DOI":"10.1137\/130932296","type":"journal-article","created":{"date-parts":[[2014,9,25]],"date-time":"2014-09-25T13:06:12Z","timestamp":1411650372000},"page":"1654-1683","source":"Crossref","is-referenced-by-count":5,"title":["New Bounds for Matching Vector Families"],"prefix":"10.1137","volume":"43","author":[{"given":"Abhishek","family":"Bhowmick","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zeev","family":"Dvir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shachar","family":"Lovett","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,9,25]]},"reference":[{"key":"atypb1","unstructured":"L. Babai and P. Frankl,\n                      Linear Algebra Methods in Combinatorics\n                      , University of Chicago, 1998."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01212974"},{"key":"atypb3","doi-asserted-by":"crossref","unstructured":"A. Beimel, Y. Ishai, E. Kushilevitz, and J.F. Raymond,\n                      Breaking the ${O}(n^{1\/(2k-1)})$ barrier for information-theoretic private information retrieval\n                      , in Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science (FOCS), 2002, pp. 261-270.","DOI":"10.1109\/SFCS.2002.1181949"},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"A. Ben-Aroya, K. Efremenko, and A. Ta-Shma,\n                      Local list decoding with a constant number of queries\n                      , in Proceedings of the 51st IEEE Symposium on Foundations of Computer Science (FOCS), 2010, pp. 715-722.","DOI":"10.1109\/FOCS.2010.88"},{"key":"atypb5","unstructured":"E. Ben-Sasson, S. Lovett, and N. Zewi,\n                      An Additive Combinatorics Approach to the Log-Rank Conjecture in Communication Complexity\n                      , CoRR abs\/1111.5884, 2011."},{"key":"atypb6","first-page":"177","author":"Ben-Sasson E.","year":"2011","journal-title":"Proceedings of STOC"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/100804322"},{"key":"atypb9","first-page":"20","author":"Dvir Z.","year":"2013","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1137\/090772721"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"O. Goldreich, H. Karloff, L. Schulman, and L. Trevisan,\n                      Lower bounds for locally decodable codes and private information retrieval\n                      , in Proceedings of the 17th IEEE Computational Complexity Conference (CCC), 2002, pp. 175-183.","DOI":"10.1109\/CCC.2002.1004353"},{"key":"atypb12","first-page":"230","volume":"17","author":"Gowers W. T.","year":"1998","journal-title":"Geom. Funct. Anal."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070032"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(02)00204-3"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"T. Itoh and Y. Suzuki,\n                      New constructions for query-efficient locally decodable codes of subexponential length\n                      , IEICE Trans. Inform. Systems, (2010), pp. 263-270.","DOI":"10.1587\/transinf.E93.D.263"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"J. Katz and L. Trevisan,\n                      On the efficiency of local decoding procedures for error-correcting codes\n                      , in Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), 2000, pp. 80-86.","DOI":"10.1145\/335305.335315"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/070696519"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.007"},{"key":"atypb20","unstructured":"Y. Meng Chee, T. Feng, S. Ling, H. Wang, and L. Zhang,\n                      Query-efficient locally decodable codes of subexponential length\n                      , in Electronic Colloquium on Computational Complexity, TR10-173, 2010."},{"key":"atypb21","unstructured":"P. Raghavendra,\n                      A note on Yekhanin's locally decodable codes\n                      , in Electronic Colloquium on Computational Complexity, TR07-016, 2007."},{"key":"atypb22","unstructured":"B. I. Ruzsa and I. Z. Ruzsa,\n                      An Analog of Freiman's Theorem in Groups\n                      , 1993."},{"key":"atypb23","unstructured":"T. Sanders,\n                      On the Bogolyubov-Ruzsa Lemma\n                      , arXiv:1011.0107, 2010."},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970007"},{"key":"atypb25","first-page":"347","volume":"13","author":"Trevisan L.","year":"2004","journal-title":"Quad. Mat."},{"key":"atypb26","unstructured":"D. Woodruff,\n                      New lower bounds for general locally decodable codes\n                      , in Electronic Colloquium on Computational Complexity, TR07-006, 2007."},{"key":"atypb27","first-page":"766","author":"Woodruff D. P.","year":"2010","journal-title":"Berlin"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1145\/1326554.1326555"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1561\/0400000030"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2012.03.008"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130932296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:37:06Z","timestamp":1787337426000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130932296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":29,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/130932296"],"URL":"https:\/\/doi.org\/10.1137\/130932296","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}