{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T00:33:00Z","timestamp":1794357180261,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540693109","type":"print"},{"value":"9783540693116","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-69311-6_12","type":"book-chapter","created":{"date-parts":[[2008,6,6]],"date-time":"2008-06-06T07:17:46Z","timestamp":1212736666000},"page":"89-100","source":"Crossref","is-referenced-by-count":0,"title":["Absorbing Random Walks and the NAE2SAT Problem"],"prefix":"10.1007","author":[{"given":"K.","family":"Subramani","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H.: On selecting a satisfying truth assignment. In: IEEE (ed.) Proceedings: 32nd annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1\u20134, pp. 163\u2013169. IEEE Computer Society Press, USA (1991)","DOI":"10.1109\/SFCS.1991.185365"},{"key":"12_CR2","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman Company, San Francisco (1979)"},{"issue":"2","key":"12_CR3","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1145\/62.322436","volume":"31","author":"J.H. Reif","year":"1984","unstructured":"Reif, J.H.: Symmetric complementation. J. ACM\u00a031(2), 401\u2013421 (1984)","journal-title":"J. ACM"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Reingold, O.: Undirected st-connectivity in log-space. In: STOC, pp. 376\u2013385 (2005)","DOI":"10.1145\/1060590.1060647"},{"issue":"3","key":"12_CR5","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/0020-0190(79)90002-4","volume":"8","author":"B. Aspvall","year":"1979","unstructured":"Aspvall, B., Plass, M.F., Tarjan, R.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters\u00a08(3), 121\u2013123 (1979)","journal-title":"Information Processing Letters"},{"key":"12_CR6","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"R. Motwani","year":"1995","unstructured":"Motwani, R., Raghavan, P.: Randomized Algorithms. Cambridge University Press, Cambridge (1995)"},{"key":"12_CR7","volume-title":"Probability Models","author":"S.M. Ross","year":"2000","unstructured":"Ross, S.M.: Probability Models, 7th edn. Academic Press, Inc., London (2000)","edition":"7"},{"key":"12_CR8","unstructured":"\u00c0lvarez, C., Greenlaw, R.: A compendium of problems complete for symmetric logarithmic space. Electronic Colloquium on Computational Complexity (ECCC)\u00a03(39) (1996)"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Johannsen, J.: Satisfiability problems complete for deterministic logarithmic space. In: STACS, pp. 317\u2013325 (2004)","DOI":"10.1007\/978-3-540-24749-4_28"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-69311-6_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:34:48Z","timestamp":1620002088000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-69311-6_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540693109","9783540693116"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-69311-6_12","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-540-69311-6","asserted-by":"object"}]},"subject":[]}}