{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,20]],"date-time":"2026-03-20T04:12:09Z","timestamp":1773979929077,"version":"3.50.1"},"reference-count":31,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5397,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Random Struct Algorithms"],"published-print":{"date-parts":[[1992,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present three alternative simple constructions of small probability spaces on<jats:italic>n<\/jats:italic>bits for which any<jats:italic>k<\/jats:italic>bits are almost independent. The number of bits used to specify a point in the sample space is (2 +<jats:italic>o<\/jats:italic>(1)) (log log<jats:italic>n<\/jats:italic>+<jats:italic>k<\/jats:italic>\/2 + log<jats:italic>k<\/jats:italic>+ log 1\/\u03f5), where \u03f5 is the statistical difference between the distribution induced on any<jats:italic>k<\/jats:italic>bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by Naor and Naor (our size bound is better as long as \u03f5 &lt; 1\/(<jats:italic>k<\/jats:italic>log<jats:italic>n<\/jats:italic>)). An additional advantage of our constructions is their simplicity.<\/jats:p>","DOI":"10.1002\/rsa.3240030308","type":"journal-article","created":{"date-parts":[[2007,5,26]],"date-time":"2007-05-26T18:23:09Z","timestamp":1180203789000},"page":"289-304","source":"Crossref","is-referenced-by-count":306,"title":["Simple Constructions of Almost k\u2010wise Independent Random Variables"],"prefix":"10.1002","volume":"3","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[]},{"given":"Oded","family":"Goldreich","sequence":"additional","affiliation":[]},{"given":"Johan","family":"H\u00e5stad","sequence":"additional","affiliation":[]},{"given":"Ren\u00e9","family":"Peralta","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"L. M.Adlemanand M\u2010D. A.Huang Recognizing primes in random polynomial time inProc. 19th STOC 1987 pp.462\u2013470.","DOI":"10.1145\/28395.28445"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"M.Ajtai J.Komlos andE.Szemer\u00e9di Deterministic simulation in LOGSPACE inProc. 19th STOC 1987 pp.132\u2013140.","DOI":"10.1145\/28395.28410"},{"key":"e_1_2_1_4_2","unstructured":"N.Alon Unpublished manuscript."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240020403"},{"key":"e_1_2_1_5_3","unstructured":"Also in32nd FOCS 1991 pp.586\u2013593."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.119713"},{"key":"e_1_2_1_8_2","unstructured":"Y.Azar R.Motwani andJ.Naor An efficient construction of a multiple value small bias probability space unpublished manuscript."},{"key":"e_1_2_1_9_2","unstructured":"M.Bellare O.Goldreich andS.GoldwasserRandomness in interactive proofs in31st FOCS 1990 pp.318\u2013326."},{"key":"e_1_2_1_10_2","unstructured":"R.Ben\u2010Natan On dependent random variables over small sample spaces M.Sc. thesis Computer Science Dept. Hebrew University Jerusalem Israel February1990."},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"J.Boyar G.Brassard andR.Peralta Subquadratic zero\u2010knowledge in32nd FOCS 1991 pp.69\u201378.","DOI":"10.1109\/SFCS.1991.185350"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"B.Chor J.Friedmann O.Goldreich J.Hastad S.Rudish andR.Smolensky The bit extraction problem andt\u2010resilient functions inProc. 26th FOCS 1985 pp.396\u2013407.","DOI":"10.1109\/SFCS.1985.55"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(89)90015-0"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"A.CohenandA.Wigderson Dispensers deterministic amplification and weak random sources in30th FOCS 1989 pp.14\u201319.","DOI":"10.1109\/SFCS.1989.63449"},{"key":"e_1_2_1_15_2","unstructured":"G.Even private communication May1990; to be included in his M.Sc. thesis to be submitted to the Computer Science Dept. Technion Israel."},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"U.Feige S.Goldwasser L.Lovasz S.Safra andM.Szegedy Approximating clique is almost NP\u2010complete in32nd FOCS 1991 pp.2\u201312.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(81)90040-4"},{"key":"e_1_2_1_18_2","doi-asserted-by":"crossref","unstructured":"O.Goldreich R.Impagliazzo L. A.Levin R.Venkatesan andD.Zuckerman Security preserving amplification of hardness in31st FOCS 1990 pp.318\u2013326.","DOI":"10.1109\/FSCS.1990.89550"},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","unstructured":"S.GoldwasserandJ.Kilian Almost all primes can be quickly certified inProc. 18th STOC 1986 pp.316\u2013329.","DOI":"10.1145\/12130.12162"},{"key":"e_1_2_1_20_2","volume-title":"Shift Register Sequences","author":"Golomb S. W.","year":"1982"},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"R.ImpagliazzoandD.Zuckerman How to recycle random bits in30th FOCS 1989 pp.248\u2013253.","DOI":"10.1109\/SFCS.1989.63486"},{"key":"e_1_2_1_22_2","doi-asserted-by":"crossref","unstructured":"M.Luby A simple parallel algorithm for the maximal independent set problem inProc. 17th STOC 1985 pp.1\u201310.","DOI":"10.1145\/22145.22146"},{"key":"e_1_2_1_23_2","doi-asserted-by":"crossref","unstructured":"A.Lubotzky R.Phillips andP.Sarnak Explicit expanders and the Ramanujan conjectures inProc. 18th STOC 1986 pp.240\u2013246.","DOI":"10.1145\/12130.12154"},{"key":"e_1_2_1_24_2","volume-title":"The Theory of Error\u2010Correcting Codes","author":"MacWilliams F. J.","year":"1977"},{"key":"e_1_2_1_25_2","doi-asserted-by":"crossref","unstructured":"K.Mulmuley U. V.VaziraniandV. V.Vazirani Matchning is as easy as matrix inversion inProc. 19th STOC 1987 pp.345\u2013354.","DOI":"10.1145\/28395.383347"},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"J.NaorandM.Naor Small\u2010bias probability spaces: Efficient constructions and applications in22nd STOC 1990 pp.213\u2013223.","DOI":"10.1145\/100216.100244"},{"key":"e_1_2_1_27_2","doi-asserted-by":"crossref","unstructured":"M. O.Rabin Probabilistic algorithms for testing primality J. Num. Theor 128\u2013138(1980).","DOI":"10.1016\/0022-314X(80)90084-0"},{"key":"e_1_2_1_28_2","volume-title":"Lecture Notes in Mathematics","author":"Schmidt W. M.","year":"1976"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206006"},{"key":"e_1_2_1_30_2","unstructured":"U. V.Vazirani Randomness adversaries and computation Ph.D. thesis EECS University of California Berkeley 1986."},{"key":"e_1_2_1_31_2","doi-asserted-by":"crossref","unstructured":"U. V.VaziraniandV. V.Vazirani Efficient and secure pseudo\u2010random number generation inProc. 25th FOCS 1984 pp.458\u2013463.","DOI":"10.1109\/SFCS.1984.715948"}],"container-title":["Random Structures &amp; Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Frsa.3240030308","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/rsa.3240030308","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T18:21:47Z","timestamp":1737051707000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/rsa.3240030308"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,1]]},"references-count":31,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,1]]}},"alternative-id":["10.1002\/rsa.3240030308"],"URL":"https:\/\/doi.org\/10.1002\/rsa.3240030308","archive":["Portico"],"relation":{},"ISSN":["1042-9832","1098-2418"],"issn-type":[{"value":"1042-9832","type":"print"},{"value":"1098-2418","type":"electronic"}],"subject":[],"published":{"date-parts":[[1992,1]]}}}