{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,9]],"date-time":"2023-01-09T22:16:21Z","timestamp":1673302581788},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,11,28]],"date-time":"2015-11-28T00:00:00Z","timestamp":1448668800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00493-015-3024-z","type":"journal-article","created":{"date-parts":[[2015,11,28]],"date-time":"2015-11-28T00:18:55Z","timestamp":1448669935000},"page":"1-36","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Tight lower bounds for linear 2-query LCCs over finite fields"],"prefix":"10.1007","volume":"36","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zeev","family":"Dvir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amir","family":"Shpilka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,28]]},"reference":[{"key":"3024_CR1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1017\/S0963548307008917","volume":"18","author":"N. Alon","year":"2009","unstructured":"N. Alon: Perturbed identity matrices have high rank: Proof and applications, Combin. Probab. Comput. 18 (2009), 3\u201315.","journal-title":"Combin. Probab. Comput."},{"key":"3024_CR2","volume-title":"Proc. 43rd Annual ACM Symposium on the Theory of Computing","author":"B. Barak","year":"2011","unstructured":"B. Barak, Z. Dvir, A. Wigderson and A. Yehudayoff: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes, in: Proc. 43rd Annual ACM Symposium on the Theory of Computing. ACM, 2011."},{"key":"3024_CR3","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1007\/BF02579184","volume":"3","author":"J. Beck","year":"1983","unstructured":"J. Beck: On the lattice property of the plane and some problems of Dirac, Motzkin and Erd\u0151s in combinatorial geometry, Combinatorica 3 (1983), 281\u2013297.","journal-title":"Combinatorica"},{"key":"3024_CR4","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1007\/s00453-008-9272-1","volume":"58","author":"O. Barkol","year":"2010","unstructured":"O. Barkol, Y. Ishai and E. Weinreb: On locally decodable codes, self-correctable codes, and t-private PIR, Algorithmica 58 (2010), 831\u2013859.","journal-title":"Algorithmica"},{"key":"3024_CR5","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF01212974","volume":"14","author":"A. Balog","year":"1994","unstructured":"A. Balog and E. Szemer\u00e9di: A statistical theorem of set addition, Combinatorica 14 (1994), 263\u2013268.","journal-title":"Combinatorica"},{"key":"3024_CR6","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1137\/05063605X","volume":"36","author":"Z. Dvir","year":"2007","unstructured":"Z. Dvir and A. Shpilka: Locally decodable codes with two queries and polynomial identity testing for depth 3 circuits, SIAM J. Comput. 36 (2007), 1404\u20131434.","journal-title":"SIAM J. Comput."},{"key":"3024_CR7","first-page":"291","volume-title":"Proc. 25th Annual IEEE Conference on Computational Complexity","author":"Z. Dvir","year":"2010","unstructured":"Z. Dvir: On matrix rigidity and locally self-correctable codes, in: Proc. 25th Annual IEEE Conference on Computational Complexity, 291\u2013298, 2010."},{"key":"3024_CR8","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/s00037-006-0216-3","volume":"15","author":"O. Goldreich","year":"2006","unstructured":"O. Goldreich, H. J. Karloff, L. J. Schulman and L. Trevisan: Lower bounds for linear locally decodable codes and private information retrieval, Comput. Complexity 15 (2006), 263\u2013296.","journal-title":"Comput. Complexity"},{"key":"3024_CR9","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1007\/s000390050065","volume":"8","author":"T. Gowers","year":"1998","unstructured":"T. Gowers: A new proof of Szemer\u00e9di's theorem for arithmetic progressions of length four, Geom. Funct. Anal. 8 (1998), 529\u2013551.","journal-title":"Geom. Funct. Anal."},{"key":"3024_CR10","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1016\/j.jcss.2004.04.007","volume":"69","author":"I. Kerenidis","year":"2004","unstructured":"I. Kerenidis and Ronald de Wolf: Exponential lower bound for 2-query locally decodable codes via a quantum argument, J. Comput. System Sci. 69 (2004), 395\u2013420.","journal-title":"J. Comput. System Sci."},{"key":"3024_CR11","first-page":"198","volume-title":"Proceedings of the 50th Annual FOCS","author":"N. Kayal","year":"2009","unstructured":"N. Kayal and S. Saraf: Blackbox polynomial identity testing for depth 3 circuits, in: Proceedings of the 50th Annual FOCS, 198\u2013207, 2009."},{"key":"3024_CR12","doi-asserted-by":"crossref","unstructured":"I. Ruzsa: Sums of finite sets, in: David V. Chudnovsky, G. V. Chudnovsky, and Melvyn B. Nathanson, editors, Number Theory: New York Seminar. Springer Verlag, 1996.","DOI":"10.1007\/978-1-4612-2418-1_21"},{"key":"3024_CR13","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","volume":"27","author":"C. E. Shannon","year":"1948","unstructured":"C. E. Shannon: A mathematical theory of communication, Bell System Technical Journal 27 (1948), 379\u2013423, 623\u2013656.","journal-title":"Bell System Technical Journal"},{"key":"3024_CR14","first-page":"21","volume-title":"Proc. 51st Annual IEEE Symposium on Foundations of Computer Science","author":"N. Saxena","year":"2010","unstructured":"N. Saxena and C. Seshadhri: From Sylvester-Gallai configurations to rank bounds: Improved black-box identity test for depth-3 circuits, in: Proc. 51st Annual IEEE Symposium on Foundations of Computer Science, 21\u201329, 2010."},{"key":"3024_CR15","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1215\/S0012-7094-04-12915-X","volume":"129","author":"B. Sudakov","year":"2005","unstructured":"B. Sudakov, E. Szemer\u00e9di and V. H. Vu: On a question of Erd\u0151s and Moser, Duke Math. J. 129 (2005), 129\u2013155.","journal-title":"Duke Math. J."},{"key":"3024_CR16","first-page":"1","volume":"7","author":"S. Yekhanin","year":"2011","unstructured":"S. Yekhanin: Locally decodable codes, Foundations and Trends in Theoretical Computer Science 7 (2011), 1\u2013117.","journal-title":"Foundations and Trends in Theoretical Computer Science"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-3024-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00493-015-3024-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-015-3024-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T21:32:51Z","timestamp":1559079171000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00493-015-3024-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,28]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["3024"],"URL":"https:\/\/doi.org\/10.1007\/s00493-015-3024-z","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,28]]}}}