{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T23:13:31Z","timestamp":1725491611070},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540752905"},{"type":"electronic","value":"9783540752929"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-75292-9_31","type":"book-chapter","created":{"date-parts":[[2007,9,11]],"date-time":"2007-09-11T06:43:07Z","timestamp":1189492987000},"page":"455-466","source":"Crossref","is-referenced-by-count":0,"title":["A Randomized Algorithm for BBCSPs in the Prover-Verifier Model"],"prefix":"10.1007","author":[{"given":"K.","family":"Subramani","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"2","key":"31_CR1","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/S0167-6423(99)00007-6","volume":"35","author":"A. Aiken","year":"1999","unstructured":"Aiken, A.: Introduction to set constraint-based program analysis. Science of Computer Programming\u00a035(2), 79\u2013111 (1999)","journal-title":"Science of Computer Programming"},{"issue":"3","key":"31_CR2","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":"31_CR3","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1007\/978-3-540-25984-8_14","volume-title":"Automated Reasoning","author":"L.M. Moura de","year":"2004","unstructured":"de Moura, L.M., Owre, S., Ruess, H., Rushby, J.M., Shankar, N.: The ics decision procedures for embedded deduction. In: Basin, D., Rusinowitch, M. (eds.) IJCAR 2004. LNCS (LNAI), vol.\u00a03097, pp. 218\u2013222. Springer, Heidelberg (2004)"},{"issue":"2","key":"31_CR4","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1145\/201019.201022","volume":"42","author":"D.R. Karger","year":"1995","unstructured":"Karger, D.R., Klein, P.N., Tarjan, R.E.: A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM\u00a042(2), 321\u2013328 (1995)","journal-title":"Journal of the ACM"},{"key":"31_CR5","unstructured":"Khachiyan, L.G.: A polynomial algorithm for linear programming. Soviet Math. Doklady, vol. 20, pp. 191\u2013194 (1979) (Russian original in Doklady Akademiia Nauk SSSR 244, 1093\u20131096)"},{"key":"31_CR6","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5625.001.0001","volume-title":"Programming with Constraints: An Introduction","author":"K. Marriott","year":"1998","unstructured":"Marriott, K., Stuckey, P.J.: Programming with Constraints: An Introduction. The MIT Press, Cambridge (1998)"},{"key":"31_CR7","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, England (1995)"},{"key":"31_CR8","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, pp. 163\u2013169, October 1\u20134 (1991), 1109 Spring Street, Suite 300, Silver Spring, MD 20910, USA. IEEE Computer Society Press, Los Alamitos (1991)","DOI":"10.1109\/SFCS.1991.185365"},{"key":"31_CR9","volume-title":"Probability Models","author":"S.M. Ross","year":"2000","unstructured":"Ross, S.M.: Probability Models, 7th edn. Academic Press, Inc., San Diego (2000)","edition":"7"},{"key":"31_CR10","unstructured":"Schlenker, H., Rehberger, F.: Towards a more general distributed constraint satisfaction framework: Intensional vs. extensional constraint representation. In: 15. WLP, pp. 63\u201370 (2000)"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Sch\u00f6ning, U.: New algorithms for k-SAT based on the local search principle. In: MFCS: Symposium on Mathematical Foundations of Computer Science (2001)","DOI":"10.1007\/3-540-44683-4_9"},{"key":"31_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/11814948_1","volume-title":"Theory and Applications of Satisfiability Testing - SAT 2006","author":"H.M. Sheini","year":"2006","unstructured":"Sheini, H.M., Sakallah, K.A.: From propositional satisfiability to satisfiability modulo theories. In: Biere, A., Gomes, C.P. (eds.) SAT 2006. LNCS, vol.\u00a04121, pp. 1\u20139. Springer, Heidelberg (2006)"},{"key":"31_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1007\/3-540-46002-0_8","volume-title":"Tools and Algorithms for the Construction and Analysis of Systems","author":"K. Subramani","year":"2002","unstructured":"Subramani, K.: An analysis of zero-clairvoyant scheduling. In: Katoen, J.-P., Stevens, P. (eds.) ETAPS 2002 and TACAS 2002. LNCS, vol.\u00a02280, pp. 98\u2013112. Springer, Heidelberg (2002)"},{"issue":"2","key":"31_CR14","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s10951-005-6367-2","volume":"8","author":"K. Subramani","year":"2005","unstructured":"Subramani, K.: An analysis of totally clairvoyant scheduling. Journal of Scheduling\u00a08(2), 113\u2013133 (2005)","journal-title":"Journal of Scheduling"},{"issue":"3","key":"31_CR15","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1142\/S0129054105003182","volume":"16","author":"K. Subramani","year":"2005","unstructured":"Subramani, K.: Cascading random walks. International Journal of Foundations of Computer Science (IJFCS)\u00a016(3), 599\u2013622 (2005)","journal-title":"International Journal of Foundations of Computer Science (IJFCS)"},{"key":"31_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"398","DOI":"10.1007\/11609773_26","volume-title":"Verification, Model Checking, and Abstract Interpretation","author":"K. Subramani","year":"2005","unstructured":"Subramani, K.: Totally clairvoyant scheduling with relative timing constraints. In: Emerson, E.A., Namjoshi, K.S. (eds.) VMCAI 2006. LNCS, vol.\u00a03855, pp. 398\u2013411. Springer, Heidelberg (2005)"},{"issue":"11","key":"31_CR17","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Communications of the ACM\u00a027(11), 1134\u20131142 (1984)","journal-title":"Communications of the ACM"},{"key":"31_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-46135-3_15","volume-title":"Principles and Practice of Constraint Programming - CP 2002","author":"W. Wei","year":"2002","unstructured":"Wei, W., Selman, B.: Accelerating random walks. In: Van Hentenryck, P. (ed.) CP 2002. LNCS, vol.\u00a02470, pp. 216\u2013232. Springer, Heidelberg (2002)"}],"container-title":["Lecture Notes in Computer Science","Theoretical Aspects of Computing \u2013 ICTAC 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-75292-9_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:59:00Z","timestamp":1619506740000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-75292-9_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540752905","9783540752929"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-75292-9_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}