{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:56:11Z","timestamp":1725663371680},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540529217"},{"type":"electronic","value":"9783540471776"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1990]]},"DOI":"10.1007\/3-540-52921-7_82","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T21:49:15Z","timestamp":1330206555000},"page":"328-337","source":"Crossref","is-referenced-by-count":2,"title":["Derandomization by exploiting redundancy and mutual independence"],"prefix":"10.1007","author":[{"given":"Yijie","family":"Han","sequence":"first","affiliation":[]},{"given":"Yoshihide","family":"Igarashi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"34_CR1","doi-asserted-by":"crossref","unstructured":"M. Ajtai, J. Koml\u00f3s, and E. Szemer\u00e9di. An O(N log N) sorting network. Proc. 15th ACM Symp. on Theory of Computing, 1\u20139(1983).","DOI":"10.1145\/800061.808726"},{"key":"34_CR2","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"N. Alon, L. Babai, A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. of Algorithms 7, 567\u2013583(1986).","journal-title":"J. of Algorithms"},{"key":"34_CR3","unstructured":"S. Bernstein, \u201cTheory of Probability,\u201d GTTI, Moscow 1945."},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"R. A. Borodin and J. E. Hopcroft. Routing, merging and sorting on parallel models of computation. Proc. 14th ACM Symp. on Theory of Computing, 1982, pp. 338\u2013344.","DOI":"10.1145\/800070.802209"},{"key":"34_CR5","unstructured":"B. Berger, J. Rompel. Simulating (log c n)-wise independence in NC. Proc. 1989 IEEE FOCS, 2\u20137."},{"key":"34_CR6","unstructured":"B. Berger, J. Rompel, P. Shor. Efficient NC algorithms for set cover with applications to learning and geometry. Proc. 1989 IEEE FOCS, 54\u201359."},{"key":"34_CR7","doi-asserted-by":"crossref","unstructured":"R. Cole. Parallel merge sort. 27th Symp. on Foundations of Comput. Sci., IEEE, 511\u2013516(1986).","DOI":"10.1109\/SFCS.1986.41"},{"key":"34_CR8","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1214\/aop\/1176996762","volume":"2","author":"A. Joffe","year":"1974","unstructured":"A. Joffe. On a set of almost deterministic k-independent random variables. Ann. Probability 2(1974), 161\u2013162.","journal-title":"Ann. Probability"},{"issue":"4","key":"34_CR9","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"R. Karp","year":"1985","unstructured":"R. Karp, A. Wigderson. A fast parallel algorithm for the maximal independent set problem. JACM 32:4, Oct. 1985, 762\u2013773.","journal-title":"JACM"},{"key":"34_CR10","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1214\/aoms\/1177700007","volume":"36","author":"H. O. Lancaster","year":"1965","unstructured":"H. O. Lancaster. Pairwise statistical independence, Ann. Math. Stat. 36(1965), 1313\u20131317.","journal-title":"Ann. Math. Stat."},{"issue":"4","key":"34_CR11","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"M. Luby. A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15:4, Nov. 1986, 1036\u20131053.","journal-title":"SIAM J. Comput."},{"key":"34_CR12","doi-asserted-by":"crossref","unstructured":"M. Luby. Removing randomness in parallel computation without a processor penalty. Proc. 1988 IEEE FOCS, 162\u2013173.","DOI":"10.1109\/SFCS.1988.21934"},{"key":"34_CR13","doi-asserted-by":"crossref","unstructured":"G. L. Miller and J. H. Reif. Parallel tree contraction and its application. Proc. 26th Symp. on Foundations of Computer Science, IEEE, 478\u2013489(1985).","DOI":"10.1109\/SFCS.1985.43"},{"key":"34_CR14","unstructured":"R. Motwani, J. Naor, M. Naor. The probabilistic method yields deterministic parallel algorithms. Proc. 1989 IEEE FOCS, 8\u201313."},{"key":"34_CR15","doi-asserted-by":"crossref","unstructured":"G. Pantziou, P. Spirakis, C. Zaroliagis. Fast parallel approximations of the maximum weighted cut problem through Derandomization. FST&TCS 9: 1989, Bangalore, India, LNCS 405, 20\u201329.","DOI":"10.1007\/3-540-52048-1_29"},{"issue":"4","key":"34_CR16","first-page":"130","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan. Probabilistic construction of deterministic algorithms: approximating packing integer programs. JCSS 37:4, Oct. 1988, 130\u2013143.","journal-title":"JCSS"},{"issue":"3","key":"34_CR17","doi-asserted-by":"publisher","first-page":"688","DOI":"10.1137\/0214051","volume":"14","author":"M. Snir","year":"1985","unstructured":"M. Snir. On parallel searching. SIAM J. Comput. 14, 3(Aug. 1985), pp. 688\u2013708.","journal-title":"SIAM J. Comput."},{"key":"34_CR18","volume-title":"Ten Lectures on the Probabilistic Method","author":"J. Spencer","year":"1987","unstructured":"J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, Philadephia, 1987."}],"container-title":["Lecture Notes in Computer Science","Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-52921-7_82.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:25:52Z","timestamp":1605648352000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-52921-7_82"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990]]},"ISBN":["9783540529217","9783540471776"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-52921-7_82","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1990]]}}}