{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:26Z","timestamp":1759638986731,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476710"},{"type":"electronic","value":"9783662476727"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47672-7_54","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T10:07:39Z","timestamp":1434708459000},"page":"666-677","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs"],"prefix":"10.1007","author":[{"given":"Oded","family":"Goldreich","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tom","family":"Gur","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ron D.","family":"Rothblum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"issue":"6","key":"54_CR1","doi-asserted-by":"publisher","first-page":"1842","DOI":"10.1137\/S0097539700366528","volume":"30","author":"N Alon","year":"2000","unstructured":"Alon, N., Krivelevich, M., Newman, I., Szegedy, M.: Regular languages are testable with a constant number of queries. SIAM J. Comput. 30(6), 1842\u20131862 (2000)","journal-title":"SIAM J. Comput."},{"key":"54_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1007\/11537311_23","volume-title":"Fundamentals of Computation Theory","author":"B Bollig","year":"2005","unstructured":"Bollig, B.: Property testing and the branching program size of boolean functions. In: Li\u015bkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 258\u2013269. Springer, Heidelberg (2005)"},{"issue":"4","key":"54_CR3","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"E Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput. 36(4), 889\u2013974 (2006)","journal-title":"SIAM J. Comput."},{"key":"54_CR4","doi-asserted-by":"crossref","unstructured":"Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing, pp. 151\u2013158. ACM (1971)","DOI":"10.1145\/800157.805047"},{"issue":"4","key":"54_CR5","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1137\/S0097539705446962","volume":"36","author":"I Dinur","year":"2006","unstructured":"Dinur, I., Reingold, O.: Assignment testers: Towards a combinatorial proof of the PCP theorem. SIAM J. Comput. 36(4), 975\u20131024 (2006)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"54_CR6","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.ic.2003.09.005","volume":"189","author":"F Erg\u00fcn","year":"2004","unstructured":"Erg\u00fcn, F., Kumar, R., Rubinfeld, R.: Fast approximate probabilistically checkable proofs. Inf. Comput. 189(2), 135\u2013159 (2004)","journal-title":"Inf. Comput."},{"key":"54_CR7","doi-asserted-by":"crossref","unstructured":"Fischer, E., Goldhirsh, Y., Lachish, O.: Partial tests, universal tests and decomposability. In: Innovations in Theoretical Computer Science, ITCS 2014, Princeton, NJ, USA, January 12\u201314, pp. 483\u2013500 (2014)","DOI":"10.1145\/2554797.2554841"},{"issue":"4","key":"54_CR8","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM (JACM) 45(4), 653\u2013750 (1998)","journal-title":"Journal of the ACM (JACM)"},{"key":"54_CR9","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Gur, T., Rothblum, R.D.: Proofs of proximity for context-free languages and read-once branching programs. Electronic Colloquium on Computational Complexity (ECCC) 22, 24 (2015)","DOI":"10.1007\/978-3-662-47672-7_54"},{"issue":"2","key":"54_CR10","doi-asserted-by":"publisher","first-page":"534","DOI":"10.1137\/100789646","volume":"40","author":"O Goldreich","year":"2011","unstructured":"Goldreich, O., Ron, D.: On proximity-oblivious testing. SIAM Journal on Computing 40(2), 534\u2013566 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"54_CR11","doi-asserted-by":"crossref","unstructured":"Gur, T., Rothblum, R.D.: Non-interactive proofs of proximity. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, pp. 133\u2013142. ACM (2015)","DOI":"10.1145\/2688073.2688079"},{"key":"54_CR12","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"2006","unstructured":"Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation, 3rd edn. Addison-Wesley Longman Publishing Co. Inc., Boston (2006)","edition":"3"},{"key":"54_CR13","doi-asserted-by":"crossref","unstructured":"Tauman Kalai, Y., Rothblum, R.D.: Arguments of proximity (2014) (manuscript)","DOI":"10.1007\/978-3-662-48000-7_21"},{"issue":"4","key":"54_CR14","first-page":"447","volume":"22","author":"K Kriegel","year":"1988","unstructured":"Kriegel, K., Waack, S.: Lower bounds on the complexity of real-time branching programs. ITA 22(4), 447\u2013459 (1988)","journal-title":"ITA"},{"key":"54_CR15","doi-asserted-by":"crossref","unstructured":"Lewis, P.M., Stearns, R.E., Hartmanis, J.: Memory bounds for recognition of context-free and context-sensitive languages. In: SWCT (FOCS), pp. 191\u2013202 (1965)","DOI":"10.1109\/FOCS.1965.14"},{"issue":"5","key":"54_CR16","doi-asserted-by":"publisher","first-page":"1557","DOI":"10.1137\/S009753970038211X","volume":"31","author":"I Newman","year":"2002","unstructured":"Newman, I.: Testing membership in languages that have small width branching programs. SIAM Journal on Computing 31(5), 1557\u20131570 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"54_CR17","doi-asserted-by":"crossref","unstructured":"Parnas, M., Ron, D., Rubinfeld, R.: Testing parenthesis languages. In: Goemans, M.X., Jansen, K., Rolim, J.D.P., Trevisan, L. (eds.) RANDOM-APPROX 2001. LNCS, vol. 2129, pp. 261\u2013272. Springer, Heidelberg (2001)","DOI":"10.1007\/3-540-44666-4_29"},{"issue":"2","key":"54_CR18","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. Comput. 25(2), 252\u2013271 (1996)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"54_CR19","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0022-0000(81)90038-6","volume":"22","author":"WL Ruzzo","year":"1981","unstructured":"Ruzzo, W.L.: On uniform circuit complexity. J. Comput. Syst. Sci. 22(3), 365\u2013383 (1981)","journal-title":"J. Comput. Syst. Sci."},{"key":"54_CR20","doi-asserted-by":"crossref","unstructured":"Rothblum, G.N., Vadhan, S., Wigderson, A.: Interactive proofs of proximity: Delegating computation in sublinear time. In: Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC) (2013)","DOI":"10.1145\/2488608.2488709"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47672-7_54","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:14:22Z","timestamp":1676945662000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47672-7_54"}},"subtitle":["(Extended Abstract)"],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476710","9783662476727"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47672-7_54","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}