{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:21:02Z","timestamp":1787322062299,"version":"build-2736575974"},"reference-count":12,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>Subsets of $\\mathbb{F}_2^n$ that are $\\varepsilon$-biased, meaning that the parity of any set of bits is even or odd with probability $\\varepsilon$ close to $1\/2$, are powerful tools for derandomization. A simple randomized construction shows that such sets exist of size $O(n\/\\varepsilon^2)$, and known deterministic constructions achieve sets of size $O(n\/\\varepsilon^3)$, $O(n^2\/\\varepsilon^2)$, and $O((n\/\\varepsilon^2)^{5\/4})$. Rather than derandomizing these sets completely in exchange for making them larger, we attempt a partial derandomization while keeping them small, constructing sets of size $O(n\/\\varepsilon^2)$ with as few random bits as possible. Equivalently, we construct small ensembles of error-correcting codes, most of which meet the Gilbert--Varshamov bound. The naive randomized construction requires $O(n^2\/\\varepsilon^2)$ random bits. We give two constructions. The first uses Nisan's space-bounded pseudorandom generator to partly derandomize the classic Wozencraft ensemble of error-correcting codes and requires $O(n \\log (1\/\\varepsilon))$ bits. Our second construction requires $O(n \\log (n\/\\varepsilon))$ bits; it adds randomness to a Legendre symbol construction of Alon, Goldreich, H\\aastad, and Peralta and uses Weil sums to bound high moments of the bias.<\/jats:p>","DOI":"10.1137\/130934490","type":"journal-article","created":{"date-parts":[[2015,7,30]],"date-time":"2015-07-30T15:34:34Z","timestamp":1438270474000},"page":"1303-1311","source":"Crossref","is-referenced-by-count":0,"title":["Optimal $\\varepsilon$-Biased Sets with Just a Little Randomness"],"prefix":"10.1137","volume":"29","author":[{"given":"Cristopher","family":"Moore","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Russell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,7,30]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/0222053"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240030308"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009813"},{"key":"atypb4","unstructured":"M. Cheraghchi, A. Shokrollahi, and A. Wigderson,\n                      Computational hardness and explicit constructions of error correcting codes\n                      , in Proceedings of the Allerton Conference, 2006; available online from http:\/\/infoscience.epfl.ch\/record\/101078\/files\/final.pdf."},{"key":"atypb5","first-page":"191","author":"Ben-Aroya A.","year":"2009","journal-title":"Proceedings of FOCS"},{"key":"atypb6","unstructured":"J. L. Massey,\n                      Threshold Decoding\n                      , Technical report 410, Research Laboratory of Electronics, Massachusetts Institute of Technology, 1963; available online from http:\/\/hdl.handle.net\/1721.1\/4415."},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305237"},{"key":"atypb8","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1145\/301250.301294","author":"Raz R.","year":"1999","journal-title":"Proceedings of STOC"},{"key":"atypb9","first-page":"40","author":"Braverman M.","year":"2010","journal-title":"Proceedings of FOCS"},{"key":"atypb10","first-page":"221","author":"De A.","year":"2011","journal-title":"Proceedings of the IEEE Conference on Computational Complexity"},{"key":"atypb11","first-page":"19","author":"Steinke T.","year":"2012","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"atypb12","unstructured":"M. Naor,\n                      Constructing Ramsey Graphs from Small Probability Spaces\n                      , IBM, New York, 1992; available online from \\burlhttp:\/\/www.wisdom.weizmann.ac.il\/ naor\/PAPERS\/ramsey.ps."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130934490","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:17:43Z","timestamp":1787318263000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130934490"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130934490"],"URL":"https:\/\/doi.org\/10.1137\/130934490","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}