{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:44:35Z","timestamp":1725795875430},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_22","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"259-270","source":"Crossref","is-referenced-by-count":0,"title":["Lower Bounds for Approximate LDCs"],"prefix":"10.1007","author":[{"given":"Jop","family":"Bri\u00ebt","sequence":"first","affiliation":[]},{"given":"Zeev","family":"Dvir","sequence":"additional","affiliation":[]},{"given":"Guangda","family":"Hu","sequence":"additional","affiliation":[]},{"given":"Shubhangi","family":"Saraf","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"doi-asserted-by":"crossref","unstructured":"Ai, A., Dvir, Z., Saraf, S., Wigderson, A.: Sylvester-Gallai type theorems for approximate collinearity. Forum of Mathematics, Sigma\u00a04 (2014)","key":"22_CR1","DOI":"10.1017\/fms.2014.1"},{"doi-asserted-by":"crossref","unstructured":"Ben-Aroya, A., Regev, O., de Wolf, R.: A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs. In: FOCS 2008, pp. 477\u2013486 (2008)","key":"22_CR2","DOI":"10.1109\/FOCS.2008.45"},{"doi-asserted-by":"crossref","unstructured":"Barak, B., Dvir, Z., Wigderson, A., Yehudayoff, A.: Fractional Sylvester-Gallai theorems. Proceedings of the National Academy of Sciences (2012)","key":"22_CR3","DOI":"10.1073\/pnas.1203737109"},{"doi-asserted-by":"crossref","unstructured":"Ben-Aroya, A., Efremenko, K., Ta-Shma, A.: Local list decoding with a constant number of queries. In: FOCS 2010, pp. 715\u2013722 (2010)","key":"22_CR4","DOI":"10.1109\/FOCS.2010.88"},{"key":"22_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/3-540-52282-4_30","volume-title":"STACS 90","author":"D. Beaver","year":"1990","unstructured":"Beaver, D., Feigenbaum, J.: Hiding instances in multioracle queries. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol.\u00a0415, pp. 37\u201348. Springer, Heidelberg (1990)"},{"issue":"1","key":"22_CR6","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1145\/200836.200880","volume":"42","author":"M. Blum","year":"1995","unstructured":"Blum, M., Kannan, S.: Designing programs that check their work. J. ACM\u00a042(1), 269\u2013291 (1995)","journal-title":"J. ACM"},{"key":"22_CR7","doi-asserted-by":"publisher","first-page":"120","DOI":"10.3934\/era.2012.19.120","volume":"19","author":"J. Bri\u00ebt","year":"2012","unstructured":"Bri\u00ebt, J., Naor, A., Regev, O.: Locally decodable codes and the failure of cotype for projective tensor products. Electronic Research Announcements in Mathematical Sciences (ERA-MS)\u00a019, 120\u2013130 (2012)","journal-title":"Electronic Research Announcements in Mathematical Sciences (ERA-MS)"},{"unstructured":"Chee, Y., Feng, T., Ling, S., Wang, H., Zhang, L.: Query-efficient locally decodable codes of subexponential length. ECCC, TR10-173 (2010)","key":"22_CR8"},{"issue":"4","key":"22_CR9","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1137\/100804322","volume":"40","author":"Z. Dvir","year":"2011","unstructured":"Dvir, Z., Gopalan, P., Yekhanin, S.: Matching vector codes. SIAM J. Comput.\u00a040(4), 1154\u20131178 (2011)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Dvir, Z., Shpilka, A.: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. In: STOC 2005, pp. 592\u2013601 (2005)","key":"22_CR10","DOI":"10.1145\/1060590.1060678"},{"doi-asserted-by":"crossref","unstructured":"Dvir, Z., Saraf, S., Wigderson, A.: Breaking the quadratic barrier for 3-LCCs over the reals. In: STOC 2014 (2014)","key":"22_CR11","DOI":"10.1145\/2591796.2591818"},{"doi-asserted-by":"crossref","unstructured":"Dvir, Z., Saraf, S., Wigderson, A.: Improved rank bounds for design matrices and a new proof of Kelly\u2019s theorem. Forum of Mathematics, Sigma\u00a04 (2014)","key":"22_CR12","DOI":"10.1017\/fms.2014.2"},{"doi-asserted-by":"crossref","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length. In: STOC 2009, pp. 39\u201344 (2009)","key":"22_CR13","DOI":"10.1145\/1536414.1536422"},{"issue":"3","key":"22_CR14","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00037-006-0216-3","volume":"15","author":"O. Goldreich","year":"2006","unstructured":"Goldreich, O., Karloff, H., Schulman, L.J., Trevisan, L.: Lower bounds for linear locally decodable codes and private information retrieval. Computational Complexity\u00a015(3), 263\u2013296 (2006)","journal-title":"Computational Complexity"},{"doi-asserted-by":"crossref","unstructured":"Itoh, T., Suzuki, Y.: Improved constructions for query-efficient locally decodable codes of subexponential length. IEICE Transactions on Information and Systems E93-D(2), 263\u2013270 (2010)","key":"22_CR15","DOI":"10.1587\/transinf.E93.D.263"},{"issue":"3","key":"22_CR16","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.jcss.2004.04.007","volume":"69","author":"I. Kerenidis","year":"2004","unstructured":"Kerenidis, I., de Wolf, R.: Exponential lower bound for 2-query locally decodable codes via a quantum argument. Journal of Computer and System Sciences\u00a069(3), 395\u2013420 (2004)","journal-title":"Journal of Computer and System Sciences"},{"issue":"10","key":"22_CR17","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1145\/2347736.2347757","volume":"55","author":"G. Kindler","year":"2012","unstructured":"Kindler, G., Rao, A., O\u2019Donnell, R., Wigdersons, A.: Spherical cubes: optimal foams from computational hardness amplification. Commun. ACM\u00a055(10), 90\u201397 (2012)","journal-title":"Commun. ACM"},{"doi-asserted-by":"crossref","unstructured":"Katz, J., Trevisan, L.: On the efficiency of local decoding procedures for error-correcting codes. In: STOC 2000, pp. 80\u201386 (2000)","key":"22_CR18","DOI":"10.1145\/335305.335315"},{"issue":"5","key":"22_CR19","doi-asserted-by":"publisher","first-page":"1952","DOI":"10.1137\/070696519","volume":"38","author":"K.S. Kedlaya","year":"2009","unstructured":"Kedlaya, K.S., Yekhanin, S.: Locally decodable codes from nice subsets of finite fields and prime factors of Mersenne numbers. SIAM J. Comput.\u00a038(5), 1952\u20131969 (2009)","journal-title":"SIAM J. Comput."},{"key":"22_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/3-540-52282-4_44","volume-title":"STACS 90","author":"R.J. Lipton","year":"1990","unstructured":"Lipton, R.J.: Efficient checking of computations. In: Choffrut, C., Lengauer, T. (eds.) STACS 1990. LNCS, vol.\u00a0415, pp. 207\u2013215. Springer, Heidelberg (1990)"},{"unstructured":"Raghavendra, P.: A note on Yekhanin\u2019s locally decodable codes. ECCC, TR07-016 (2007)","key":"22_CR21"},{"unstructured":"Woodruff, D.P.: New lower bounds for general locally decodable codes. ECCC, TR07-006 (2007)","key":"22_CR22"},{"issue":"4","key":"22_CR23","doi-asserted-by":"publisher","first-page":"678","DOI":"10.1007\/s11390-012-1254-8","volume":"27","author":"D.P. Woodruff","year":"2012","unstructured":"Woodruff, D.P.: A quadratic lower bound for three-query linear locally decodable codes over any field. Journal of Computer Science and Technology\u00a027(4), 678\u2013686 (2012)","journal-title":"Journal of Computer Science and Technology"},{"issue":"1","key":"22_CR24","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1326554.1326555","volume":"55","author":"S. Yekhanin","year":"2008","unstructured":"Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. Journal of the ACM\u00a055(1), 1\u201316 (2008)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:32:51Z","timestamp":1558909971000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}