{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,29]],"date-time":"2025-06-29T10:20:58Z","timestamp":1751192458600,"version":"3.38.0"},"reference-count":25,"publisher":"Informa UK Limited","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["International Journal of Computer Mathematics"],"published-print":{"date-parts":[[2011,2]]},"DOI":"10.1080\/00207161003631893","type":"journal-article","created":{"date-parts":[[2010,12,13]],"date-time":"2010-12-13T13:25:47Z","timestamp":1292246747000},"page":"452-467","source":"Crossref","is-referenced-by-count":2,"title":["Absorbing random walks and the NAE2SAT problem"],"prefix":"10.1080","volume":"88","author":[{"given":"K.","family":"Subramani","sequence":"first","affiliation":[]},{"given":"Xiaofeng","family":"Gu","sequence":"additional","affiliation":[]}],"member":"301","reference":[{"key":"CIT0001","volume":"3","author":"\u00c0lvarez C.","year":"1996","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"CIT0002","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., Karp, R. M., Lipton, R. J., Lovasz, L. and Rackoff, C. Random walks, universal traversal sequences and the complexity of maze problems. 20th Annual Symposium on Foundations of Computer Science (FOCS). 29\u201331 October1979, San Juan, Puerto Rico. pp.218\u2013223. Washington, DC: IEEE. Available athttp:\/\/www.computer.org\/portal\/web\/csdl\/doi\/10.1109\/SFCS.1979.34","DOI":"10.1109\/SFCS.1979.34"},{"key":"CIT0003","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90002-4"},{"key":"CIT0004","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04245-8","volume-title":"Computational Geometry \u2013 Algorithms and Applications","author":"de Berg M.","year":"2000","edition":"2"},{"volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","year":"1979","author":"Garey M. R.","key":"CIT0005"},{"key":"CIT0006","unstructured":"D.S. Johnson, Personal Communication"},{"key":"CIT0007","unstructured":"Johannsen, J. Satisfiability problems complete for deterministic logarithmic space. Proceeding of 21st Annual Symposium on Theoretical Aspects of Computer Science, Proceeding. 25\u201327 March, Montpellier, France. Edited by: Diekert, V. and Habib, M. Vol. 2996, pp.317\u2013325. Berlin, Heidelberg: Springer. 2004, STACS 2004, Lecture Notes in Computer Science"},{"key":"CIT0008","doi-asserted-by":"publisher","DOI":"10.1145\/201019.201022"},{"key":"CIT0009","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(82)90058-5"},{"key":"CIT0010","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"Motwani R.","year":"1995"},{"key":"CIT0011","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C. H. On selecting a satisfying truth assignment. Proceedings of the 32nd Annual Symposium on Foundations of Computer Science. 1\u20134 October1991, San Juan, Puerto Rico. Edited by: IEEE. pp.163\u2013169. Washington, DC: IEEE.","DOI":"10.1109\/SFCS.1991.185365"},{"volume-title":"Computational Complexity","year":"1994","author":"Papadimitriou C. H.","key":"CIT0012"},{"key":"CIT0013","doi-asserted-by":"crossref","unstructured":"Paturi, R., Pudl\u00e1k, P., Saks, M. E. and Zane, F. An improved exponential-time algorithm for k-SAT. Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS-98). November, Palo Alto, CA. pp.628\u2013637.","DOI":"10.1109\/SFCS.1998.743513"},{"journal-title":"CJTCS: Chicago J. Theor. Comput. Sci.","year":"1999","author":"Paturi R.","key":"CIT0014"},{"key":"CIT0015","unstructured":"Porschen, S., Randerath, B. and Speckenmeyer, E. Linear time algorithms for some not-all-equal satisfiability problems. Theory and Applications of Satisfiability Testing, 6th International Conference. 5\u20138 May2003, Santa Margherita Ligure, Italy. Edited by: Giunchiglia, E. and Tacchella, A. Vol. 2919, pp.172\u2013187. Berlin, Heidelberg: Springer. SAT 2003, Lecture Notes in Computer Science Available athttp:\/\/www.springerlink.com\/content\/m3qx4w5h6n83bq3g\/"},{"key":"CIT0016","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1145\/62.322436","volume":"31","author":"Reif J. H.","year":"1984","journal-title":"J. Assoc. Comput. Mach."},{"key":"CIT0017","doi-asserted-by":"crossref","unstructured":"Reingold, O. Undirected st-connectivity in log-space. Symposium on the Theory of Computing. pp.376\u2013385.","DOI":"10.1145\/1060590.1060647"},{"key":"CIT0018","volume-title":"Probability Models","author":"Ross S. M.","year":"2000","edition":"7"},{"key":"CIT0019","doi-asserted-by":"crossref","unstructured":"Schoning, U. A probabilistic algorithm for k-SAT and constraint satisfaction problems. Proceedings of 40th symposium on foundations of computer science. pp.410\u2013414. Los Alamos, CA: IEEE Computer Society Press.","DOI":"10.1109\/SFFCS.1999.814612"},{"key":"CIT0020","unstructured":"Sch\u00f6ning, U. New algorithms for k-SAT based on the local search principle. Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001). 27\u201331 August2001, Marianske Lazne, Czech Republic. Edited by: Sgall, J., Pultr, A. and Kolman, P. Vol. 2136, pp.87\u201395. Berlin, Heidelberg: Springer. Lecture Notes in Computer Science"},{"key":"CIT0021","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0094-7"},{"key":"CIT0022","unstructured":"Subramani, K. On Clausal equivalence and Hull inclusion. Proceedings of the 8th Italian Conference on Theoretical Computer Science (ICTCS). 13\u201315 October2003, Bertinoro, Italy. Edited by: Blundo, C. and Laneve, C. Vol. 2841, pp.188\u2013201. Berlin, Heidelberg: Springer. Lecture Notes in Computer Science"},{"key":"CIT0023","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054105003182"},{"key":"CIT0024","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"CIT0025","doi-asserted-by":"crossref","unstructured":"Wei, W. and Selman, B. Accelerating random walks. Proceeding of the 8th International Conference on Principles and Practice of Constraint Programming (CP 2002). 9\u201313 September2002, Ithaca, NY, USA. Edited by: Van Hentenryck, P. Vol. 2470, pp.216\u2013232. Berlin, Heidelberg: Springer. Lecture Notes in Computer Science","DOI":"10.1007\/3-540-46135-3_15"}],"container-title":["International Journal of Computer Mathematics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.tandfonline.com\/doi\/pdf\/10.1080\/00207161003631893","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T18:46:28Z","timestamp":1740768388000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.tandfonline.com\/doi\/abs\/10.1080\/00207161003631893"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,2]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2011,2]]}},"alternative-id":["10.1080\/00207161003631893"],"URL":"https:\/\/doi.org\/10.1080\/00207161003631893","relation":{},"ISSN":["0020-7160","1029-0265"],"issn-type":[{"type":"print","value":"0020-7160"},{"type":"electronic","value":"1029-0265"}],"subject":[],"published":{"date-parts":[[2011,2]]}}}