{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T18:30:45Z","timestamp":1725474645517},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540499947"},{"type":"electronic","value":"9783540499954"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11944836_8","type":"book-chapter","created":{"date-parts":[[2006,11,28]],"date-time":"2006-11-28T04:48:02Z","timestamp":1164689282000},"page":"57-68","source":"Crossref","is-referenced-by-count":7,"title":["One-Input-Face MPCVP Is Hard for L, But in LogDCFL"],"prefix":"10.1007","author":[{"given":"Tanmoy","family":"Chakraborty","sequence":"first","affiliation":[]},{"given":"Samir","family":"Datta","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","unstructured":"Allender, E., Barrington, D.A.M., Chakraborty, T., Datta, S., Roy, S.: Grid Graph Reachability Problems. In: Electronic Colloquium on Computational Complexity, Technical Report TR05-149 (2005)"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/11590156_19","volume-title":"FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science","author":"E. Allender","year":"2005","unstructured":"Allender, E., Datta, S., Roy, S.: The Directed Planar Reachability Problem. In: Ramanujam, R., Sen, S. (eds.) FSTTCS 2005. LNCS, vol.\u00a03821, pp. 238\u2013249. Springer, Heidelberg (2005)"},{"issue":"1","key":"8_CR3","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/j.ic.2003.09.002","volume":"189","author":"E. Allender","year":"2004","unstructured":"Allender, E., Mahajan, M.: The Complexity of Planarity Testing. Information and Computation\u00a0189(1), 117\u2013134 (2004)","journal-title":"Information and Computation"},{"key":"8_CR4","unstructured":"Barrington, D.A.M.: Grid Graph Reachability Problems. In: Dagstuhl Seminar on Complexity of Boolean Functions, Seminar number 02121 (2002)"},{"key":"8_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/BFb0028550","volume-title":"STACS 98","author":"D.A.M. Barrington","year":"1998","unstructured":"Barrington, D.A.M., Lu, C.-J., Miltersen, P.B., Skyum, S.: Searching Constant Width Mazes Captures the AC0 Hierarchy. In: Meinel, C., Morvan, M. (eds.) STACS 1998. LNCS, vol.\u00a01373, pp. 73\u201383. Springer, Heidelberg (1998)"},{"issue":"2","key":"8_CR6","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1137\/S0097539792226278","volume":"24","author":"A.L. Delcher","year":"1995","unstructured":"Delcher, A.L., Kosaraju, S.R.: An NC Algorithm for Evaluating Monotone Planar Circuits. SIAM Journal of Computing\u00a024(2), 369\u2013375 (1995)","journal-title":"SIAM Journal of Computing"},{"issue":"3","key":"8_CR7","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0890-5401(89)90009-6","volume":"80","author":"P.W. Dymond","year":"1989","unstructured":"Dymond, P.W., Cook, S.A.: Complexity Theory of Parallel Time and Hardware. Information and Computation\u00a080(3), 205\u2013226 (1989)","journal-title":"Information and Computation"},{"issue":"3","key":"8_CR8","doi-asserted-by":"publisher","first-page":"400","DOI":"10.1006\/jcss.1997.1485","volume":"54","author":"K. Etessami","year":"1997","unstructured":"Etessami, K.: Counting quantifiers, successor relations, and logarithmic space. Journal of Computer and System Sciences\u00a054(3), 400\u2013411 (1997)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"8_CR9","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1145\/1008354.1008356","volume":"9","author":"L.M. Goldschlager","year":"1977","unstructured":"Goldschlager, L.M.: The Monotone and Planar Circuit Value Problems are Logspace Complete for P. SIGACT News\u00a09(2), 25\u201329 (1977)","journal-title":"SIGACT News"},{"issue":"1","key":"8_CR10","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/0020-0190(80)90117-9","volume":"10","author":"L.M. Goldschlager","year":"1980","unstructured":"Goldschlager, L.M.: A Space-Efficient Algorithm for the Monotone Planar Circuit Value Problem. Information Processing Letters\u00a010(1), 25\u201327 (1980)","journal-title":"Information Processing Letters"},{"key":"8_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/3-540-53487-3_48","volume-title":"Foundations of Software Technology and Theoretical Computer Science","author":"S.R. Kosaraju","year":"1990","unstructured":"Kosaraju, S.R.: On the Parallel Evaluation of Classes of Circuits. In: Veni Madhavan, C.E., Nori, K.V. (eds.) FSTTCS 1990. LNCS, vol.\u00a0472, pp. 232\u2013237. Springer, Heidelberg (1990)"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"Ladner, R.E.: The Circuit Value Problem is Logspace Complete for P. SIGACT News, 18\u201329 (1975)","DOI":"10.1145\/990518.990519"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Limaye, N., Mahajan, M., Sarma, M.N.J.: Evaluating monotone circuits on cylinders, planes, and tori. In Electronic Colloquium on Computational Complexity, Technical Report TR06-009 (2006)","DOI":"10.1007\/11672142_54"},{"key":"8_CR14","first-page":"376","volume-title":"Proceedings of 37th ACM Symposium on Theory of Computing (STOC)","author":"O. Reingold","year":"2005","unstructured":"Reingold, O.: Undirected st-Connectivity in Log-Space. In: Proceedings of 37th ACM Symposium on Theory of Computing (STOC), pp. 376\u2013385. IEEE Computer Society Press, Los Alamitos (2005)"},{"key":"8_CR15","volume-title":"SPDP: 3rd IEEE Symposium on Parallel and Distributed Processing. ACM Special Interest Group on Computer Architecture (SIGARCH)","author":"H. Yang","year":"1991","unstructured":"Yang, H.: An NC Algorithm for the General Planar Monotone Circuit Value Problem. In: SPDP: 3rd IEEE Symposium on Parallel and Distributed Processing. ACM Special Interest Group on Computer Architecture (SIGARCH), IEEE Computer Society, Los Alamitos (1991)"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11944836_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T07:17:53Z","timestamp":1619507873000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11944836_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540499947","9783540499954"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/11944836_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}