{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:20:30Z","timestamp":1742617230062,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540632481"},{"type":"electronic","value":"9783540692478"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63248-4_9","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:22:35Z","timestamp":1330298555000},"page":"95-109","source":"Crossref","is-referenced-by-count":0,"title":["Sample spaces with small bias on neighborhoods and error-correcting communication protocols"],"prefix":"10.1007","author":[{"given":"Michael","family":"Saks","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiyu","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/0012-365X(86)90161-5","volume":"58","author":"N. Alon","year":"1986","unstructured":"N. Alon, Explicit constructions of exponential sized families of k-independent sets, Discrete Math, 58, pp 191\u2013193, 1986.","journal-title":"Discrete Math"},{"issue":"4","key":"9_CR2","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1002\/rsa.3240020403","volume":"2","author":"N. Alon","year":"1991","unstructured":"N. Alon, A parallel algorithm version of the Local Lemma, Random Structures and Algorithms 2(4), pp 367\u2013378, 1991.","journal-title":"Random Structures and Algorithms"},{"key":"9_CR3","doi-asserted-by":"crossref","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. Algorithms 7, pp 567\u2013583, 1986.","journal-title":"J. Algorithms"},{"issue":"2","key":"9_CR4","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/18.119713","volume":"38","author":"N. Alon","year":"1992","unstructured":"N. Alon, J. Bruck, J. Naor, M. Naor, R. Roth, Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs, IEEE Trans. on Info. Theory, Vol 38(2), pp 509\u2013515, 1992.","journal-title":"IEEE Trans. on Info. Theory"},{"issue":"3","key":"9_CR5","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","volume":"3","author":"N. Alon","year":"1992","unstructured":"N. Alon, O. Goldreich, J. Hastad, R. Peralta, Simple constructions of almost k-wise independent random variables, Random Structures and Algorithms 3(3), pp 289\u2013303, 1992.","journal-title":"Random Structures and Algorithms"},{"key":"9_CR6","unstructured":"N. Alon, J. Spencer, The Probabilistic Method, Wiley, 1991."},{"issue":"4","key":"9_CR7","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1145\/115234.115347","volume":"38","author":"B. Berger","year":"1991","unstructured":"B. Berger, J. Rompel, Simulating (log c n)-wise independence in NC, J. Assoc. Comput. Mach. 38(4), pp 1026\u20131046, 1991.","journal-title":"J. Assoc. Comput. Mach."},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich, R. Smolensky, The bit extraction problem or t-resilient functions, 26th IEEE FOCS, pp 396\u2013407, 1985.","DOI":"10.1109\/SFCS.1985.55"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"S. Chari, P. Rohatgi, A. Srinivasan, Improved algorithms via approximations of probability distributions, 26th ACM STOC, pp 584\u2013592, 1994.","DOI":"10.1145\/195058.195411"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"G. Even, O. Goldreich, M. Luby, N. Nisan, B. Velickovic, Approximations of general independent distributions, 24th ACM STOC, pp 10\u201316, 1992.","DOI":"10.1145\/129712.129714"},{"key":"9_CR11","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1016\/0097-3165(73)90005-8","volume":"14","author":"P. Erd\u00f6s","year":"1973","unstructured":"P. Erd\u00f6s, J. Selfridge, On a combinatorial game, Journal of Combinatorial Theory, Series A 14, pp 298\u2013301, 1973.","journal-title":"Journal of Combinatorial Theory, Series A"},{"key":"9_CR12","unstructured":"A. Fundia, Derandomizing Chebyshev's inequality to find independent sets in uncrowded hypergraghs, Random Structures and Algorithms, to appear."},{"key":"9_CR13","doi-asserted-by":"crossref","unstructured":"D. Karger and D. Koller, (De)randomized construction of small sample spaces in NC, 35th IEEE FOCS, pp 252\u2013263, 1994.","DOI":"10.1109\/SFCS.1994.365689"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"H. Karloff and Y. Mansour, On construction of k-wise independent random variables, Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 1994.","DOI":"10.1145\/195058.195409"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"R. Karp and A. Wigderson, A fast parallel algorithm for the maximal independent set problem, Proceedings of the 16th Annual ACM Symposium on Theory of Computing, 1984.","DOI":"10.1145\/800057.808690"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"D. Koller and N. Megiddo, Finding small sample spaces satisfying given constraints, Proceedings of the 25th Annual ACM Symposium on Theory of Computing, pp 268\u2013277, 1993.","DOI":"10.1145\/167088.167168"},{"key":"9_CR17","unstructured":"Kuselevitz and N. Nisan, Communication Complexity."},{"key":"9_CR18","doi-asserted-by":"crossref","unstructured":"N. Linial, M. Luby, M. Saks, D. Zuckerman, Efficient construction of a small hitting set for combinatorial rectangles in high dimension, 25th ACM STOC, pp 258\u2013267, 1993.","DOI":"10.1145\/167088.167166"},{"issue":"4","key":"9_CR19","doi-asserted-by":"crossref","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), pp 1036\u20131053, 1986.","journal-title":"SIAM J. Comput."},{"key":"9_CR20","doi-asserted-by":"crossref","unstructured":"R. Motwani, J. Naor, M. Naor, The probabilistic method yields deterministic parallel algorithms, 30th IEEE FOCS, pp 8\u201313, 1989.","DOI":"10.1109\/SFCS.1989.63448"},{"issue":"4","key":"9_CR21","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"J. Naor, M. Naor, Small-bias probability spaces: efficient constructions and applications, SIAM J. Comput. 22(4), pp 838\u2013856, 1993.","journal-title":"SIAM J. Comput."},{"key":"9_CR22","doi-asserted-by":"crossref","unstructured":"M. Naor, L. Schulman, A. Srinivasan, Splitters and near-optimal deran-domization, 36th IEEE FOCS, pp 182\u2013191, 1995.","DOI":"10.1109\/SFCS.1995.492475"},{"key":"9_CR23","first-page":"130","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan, Probabilistic construction of deterministic algorithms: approximating packing integer programs, JCSS 37, pp 130\u2013143, 1988.","journal-title":"JCSS"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"L. Schulman, Sample spaces uniform, on neighborhoods, 24th ACM STOC, pp 17\u201325, 1992.","DOI":"10.1145\/129712.129715"},{"issue":"3","key":"9_CR25","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1109\/18.6031","volume":"34","author":"G. Seroussi","year":"1988","unstructured":"G. Seroussi, N. Bshouty, Vector sets for exhaustive testing of logic circuits, IEEE Trans. on Info. Theory, Vol 34(3), pp 513\u2013522, 1988.","journal-title":"IEEE Trans. on Info. Theory"},{"key":"9_CR26","volume-title":"Ten Lectures on the Probabilistic Method","author":"J. Spencer","year":"1987","unstructured":"J. Spencer, Ten Lectures on the Probabilistic Method, SIAM(Philadelphia), 1987."},{"key":"9_CR27","volume-title":"Ph.D. Thesis","author":"U. Vazirani","year":"1986","unstructured":"U. Vazirani, Randomness, Adversaries and Computation, Ph.D. Thesis, University of California, Berkeley, 1986."},{"key":"9_CR28","doi-asserted-by":"crossref","unstructured":"A. C-C Yao, Some complexity questions related to distributive computing, 11th ACM STOC, pp 209\u2013213, 1979.","DOI":"10.1145\/800135.804414"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63248-4_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:41:41Z","timestamp":1742600501000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63248-4_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540632481","9783540692478"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-63248-4_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}