{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:35Z","timestamp":1725664715387},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540614227"},{"type":"electronic","value":"9783540685296"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-61422-2_115","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:36:41Z","timestamp":1330292201000},"page":"1-3","source":"Crossref","is-referenced-by-count":0,"title":["Derandomization via small sample spaces"],"prefix":"10.1007","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"1_CR1","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 and A. Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Alg., 7:567\u2013583, 1986.","journal-title":"J. Alg."},{"key":"1_CR2","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 and R. Roth. Construction of asymptotically good, low-rate error-correcting codes through pseudo-random graphs. IEEE Trans. Info. Theory, 38:509\u2013516, 1992.","journal-title":"IEEE Trans. Info. Theory"},{"issue":"3","key":"1_CR3","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. H\u00e5stad and R. Peralta. Simple constructions of almost k-wise independent random variables. Random Structures and Algorithms, 3(3):289\u2013303, 1992.","journal-title":"Random Structures and Algorithms"},{"doi-asserted-by":"crossref","unstructured":"N. Alon, Y. Matias and M. Szegedy. The space complexity of approximating the frequency moments. In Proc. of the 28th ACM Symp. on Theory of Computing, 1996, in press.","key":"1_CR4","DOI":"10.1145\/237814.237823"},{"unstructured":"N. Alon and M. Naor. Derandomization, witnesses for Boolean matrix multiplication and construction of perfect hash functions. To appear in Algorithmica.","key":"1_CR5"},{"unstructured":"N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, 1992.","key":"1_CR6"},{"key":"1_CR7","doi-asserted-by":"crossref","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N. Alon","year":"1995","unstructured":"N. Alon, R. Yuster and U. Zwick. Color-coding. J. ACM 42:844\u2013856, 1995.","journal-title":"J. ACM"},{"unstructured":"Y. Azar, R. Motwani and J. Naor. Approximating arbitrary probability distributions using small sample spaces. Manuscript, 1990.","key":"1_CR8"},{"key":"1_CR9","doi-asserted-by":"crossref","first-page":"1026","DOI":"10.1145\/115234.115347","volume":"38","author":"B. Berger","year":"1991","unstructured":"B. Berger and J. Rompel. Simulating (logc n)-wise independence in NC. Journal of the ACM, 38:1026\u20131046, 1991.","journal-title":"Journal of the ACM"},{"doi-asserted-by":"crossref","unstructured":"B. Berger, J. Rompel and P. W. Shor. Efficient NC algorithms for set cover with applications to learning and geometry. In Proc. 30th IEEE Symposium on Foundations of Computer Science, pages 54\u201359, 1989.","key":"1_CR10","DOI":"10.1109\/SFCS.1989.63455"},{"key":"1_CR11","volume-title":"Theory of Probability","author":"S. Bernstein","year":"1945","unstructured":"S. Bernstein. Theory of Probability (3rd Edition). GTTI, Moscow, 1945.","edition":"3rd Edition"},{"doi-asserted-by":"crossref","unstructured":"B. Chor, O. Goldreich, J. Hastad, J. Friedman, S. Rudich and R. Smolensky. The Bit Extraction Problem or t-Resilient Functions. In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, pages 396\u2013407, 1985.","key":"1_CR12","DOI":"10.1109\/SFCS.1985.55"},{"doi-asserted-by":"crossref","unstructured":"S. Chari, P. Rohatgi and A. Srinivasan. Improved algorithms via approximations of probability distributions. In Proc. 26th ACM Symposium on Theory of Computing, pages 584\u2013592, 1994.","key":"1_CR13","DOI":"10.1145\/195058.195411"},{"key":"1_CR14","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","volume":"18","author":"L. Carter","year":"1979","unstructured":"L. Carter and M. Wegman. Universal classes of Hash functions. J. Computer System Sciences, 18:143\u2013154, 1979.","journal-title":"J. Computer System Sciences"},{"doi-asserted-by":"crossref","unstructured":"G. Even, O. Goldreich, M. Luby, N. Nisan and B. Veli\u0107kovi\u0107. Approximations of general independent distributions. In Proc. 24th ACM Symposium on Theory of Computing, pages 10\u201316, 1992.","key":"1_CR15","DOI":"10.1145\/129712.129714"},{"doi-asserted-by":"crossref","unstructured":"J. Friedman. On the bit extraction problem. In Proc. 33rd IEEE Symposium on Foundations of Computer Science, pages 314\u2013319, 1992.","key":"1_CR16","DOI":"10.1109\/SFCS.1992.267760"},{"doi-asserted-by":"crossref","unstructured":"M. Fredman, J. Komlos and E. Szemer\u00e9di. Storing a sparse table with O(1) worst-case access time. In Proc. 23rd IEEE Symposium on Foundations of Computer Science, pages 165\u2013169, 1982.","key":"1_CR17","DOI":"10.1109\/SFCS.1982.39"},{"doi-asserted-by":"crossref","unstructured":"M. T. Goodrich. Geometric partitioning made easier, even in parallel. In Proc. 9th ACM Symp. Comput. Geom., pages 73\u201382, 1993.","key":"1_CR18","DOI":"10.1145\/160985.161002"},{"key":"1_CR19","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. Annals of Probability, 2:161\u2013162, 1974.","journal-title":"Annals of Probability"},{"doi-asserted-by":"crossref","unstructured":"D. Koller and N. Megiddo, Constructing small sample spaces satisfying given constraints. In Proc. of the 25th Annual ACM Symposium on Theory of Computing, pages 268\u2013277, 1993.","key":"1_CR20","DOI":"10.1145\/167088.167168"},{"doi-asserted-by":"crossref","unstructured":"H. Karloff and Y. Mansour. On construction of k-wise independent random variables. In Proc. of the 26th Annual ACM Symposium on Theory of Computing, pages 564\u2013573, 1994.","key":"1_CR21","DOI":"10.1145\/195058.195409"},{"key":"1_CR22","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/4221.4226","volume":"32","author":"R. Karp","year":"1985","unstructured":"R. Karp and A. Wigderson. A fast parallel algorithm for the maximum independent set problem. J. ACM, 32: 762\u2013773, 1985.","journal-title":"J. ACM"},{"key":"1_CR23","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:1313\u20131317, 1965.","journal-title":"Ann. Math. Stat."},{"issue":"4","key":"1_CR24","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):1036\u20131053, 1986.","journal-title":"SIAM J. Comput."},{"issue":"2","key":"1_CR25","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1016\/0022-0000(93)90033-S","volume":"47","author":"M. Luby","year":"1993","unstructured":"M. Luby. Removing randomness in parallel computation without a processor penalty. J. Comput. Syst. Sci., 47(2):250\u2013286, 1993.","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR26","doi-asserted-by":"crossref","first-page":"478","DOI":"10.1016\/S0022-0000(05)80069-8","volume":"49","author":"R. Motwani","year":"1994","unstructured":"R. Motwani, J. Naor and M. Naor. The probabilistic method yields deterministic parallel algorithms. J. Comput. Syst. Sci., 49:478\u2013516, 1994.","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR27","volume-title":"The Theory of Error-Correcting Codes","author":"F. J. MacWilliams","year":"1977","unstructured":"F. J. MacWilliams and N. J. A. Sloane. The Theory of Error-Correcting Codes. North Holland, Amsterdam, 1977."},{"issue":"4","key":"1_CR28","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","volume":"22","author":"J. Naor","year":"1993","unstructured":"J. Naor and M. Naor. Small-bias probability spaces: efficient constructions and applications. SIAM J. Comput., 22(4):838\u2013856, 1993.","journal-title":"SIAM J. Comput."},{"key":"1_CR29","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","volume":"37","author":"P. Raghavan","year":"1988","unstructured":"P. Raghavan. Probabilistic construction of deterministic algorithms: approximating packing integer programs. J. Comput. Syst. Sci., 37:130\u2013143, 1988.","journal-title":"J. Comput. Syst. Sci."},{"key":"1_CR30","doi-asserted-by":"crossref","first-page":"128","DOI":"10.2307\/2983576","volume":"9","author":"C. R. Rao","year":"1947","unstructured":"C. R. Rao. Factorial experiments derivable from combinatorial arrangements of arrays. J. Royal Stat. Soc. 9: 128\u2013139, 1947.","journal-title":"J. Royal Stat. Soc."},{"doi-asserted-by":"crossref","unstructured":"L. J. Schulman. Sample spaces uniform on neighborhoods. In Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pages 17\u201325, 1992.","key":"1_CR31","DOI":"10.1145\/129712.129715"},{"unstructured":"J. Spencer. Ten Lectures on the Probabilistic Method. SIAM, 1987.","key":"1_CR32"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2014 SWAT'96"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-61422-2_115.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,20]],"date-time":"2024-04-20T17:27:16Z","timestamp":1713634036000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-61422-2_115"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540614227","9783540685296"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/3-540-61422-2_115","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]}}}