{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,3]],"date-time":"2026-05-03T03:06:09Z","timestamp":1777777569323,"version":"3.51.4"},"reference-count":428,"publisher":"Emerald","issue":"1-3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012,12,20]]},"abstract":"<jats:p>This is a survey of pseudorandomness, the theory of efficiently generating objects that \"look random\" despite being constructed using little or no randomness. This theory has significance for a number of areas in computer science and mathematics, including computational complexity, algorithms, cryptography, combinatorics, communications, and additive number theory. Our treatment places particular emphasis on the intimate connections that have been discovered between a variety of fundamental \"pseudorandom objects\" that at first seem very different in nature: expander graphs, randomness extractors, list-decodable error-correcting codes, samplers, and pseudorandom generators. The structure of the presentation is meant to be suitable for teaching in a graduate-level course, with exercises accompanying each section.<\/jats:p>","DOI":"10.1561\/0400000010","type":"journal-article","created":{"date-parts":[[2012,12,20]],"date-time":"2012-12-20T10:59:55Z","timestamp":1356001195000},"page":"1-336","source":"Crossref","is-referenced-by-count":203,"title":["Pseudorandomness"],"prefix":"10.1108","volume":"7","author":[{"given":"Salil P.","family":"Vadhan","sequence":"first","affiliation":[{"name":"Harvard University School of Engineering and Applied Sciences, , Cambridge, MA, 02138,","place":["USA"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","published-online":{"date-parts":[[2012,12,20]]},"reference":[{"key":"2026040314135210000_ref001","author":"Aaronson"},{"issue":"1","key":"2026040314135210000_ref002","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/0022-0000(89)90018-4","article-title":"On hiding\n      information from an oracle","volume":"39","author":"Abadi","journal-title":"Journal of Computer and System\n      Sciences"},{"key":"2026040314135210000_ref003","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1109\/SFCS.1978.37","article-title":"Two theorems\n      on random polynomial time","author":"Adleman","year":"1978","journal-title":"Annual Symposium on Foundations\n      of Computer Science (Ann Arbor, Mich., 1978)"},{"key":"2026040314135210000_ref004","first-page":"355","article-title":"On\n      derandomizing tests for certain polynomial identities","author":"Agrawal","year":"2003","journal-title":"IEEE\n      Conference on Computational Complexity"},{"issue":"4","key":"2026040314135210000_ref005","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1145\/792538.792540","article-title":"Primality and\n      identity testing via Chinese remaindering","volume":"50","author":"Agrawal","journal-title":"Journal of the\n      ACM"},{"issue":"2","key":"2026040314135210000_ref006","doi-asserted-by":"crossref","first-page":"781","DOI":"10.4007\/annals.2004.160.781","article-title":"PRIMES is in\n      P","volume":"160","author":"Agrawal","journal-title":"Annals of Mathematics. Second Series"},{"key":"2026040314135210000_ref007","first-page":"67","article-title":"Arithmetic\n      circuits: A chasm at depth four","author":"Agrawal","year":"2008","journal-title":"FOCS"},{"key":"2026040314135210000_ref008","author":"Aho"},{"issue":"6","key":"2026040314135210000_ref009","doi-asserted-by":"crossref","first-page":"583","DOI":"10.1112\/blms\/22.6.583","article-title":"Construction of a thin set with small Fourier\n      coefficients","volume":"22","author":"Ajtai","journal-title":"Bulletin of the London Mathematical\n      Society"},{"issue":"1","key":"2026040314135210000_ref010","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02579338","article-title":"Sorting in\n       clogn parallel steps","volume":"3","author":"Ajtai","journal-title":"Combinatorica"},{"key":"2026040314135210000_ref011","first-page":"132","article-title":"Deterministic Simulation in LOGSPACE","author":"Ajtai","year":"1987","journal-title":"Annual ACM Symposium on Theory of Computing"},{"key":"2026040314135210000_ref012","article-title":"Deterministic simulation of probabilistic constant depth\n      circuits","author":"Ajtai","journal-title":"Randomness and Computation"},{"key":"2026040314135210000_ref013","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1109\/SFCS.1979.34","article-title":"Random walks,\n      universal traversal sequences, and the complexity of maze problems","author":"Aleliunas","year":"1979","journal-title":"Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico,\n      1979)"},{"key":"2026040314135210000_ref014","author":"Allender"},{"issue":"2","key":"2026040314135210000_ref015","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02579166","article-title":"Eigenvalues and\n      expanders","volume":"6","author":"Alon","journal-title":"Combinatorica"},{"issue":"3","key":"2026040314135210000_ref016","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/BF02579382","article-title":"Eigenvalues,\n      geometric expanders, sorting in rounds, and Ramsey theory","volume":"6","author":"Alon","journal-title":"Combinatorica"},{"key":"2026040314135210000_ref017","first-page":"73","article-title":"Explicit\n      unique-neighbor expanders","author":"Alon","year":"2002","journal-title":"Symposium on Foundations of\n      Computer Science (Vancouver, BC, 2002)"},{"issue":"72-1","key":"2026040314135210000_ref018","first-page":"15","article-title":"Explicit\n      construction of linear sized tolerant networks","volume":"72","author":"Alon","journal-title":"Discrete\n      Mathematics"},{"issue":"3","key":"2026040314135210000_ref019","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1002\/rsa.3240030308","article-title":"Simple\n      constructions of almost k-wise independent random\n     variables","volume":"3","author":"Alon","journal-title":"Random Structures & Algorithms"},{"issue":"4","key":"2026040314135210000_ref020","doi-asserted-by":"crossref","DOI":"10.1145\/1290672.1290679","article-title":"Guessing\n      secrets efficiently via list decoding","volume":"3","author":"Alon","journal-title":"ACM Transactions on\n      Algorithms"},{"issue":"6","key":"2026040314135210000_ref021","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/0020-0190(95)00032-8","article-title":"e-discrepancy sets and their application for\n      interpolation of sparse polynomials","volume":"54","author":"Alon","journal-title":"Information Processing\n      Letters"},{"issue":"1","key":"2026040314135210000_ref022","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1006\/jcss.1997.1545","article-title":"The space\n      complexity of approximating the frequency moments","volume":"58","author":"Alon","journal-title":"Journal of\n      Computer and System Sciences"},{"key":"2026040314135210000_ref023","first-page":"320","article-title":"Eigenvalues,\n      expanders and superconcentrators (Extended Abstract)","author":"Alon","year":"1984","journal-title":"Annual Symposium on Foundations of Computer Science"},{"issue":"2","key":"2026040314135210000_ref024","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1002\/rsa.3240050203","article-title":"Random\n      Cayley graphs and expanders","volume":"5","author":"Alon","journal-title":"Random Structures and\n      Algorithms"},{"key":"2026040314135210000_ref025","author":"Alon","journal-title":"The Probabilistic Method.\n      Wiley-Interscience Series in Discrete Mathematics and Optimization"},{"key":"2026040314135210000_ref026","author":"Alon"},{"key":"2026040314135210000_ref027","article-title":"Worst-case\n      hardness suffices for derandomization: A new method for hardness-randomness\n      trade-offs","author":"Andreev","journal-title":"Automata, Languages and Programming, 24th\n      International Colloquium"},{"issue":"6","key":"2026040314135210000_ref028","doi-asserted-by":"crossref","first-page":"2103","DOI":"10.1137\/S0097539797325636","article-title":"Weak random\n      sources, hitting sets, and BPP simulations","volume":"28","author":"Andreev","journal-title":"SIAM Journal on\n      Computing"},{"key":"2026040314135210000_ref029","author":"Angluin"},{"issue":"2","key":"2026040314135210000_ref030","doi-asserted-by":"crossref","first-page":"487","DOI":"10.1137\/S0097539796297577","article-title":"Reconstructing\n      algebraic functions from mixed data","volume":"28","author":"Ar","journal-title":"SIAM Journal on\n      Computing"},{"key":"2026040314135210000_ref031","first-page":"412","article-title":"Discrepancy sets\n      and pseudorandom generators for combinatorial rectangles","author":"Armoni","year":"1996","journal-title":"Annual Symposium on Foundations of Computer Science (Burlington, VT, 1996)"},{"key":"2026040314135210000_ref032","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804090","author":"Arora","year":"2009","journal-title":"Computational\n      complexity"},{"key":"2026040314135210000_ref033","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","article-title":"Proof\n      verification and the hardness of approximation problems","volume":"45","author":"Arora","year":"1998","journal-title":"Journal of the ACM"},{"key":"2026040314135210000_ref034","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","article-title":"Probabilistic\n      checking of proofs: A new characterization of NP","volume":"45","author":"Arora","year":"1998","journal-title":"Journal of\n      the ACM"},{"key":"2026040314135210000_ref035","first-page":"485","article-title":"Improved low\n      degree testing and its applications","author":"Arora","year":"1997","journal-title":"Proceedings of the\n      Annual ACM Symposium on Theory of Computing"},{"key":"2026040314135210000_ref036","author":"Artin","year":"1991","journal-title":"Algebra"},{"key":"2026040314135210000_ref037","author":"Arvind"},{"issue":"2","key":"2026040314135210000_ref038","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1007\/s00037-011-0010-8","article-title":"Derandomizing\n      Arthur-Merlin games and approximate counting implies exponential-size lower\n      bounds","volume":"20","author":"Aydinlioglu","journal-title":"Computational Complexity"},{"key":"2026040314135210000_ref039","author":"Aydinlioglu"},{"issue":"2","key":"2026040314135210000_ref040","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/PL00009813","article-title":"Approximating\n      probability distributions using small sample spaces","volume":"18","author":"Azar","journal-title":"Combinatorica"},{"key":"2026040314135210000_ref041","doi-asserted-by":"crossref","article-title":"Checking\n      computations in polylogarithmic time","author":"Babai","DOI":"10.1145\/103418.103428"},{"issue":"1","key":"2026040314135210000_ref042","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/BF01200056","article-title":"Nondeterministic\n      exponential time has two-prover interactive protocols","volume":"1","author":"Babai","journal-title":"Computational Complexity"},{"issue":"4","key":"2026040314135210000_ref043","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/BF01275486","article-title":"BPP has\n      subexponential time simulations unless EXPTIME has publishable proofs","volume":"3","author":"Babai","journal-title":"Computational Complexity"},{"issue":"2","key":"2026040314135210000_ref044","doi-asserted-by":"crossref","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","article-title":"Arthur-Merlin\n      games: A randomized proof system, and a hierarchy of complexity\n     classes","volume":"36","author":"Babai","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314135210000_ref045","doi-asserted-by":"crossref","first-page":"1193","DOI":"10.1137\/1.9781611973068.129","article-title":"The uniform\n      hardcore lemma via approximate Bregman pro jections","author":"Barak","year":"2009","journal-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms"},{"issue":"4","key":"2026040314135210000_ref046","doi-asserted-by":"crossref","first-page":"1095","DOI":"10.1137\/S0097539705447141","article-title":"Extracting\n      randomness using few independent sources","volume":"36","author":"Barak","journal-title":"SIAM Journal on\n      Computing"},{"key":"2026040314135210000_ref047","article-title":"Simulating\n      independence: New constructions of condensers, Ramsey graphs, dispersers, and\n      extractors","volume":"57","author":"Barak","journal-title":"Journal of the ACM"},{"key":"2026040314135210000_ref048","article-title":"2-source\n      dispersers for no(1) entropy and Ramsey graphs beating\n      the Frankl-Wilson construction","author":"Barak","journal-title":"Annals of\n     Mathematics"},{"key":"2026040314135210000_ref049","doi-asserted-by":"crossref","first-page":"200","DOI":"10.1007\/978-3-540-45198-3_18","article-title":"Computational analogues of entropy","author":"Barak","year":"2003","journal-title":"Approximation, randomization, and combinatorial optimization"},{"key":"2026040314135210000_ref050","author":"Barak","journal-title":"Additive Combinatorics and\n      Computer Science"},{"key":"2026040314135210000_ref051","author":"Barker"},{"issue":"3","key":"2026040314135210000_ref052","first-page":"206","article-title":"Asymptotically optimal switching circuits","volume":"17","author":"Bassalygo","journal-title":"Problems of Information Transmission"},{"key":"2026040314135210000_ref053","first-page":"255","article-title":"Twice-ramanujan sparsi- fiers","author":"Batson","year":"2009","journal-title":"Annual ACM Symposium on Theory of Computing (Bethesda, MD)"},{"key":"2026040314135210000_ref054","article-title":"Hiding\n      instances in multioracle queries (Extended Abstract)","author":"Beaver","journal-title":"STACS\n      90 (Rouen, 1990)"},{"issue":"4","key":"2026040314135210000_ref055","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/BF01275487","article-title":"Randomness\n      in interactive proofs","volume":"3","author":"Bellare","journal-title":"Computational Complexity"},{"key":"2026040314135210000_ref056","doi-asserted-by":"crossref","article-title":"\u201cPseudo-Random\u201d number generation within cryptographic\n      algorithms: The DDS case","author":"Bellare","DOI":"10.1007\/BFb0052242"},{"key":"2026040314135210000_ref057","first-page":"276","article-title":"Randomness-efficient oblivious sampling","author":"Bellare","year":"1994","journal-title":"Annual Symposium on Foundations of Computer Science"},{"key":"2026040314135210000_ref058","first-page":"325","article-title":"A\n      combinatorial construction of almost- Ramanujan graphs using the zig-zag\n      product","author":"Ben-Aroya","year":"2008","journal-title":"Annual ACM Symposium on Theory of Computing\n      (Victoria, British Columbia)"},{"issue":"4","key":"2026040314135210000_ref059","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1137\/S0097539705446810","article-title":"Robust PCPs of\n      proximity, shorter PCPs and applications to coding","volume":"36","author":"Ben-Sasson","journal-title":"SIAM\n      Journal on Computing"},{"key":"2026040314135210000_ref060","first-page":"65","article-title":"Affine\n      dispersers from subspace polynomials","author":"Ben-Sasson","year":"2009","journal-title":"STOC\u201909\n      \u2014 Proceedings of the 2009 ACM International Symposium on Theory of Computing"},{"key":"2026040314135210000_ref061","first-page":"612","article-title":"Randomnessefficient low degree tests and short PCPs via epsilon-biased\n      sets","author":"Ben-Sasson","year":"2003","journal-title":"Proceedings of the Annual ACM Symposium on Theory of\n      Computing"},{"key":"2026040314135210000_ref062","doi-asserted-by":"crossref","article-title":"From affine to\n      two-source extractors via approximate duality","author":"Ben-Sasson","DOI":"10.1137\/12089003X"},{"key":"2026040314135210000_ref063","author":"Bennett"},{"issue":"3","key":"2026040314135210000_ref064","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/0020-0190(84)90018-8","article-title":"On\n      computing the determinant in small parallel time using a small number of\n      processors","volume":"18","author":"Berkowitz","journal-title":"Information Processing Letters"},{"key":"2026040314135210000_ref065","author":"Berlekamp","journal-title":"Algebraic Coding\n      Theory"},{"key":"2026040314135210000_ref066","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1090\/S0025-5718-1970-0276200-X","article-title":"Factoring\n      polynomials over large finite fields","volume":"24","author":"Berlekamp","year":"1970","journal-title":"Mathematics of\n      Computation"},{"key":"2026040314135210000_ref067","article-title":"On families of\n      hash functions via geometric codes and concatenation","author":"Bierbrauer","journal-title":"Advances in cryptology \u2014 CRYPTO \u201993 (Santa Barbara, CA, 1993)"},{"issue":"5","key":"2026040314135210000_ref068","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1007\/s00493-006-0029-7","article-title":"Lifts,\n      discrepancy and nearly optimal spectral gap","volume":"26","author":"Bilu","journal-title":"Combinatorica"},{"issue":"2","key":"2026040314135210000_ref069","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1007\/BF02579167","article-title":"Independent\n      unbiased coin flips from a correlated biased source \u2014 a finite state Markov\n      chain","volume":"6","author":"Blum","journal-title":"Combinatorica"},{"issue":"1","key":"2026040314135210000_ref070","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/200836.200880","article-title":"Designing\n      programs that check their work","volume":"42","author":"Blum","journal-title":"Journal of the ACM"},{"issue":"3","key":"2026040314135210000_ref071","doi-asserted-by":"crossref","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","article-title":"Self-testing\/correcting with applications to numerical\n      problems","volume":"47","author":"Blum","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"2026040314135210000_ref072","doi-asserted-by":"crossref","first-page":"850","DOI":"10.1137\/0213053","article-title":"How to\n      generate cryptographically strong sequences of pseudorandom bits","volume":"13","author":"Blum","journal-title":"SIAM Journal on Computing"},{"key":"2026040314135210000_ref073","article-title":"Pseudorandomness for Width 2 Branching\n     Programs","volume":"16","author":"Bogdanov","journal-title":"Electronic Colloquium on Computational Complexity\n      (ECCC)"},{"issue":"1","key":"2026040314135210000_ref074","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/0400000004","article-title":"Average-case\n      complexity","volume":"2","author":"Bogdanov","journal-title":"Foundations and Trends\u00ae in Theoretical\n      Computer Science"},{"issue":"6","key":"2026040314135210000_ref075","doi-asserted-by":"crossref","first-page":"2464","DOI":"10.1137\/070712109","article-title":"Pseudorandom\n      bits for polynomials","volume":"39","author":"Bogdanov","journal-title":"SIAM Journal on Computing"},{"key":"2026040314135210000_ref076","author":"Borodin"},{"key":"2026040314135210000_ref077","article-title":"Does privacy\n      require true randomness?","author":"Bosley","journal-title":"Theory of cryptography"},{"issue":"1","key":"2026040314135210000_ref078","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/s00039-007-0593-z","article-title":"On the\n      construction of affine extractors","volume":"17","author":"Bourgain","journal-title":"Geometric and Functional\n      Analysis"},{"issue":"1","key":"2026040314135210000_ref079","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/s00039-004-0451-1","article-title":"A sum-product\n      estimate in finite fields, and applications","volume":"14","author":"Bourgain","journal-title":"Geometric and\n      Functional Analysis"},{"issue":"1","key":"2026040314135210000_ref080","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1145\/58562.59305","article-title":"Inferring\n      sequences produced by pseudo-random number generators","volume":"36","author":"Boyar","journal-title":"Journal\n      of the Association for Computing Machinery"},{"issue":"5","key":"2026040314135210000_ref081","doi-asserted-by":"crossref","DOI":"10.1145\/1754399.1754401","article-title":"Polylogarithmic independence fools AC0\n      circuits","volume":"57","author":"Braverman","journal-title":"Journal of the ACM"},{"key":"2026040314135210000_ref082","first-page":"40","article-title":"Pseudorandom generators for regular branching\n     programs","author":"Braverman","year":"2010","journal-title":"FOCS"},{"key":"2026040314135210000_ref083","first-page":"50","article-title":"How hard is to\n      marry at random? (On the approximation of the permanent)","author":"Broder","year":"1986","journal-title":"Annual ACM Symposium on Theory of Computing (Berkeley, CA)"},{"key":"2026040314135210000_ref084","first-page":"30","article-title":"The coin\n      problem and pseudorandomness for branching programs","author":"Brody","year":"2010","journal-title":"FOCS"},{"key":"2026040314135210000_ref085","article-title":"One-sided\n      two-sided error in probabilistic computation","author":"Buhrman","journal-title":"STACS 99\n      (Trier)"},{"key":"2026040314135210000_ref086","first-page":"8","article-title":"Nonrelativizing separations","author":"Buhrman","year":"1998","journal-title":"Annual\n      IEEE Conference on Computational Complexity (Buffalo, NY, 1998)"},{"issue":"6","key":"2026040314135210000_ref087","doi-asserted-by":"crossref","DOI":"10.1137\/S0097539702405292","article-title":"Are\n      bitvectors optimal?","volume":"31","author":"Buhrman","journal-title":"SIAM Journal on Computing"},{"key":"2026040314135210000_ref088","article-title":"Uniform\n      hardness amplification in NP via monotone codes","volume":"13","author":"Buresh-Oppenheim","journal-title":"Electronic\n      Colloquium on Computational Complexity (ECCC)"},{"key":"2026040314135210000_ref089","author":"B\u00fcrgisser"},{"key":"2026040314135210000_ref090","doi-asserted-by":"crossref","article-title":"Exposure-\n      resilient functions and all-or-nothing transforms","author":"Canetti","DOI":"10.1007\/3-540-45539-6_33"},{"issue":"1","key":"2026040314135210000_ref091","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0020-0190(94)00171-T","article-title":"Lower\n      bounds for sampling algorithms for estimating the average","volume":"53","author":"Canetti","journal-title":"Information Processing Letters"},{"key":"2026040314135210000_ref092","first-page":"659","article-title":"Randomness\n      conductors and constant-degree lossless expanders","author":"Capalbo","year":"2002","journal-title":"Annual\n      ACM Symposium on Theory of Computing (STOC \u201802)"},{"issue":"2","key":"2026040314135210000_ref093","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/0022-0000(79)90044-8","article-title":"Universal\n      classes of hash functions","volume":"18","author":"Carter","journal-title":"Journal of Computer and System\n      Sciences"},{"key":"2026040314135210000_ref094","first-page":"195","article-title":"A lower bound\n      for the smallest eigenvalue of the Laplacian","author":"Cheeger","year":"1970","journal-title":"Problems in\n      analysis (Papers dedicated to Salomon Bochner, 1969)"},{"key":"2026040314135210000_ref095","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","article-title":"A measure of\n      asymptotic efficiency for tests of a hypothesis based on the sum of\n      observations","volume":"23","author":"Chernoff","year":"1952","journal-title":"Annals of Mathematical Statistics"},{"key":"2026040314135210000_ref096","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1137\/0217015","article-title":"Unbiased\n      bits from sources of weak randomness and probabilistic communication\n      complexity","volume":"17","author":"Chor","year":"1988","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"2026040314135210000_ref097","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0885-064X(89)90015-0","article-title":"On the\n      power of two-point based sampling","volume":"5","author":"Chor","journal-title":"Journal of\n      Complexity"},{"key":"2026040314135210000_ref098","first-page":"396","article-title":"The bit\n      extraction problem of t-resilient functions (Preliminary Version)","author":"Chor","year":"1985","journal-title":"FOCS"},{"issue":"6","key":"2026040314135210000_ref099","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/293347.293350","article-title":"Private\n      information retrieval","volume":"45","author":"Chor","journal-title":"Journal of the ACM"},{"issue":"2","key":"2026040314135210000_ref100","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1007\/s004930200010","article-title":"Sparse\n      quasi-random graphs","volume":"22","author":"Chung","journal-title":"Combinatorica"},{"issue":"1","key":"2026040314135210000_ref101","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/rsa.20188","article-title":"Quasi-random\n      graphs with given degree sequences","volume":"32","author":"Chung","journal-title":"Random Structures and\n      Algorithms"},{"issue":"1","key":"2026040314135210000_ref102","doi-asserted-by":"crossref","DOI":"10.37236\/1557","article-title":"Guessing\n      secrets","volume":"8","author":"Chung","journal-title":"Electronic Journal of Combinatorics"},{"key":"2026040314135210000_ref103","author":"Chung"},{"key":"2026040314135210000_ref104","author":"ChungGrahamWilson"},{"key":"2026040314135210000_ref105","author":"Chung"},{"key":"2026040314135210000_ref106","first-page":"151","volume-title":"vol. 6841 of Lecture Notes in Computer\n       Science","author":"Chung","year":"2011"},{"key":"2026040314135210000_ref107","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1109\/SFCS.1989.63449","article-title":"Dispersers,\n      deterministic amplification, and weak random sources (extended\n     abstract)","author":"Cohen","year":"1989","journal-title":"Annual Symposium on Foundations of Computer\n      Science (Research Triangle Park, North Carolina)"},{"issue":"3","key":"2026040314135210000_ref108","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0747-7171(08)80013-2","article-title":"Matrix\n      multiplication via arithmetic progressions","volume":"9","author":"Coppersmith","journal-title":"Journal of\n      Symbolic Computation"},{"key":"2026040314135210000_ref109","author":"Cormen","journal-title":"Introduction to\n      Algorithms"},{"key":"2026040314135210000_ref110","author":"Cover","journal-title":"Elements of Information\n      Theory"},{"issue":"4","key":"2026040314135210000_ref111","doi-asserted-by":"crossref","first-page":"618","DOI":"10.1137\/0205040","article-title":"Fast parallel\n      matrix inversion algorithms","volume":"5","author":"Csanky","journal-title":"SIAM Journal on\n      Computing"},{"key":"2026040314135210000_ref112","author":"Davidoff","year":"2003"},{"key":"2026040314135210000_ref113","first-page":"221","article-title":"Pseudorandomness\n      for permutation and regular branching programs","author":"De","year":"2011","journal-title":"IEEE\n      Conference on Computational Complexity"},{"key":"2026040314135210000_ref114","doi-asserted-by":"crossref","first-page":"483","DOI":"10.1007\/978-3-642-22935-0_41","article-title":"Extractors and\n      lower bounds for locally samplable sources","author":"De","year":"2011","journal-title":"Approximation,\n      Randomization, and Combinatorial Optimization"},{"key":"2026040314135210000_ref115","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.gs.2008.001","article-title":"A Brief Introduction to Fourier analysis on the Boolean cube","volume":"1","author":"de Wolf","year":"2008","journal-title":"Theory\n      of Computing, Graduate Surveys"},{"issue":"4","key":"2026040314135210000_ref116","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1016\/0020-0190(78)90067-4","article-title":"A\n      probabilistic remark on algebraic program testing","volume":"7","author":"DeMillo","journal-title":"Information\n      Processing Letters"},{"key":"2026040314135210000_ref117","article-title":"New\n      directions in cryptography","author":"Diffie","journal-title":"IEEE Transactions on Information\n      Theory"},{"key":"2026040314135210000_ref118","article-title":"The PCP theorem\n      by gap amplification","volume":"54","author":"Dinur","journal-title":"Journal of the ACM"},{"key":"2026040314135210000_ref119","article-title":"Security\n      amplification for interactive cryptographic\n     primitives","author":"Dodis","journal-title":"Theory of Cryptography"},{"key":"2026040314135210000_ref120","article-title":"Randomness\n      condensers for efficiently samplable, seed-dependent sources","author":"Dodis","journal-title":"Proceedings of the IACR Theory of Cryptography Conference (TCC \u201812)"},{"key":"2026040314135210000_ref121","author":"Dubhashi","journal-title":"Concentration of Measure\n      for the Analysis of Randomized Algorithms"},{"key":"2026040314135210000_ref122","first-page":"102","article-title":"Extractors for\n      varieties","author":"Dvir","year":"2009","journal-title":"IEEE Conference on Computational\n      Complexity"},{"issue":"1","key":"2026040314135210000_ref123","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00037-009-0258-4","article-title":"Extractors\n      and rank extractors for polynomial sources","volume":"18","author":"Dvir","journal-title":"Computational\n      Complexity"},{"key":"2026040314135210000_ref124","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1109\/FOCS.2009.40","article-title":"Extensions to\n      the method of multiplicities, with applications to Kakeya sets and\n     mergers","author":"Dvir","year":"2009","journal-title":"2009 Annual IEEE Symposium on Foundations of\n      Computer Science (FOCS 2009)"},{"key":"2026040314135210000_ref125","doi-asserted-by":"crossref","article-title":"Subspace\n      evasive sets","author":"Dvir","DOI":"10.1145\/2213977.2214010"},{"issue":"5","key":"2026040314135210000_ref126","doi-asserted-by":"crossref","first-page":"1404","DOI":"10.1137\/05063605X","article-title":"Locally\n      decodable codes with two queries and polynomial identity testing for depth 3\n      circuits","volume":"36","author":"Dvir","journal-title":"SIAM Journal on Computing"},{"key":"2026040314135210000_ref127","first-page":"293","article-title":"Leakage-resilient cryptography","author":"Dziembowski","year":"2008","journal-title":"Symposium on Foundations of Computer Science"},{"key":"2026040314135210000_ref128","first-page":"39","article-title":"3-query\n      locally decodable codes of subexponential length","author":"Efremenko","year":"2009","journal-title":"STOC\u201909 \u2014 Proceedings of the 2009 ACM International Symposium on Theory\n      of Computing"},{"key":"2026040314135210000_ref129","author":"Elias"},{"issue":"3","key":"2026040314135210000_ref130","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1214\/aoms\/1177692552","article-title":"The efficient\n      construction of an unbiased random sequence","volume":"43","author":"Elias","journal-title":"The Annals of\n      Mathematical Statistics"},{"issue":"1","key":"2026040314135210000_ref131","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1109\/18.61123","article-title":"Error-correcting codes for list decoding","volume":"37","author":"Elias","journal-title":"IEEE Transactions on Information Theory"},{"key":"2026040314135210000_ref132","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1090\/S0002-9904-1947-08785-1","article-title":"Some remarks on\n      the theory of graphs","volume":"53","author":"Erdos","year":"1947","journal-title":"Bulletin of the American Mathematical\n      Society"},{"key":"2026040314135210000_ref133","first-page":"27","article-title":"Problems and\n      results in chromatic graph theory","author":"Erdos","year":"1969","journal-title":"Proof Techniques in\n      Graph Theory (Proceedings of Ann Arbor Graph Theory Conference, Ann Arbor, Michigan,\n      1968)"},{"issue":"51-1","key":"2026040314135210000_ref134","first-page":"79","article-title":"Families of finite sets in which no set is covered by the union of\n       r others","volume":"51","author":"Erdos","journal-title":"Israel Journal of\n      Mathematics"},{"key":"2026040314135210000_ref135","author":"Even"},{"issue":"1","key":"2026040314135210000_ref136","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W","article-title":"Efficient\n      approximation of product distributions","volume":"13","author":"Even","journal-title":"Random Struct.\n      Algorithms"},{"issue":"2","key":"2026040314135210000_ref137","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1016\/S0019-9958(84)80056-X","article-title":"The complexity\n      of promise problems with applications to public-key cryptography","volume":"61","author":"Even","journal-title":"Information and Control"},{"issue":"2","key":"2026040314135210000_ref138","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1145\/226643.226652","article-title":"Interactive\n      proofs and the hardness of approximating cliques","volume":"43","author":"Feige","journal-title":"Journal of\n      the ACM"},{"issue":"1","key":"2026040314135210000_ref139","first-page":"62","article-title":"Eigenvalue\n      bounds on convergence to stationarity for nonreversible Markov chains, with an application to\n      the exclusion process","volume":"1","author":"Fill","journal-title":"Annals of Applied Probability"},{"key":"2026040314135210000_ref140","author":"Forney","journal-title":"Concatenated Codes"},{"issue":"4","key":"2026040314135210000_ref141","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579457","article-title":"Intersection\n      theorems with geometric consequences","volume":"1","author":"Frankl","journal-title":"Combinatorica"},{"issue":"3","key":"2026040314135210000_ref142","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","article-title":"Storing a\n      sparse table with O(1) worst case access time","volume":"31","author":"Fredman","journal-title":"Journal of the ACM"},{"issue":"910","key":"2026040314135210000_ref143","doi-asserted-by":"crossref","DOI":"10.1090\/memo\/0910","article-title":"A proof of\n      Alon\u2019s second eigenvalue conjecture and related problems","volume":"195","author":"Friedman","journal-title":"Memoirs of the American Mathematical Society"},{"issue":"2","key":"2026040314135210000_ref144","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1137\/0217016","article-title":"Reconstructing\n      truncated integer variables satisfying linear congruences","volume":"17","author":"Frieze","journal-title":"SIAM Journal on Computing"},{"key":"2026040314135210000_ref145","article-title":"A unified\n      approach to deterministic encryption: New constructions and a connection to computational\n      entropy","author":"Fuller","journal-title":"TCC"},{"key":"2026040314135210000_ref146","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1016\/0022-0000(81)90040-4","article-title":"Explicit\n      constructions of linear-sized superconcentrators","volume":"22","author":"Gabber","year":"1981","journal-title":"Journal of\n      Computer and System Sciences"},{"issue":"4","key":"2026040314135210000_ref147","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/s00493-008-2259-3","article-title":"Deterministic\n      extractors for affine sources over large fields","volume":"28","author":"Gabizon","journal-title":"Combinatorica"},{"key":"2026040314135210000_ref148","author":"Gallager","journal-title":"Low-Density Parity-Check\n      Codes"},{"key":"2026040314135210000_ref149","doi-asserted-by":"crossref","article-title":"Self-testing\/correcting for polynomials and for approximate\n      functions","author":"Gemmell","DOI":"10.1145\/103418.103429"},{"issue":"4","key":"2026040314135210000_ref150","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/0020-0190(92)90195-2","article-title":"Highly\n      resilient correctors for polynomials","volume":"43","author":"Gemmell","journal-title":"Information Processing\n      Letters"},{"key":"2026040314135210000_ref151","doi-asserted-by":"crossref","first-page":"504","DOI":"10.1002\/j.1538-7305.1952.tb01393.x","article-title":"A comparison\n      of signalling alphabets","volume":"31","author":"Gilbert","year":"1952","journal-title":"Bell Systems Technical\n      Journal"},{"issue":"4","key":"2026040314135210000_ref152","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","article-title":"Computational\n      complexity of probabilistic Turing machines","volume":"6","author":"Gill","journal-title":"SIAM Journal on\n      Computing"},{"issue":"4","key":"2026040314135210000_ref153","doi-asserted-by":"crossref","first-page":"1203","DOI":"10.1137\/S0097539794268765","article-title":"A Chernoff\n      bound for random walks on expander graphs","volume":"27","author":"Gillman","journal-title":"SIAM Journal on\n      Computing"},{"issue":"6","key":"2026040314135210000_ref154","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved\n      approximation algorithms for maximum cut and satisfiability problems using semidefinite\n      programming","volume":"42","author":"Goemans","journal-title":"Journal of the ACM"},{"key":"2026040314135210000_ref155","article-title":"A sample of\n      samplers \u2014 a computational perspective on sampling (survey)","volume":"4","author":"Goldreich","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"2026040314135210000_ref156","author":"Goldreich","journal-title":"Modern Cryptography,\n      Probabilistic Proofs and Pseudorandomness"},{"key":"2026040314135210000_ref157","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546891","author":"Goldreich","year":"2001","journal-title":"Foundations of\n      Cryptography"},{"key":"2026040314135210000_ref158","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511721656","author":"Goldreich","year":"2004","journal-title":"Foundations of\n      Cryptography II"},{"key":"2026040314135210000_ref159","article-title":"On promise\n      problems: A survey","author":"Goldreich","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"2026040314135210000_ref160","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/0400000023","article-title":"Probabilistic proof systems: A primer","volume":"3","author":"Goldreich","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"2026040314135210000_ref161","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804106","author":"Goldreich","year":"2008","journal-title":"Computational Complexity:\n      A Conceptual Perspective"},{"key":"2026040314135210000_ref162","author":"Goldreich","journal-title":"A Primer on Pseudorandom\n      Generators"},{"key":"2026040314135210000_ref163","first-page":"191","article-title":"In a World\n      of P=BPP","author":"Goldreich","year":"2011","journal-title":"Studies in Complexity and Cryptography.\n      Miscellanea on the Interplay of Randomness and Computation"},{"key":"2026040314135210000_ref164","doi-asserted-by":"crossref","first-page":"792","DOI":"10.1145\/6490.6503","article-title":"How to\n      construct random functions","volume":"33","author":"Goldreich","year":"1986","journal-title":"Journal of the ACM"},{"issue":"4","key":"2026040314135210000_ref165","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1145\/285055.285060","article-title":"Property testing\n      and its connection to learning and approximation","volume":"45","author":"Goldreich","journal-title":"Journal of\n      the ACM"},{"key":"2026040314135210000_ref166","doi-asserted-by":"crossref","first-page":"318","DOI":"10.1109\/FSCS.1990.89550","article-title":"Security\n      preserving amplification of hardness","author":"Goldreich","year":"1990","journal-title":"Annual Symposium on\n      Foundations of Computer Science, Vol. I, II (St. Louis, MO, 1990)"},{"issue":"6","key":"2026040314135210000_ref167","doi-asserted-by":"crossref","first-page":"1163","DOI":"10.1137\/0222069","article-title":"On the existence\n      of pseudorandom generators","volume":"22","author":"Goldreich","journal-title":"SIAM Journal on\n     Computing"},{"key":"2026040314135210000_ref168","first-page":"25","article-title":"A hard-core\n      predicate for all one-way functions","author":"Goldreich","year":"1989","journal-title":"Proceedings of the\n      Annual ACM Symposium on Theory of Computing"},{"issue":"191-1","key":"2026040314135210000_ref169","first-page":"215","article-title":"Computational\n      indistinguishability: algorithms vs. circuits","volume":"191","author":"Goldreich","journal-title":"Theoretical\n      Computer Science"},{"issue":"3","key":"2026040314135210000_ref170","first-page":"691","article-title":"Proofs that\n      yield nothing but their validity, or All languages in NP have zero-knowledge proof\n      systems","volume":"38","author":"Goldreich","journal-title":"Journal of the ACM"},{"key":"2026040314135210000_ref171","author":"Goldreich"},{"issue":"2","key":"2026040314135210000_ref172","doi-asserted-by":"crossref","DOI":"10.1006\/jcss.1999.1652","article-title":"Computational\n      indistinguishability: A sample hierarchy","volume":"59","author":"Goldreich","journal-title":"Journal of Computer\n      and System Sciences"},{"key":"2026040314135210000_ref173","article-title":"Simplified\n      derandomization of BPP using a hitting set generator","author":"Goldreich","journal-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay of Randomness and\n      Computation"},{"issue":"4","key":"2026040314135210000_ref174","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<315::AID-RSA3>3.0.CO;2-1","article-title":"Tiny\n      families of functions with random properties: A quality-size trade-off for\n      hashing","volume":"11","author":"Goldreich","journal-title":"Random Structures & Algorithms"},{"key":"2026040314135210000_ref175","article-title":"Cryptography without (hardly any) secrets?","author":"Goldwasser","journal-title":"Advances in cryptology \u2014 EUROCRYPT 2009"},{"key":"2026040314135210000_ref176","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","article-title":"Probabilistic\n      Encryption","volume":"28","author":"Goldwasser","year":"1984","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"2026040314135210000_ref177","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/0218012","article-title":"The knowledge\n      complexity of interactive proof systems","volume":"18","author":"Goldwasser","journal-title":"SIAM Journal on\n      Computing"},{"key":"2026040314135210000_ref178","first-page":"126","article-title":"DNF\n      Sparsification and a faster deterministic counting algorithm","author":"Gopalan","year":"2012","journal-title":"IEEE Conference on Computational Complexity"},{"key":"2026040314135210000_ref179","article-title":"Better\n      pseudorandom generators via milder pseudorandom restrictions","author":"Gopalan"},{"issue":"3","key":"2026040314135210000_ref180","doi-asserted-by":"crossref","first-page":"529","DOI":"10.1007\/s000390050065","article-title":"A new proof of\n      Szemeredi\u2019s theorem for arithmetic progressions of length four","volume":"8","author":"Gowers","journal-title":"Geometric and Functional Analysis"},{"issue":"3","key":"2026040314135210000_ref181","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/s00039-001-0332-9","article-title":"A new proof of\n      Szemeredi\u2019s theorem","volume":"11","author":"Gowers","journal-title":"Geometric and Functional\n      Analysis"},{"key":"2026040314135210000_ref182","author":"Graham"},{"issue":"3","key":"2026040314135210000_ref183","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/1027914.1027924","article-title":"Guest\n      column: Error-correcting codes and expander graphs","volume":"35","author":"Guruswami","journal-title":"SIGACT\n      News"},{"key":"2026040314135210000_ref184","author":"Guruswami","journal-title":"Algorithmic Results in\n      List Decoding."},{"key":"2026040314135210000_ref185","first-page":"77","article-title":"Linear-algebraic list decoding of folded reed-solomon\n      codes","author":"Guruswami","year":"2011","journal-title":"IEEE Conference on Computational\n     Complexity"},{"issue":"2","key":"2026040314135210000_ref186","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1109\/TIT.2010.2095170","article-title":"On the\n      list-decodability of random linear codes","volume":"57","author":"Guruswami","journal-title":"IEEE Transactions on\n      Information Theory"},{"issue":"5","key":"2026040314135210000_ref187","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1109\/18.995539","article-title":"Combinatorial bounds for list decoding","volume":"48","author":"Guruswami","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"2026040314135210000_ref188","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1109\/TIT.2007.911222","article-title":"Explicit codes\n      achieving list decoding capacity: error-correction with optimal\n     redundancy","volume":"54","author":"Guruswami","journal-title":"IEEE Transactions on Information Theory"},{"issue":"6","key":"2026040314135210000_ref189","doi-asserted-by":"crossref","first-page":"1757","DOI":"10.1109\/18.782097","article-title":"Improved\n      decoding of Reed-Solomon and algebraic-geometry codes","volume":"45","author":"Guruswami","journal-title":"Institute of Electrical and Electronics Engineers. Transactions on Information\n      Theory"},{"key":"2026040314135210000_ref190","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1145\/335305.335327","article-title":"List decoding\n      algorithms for certain concatenated codes","author":"Guruswami","year":"2000","journal-title":"STOC"},{"key":"2026040314135210000_ref191","author":"Guruswami"},{"issue":"4","key":"2026040314135210000_ref192","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1538902.1538904","article-title":"Unbalanced\n      expanders and randomness extractors from Parvaresh-Vardy codes","volume":"56","author":"Guruswami","journal-title":"Journal of the ACM"},{"key":"2026040314135210000_ref193","article-title":"Optimal rate\n      list decoding via derivative codes","author":"Guruswami","journal-title":"Approximation,\n      randomization, and combinatorial optimization"},{"key":"2026040314135210000_ref194","doi-asserted-by":"crossref","article-title":"Folded codes\n      from function field towers and improved optimal rate list decoding","author":"Guruswami","DOI":"10.1145\/2213977.2214009"},{"issue":"12-3","key":"2026040314135210000_ref195","first-page":"85","article-title":"Uniform\n      hardness versus randomness tradeoffs for Arthur-Merlin games","volume":"12","author":"Gutfreund","journal-title":"Computational Complexity"},{"key":"2026040314135210000_ref196","author":"Hastad","journal-title":"Computational Limitations of\n      Small-Depth Circuits"},{"issue":"4","key":"2026040314135210000_ref197","doi-asserted-by":"crossref","first-page":"1364","DOI":"10.1137\/S0097539793244708","article-title":"A pseudorandom\n      generator from any one-way function","volume":"28","author":"Hastad","journal-title":"SIAM Journal on\n      Computing"},{"key":"2026040314135210000_ref198","first-page":"437","article-title":"Efficiency\n      improvements in constructing pseudorandom generators from one-way\n     functions","author":"Haitner","year":"2010","journal-title":"Proceedings of the Annual ACM Symposium on Theory\n      of Computing (STOC \u201810)"},{"key":"2026040314135210000_ref199","author":"Hamming"},{"key":"2026040314135210000_ref200","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1090\/S0002-9947-1965-0170805-7","article-title":"On the\n      computational complexity of algorithms","volume":"117","author":"Hartmanis","year":"1965","journal-title":"Transactions of the\n      American Mathematical Society"},{"key":"2026040314135210000_ref201","first-page":"531","article-title":"Algebraic structures and algorithms for matching and matroid problems","author":"Harvey","journal-title":"Annual IEEE Symposium on Foundations of Computer Science (Berkeley, CA)"},{"issue":"4","key":"2026040314135210000_ref202","doi-asserted-by":"crossref","first-page":"903","DOI":"10.1137\/S0097539705447281","article-title":"Using\n      nondeterminism to amplify hardness","volume":"35","author":"Healy","journal-title":"SIAM Journal on\n      Computing"},{"issue":"1","key":"2026040314135210000_ref203","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/s00037-007-0238-5","article-title":"Randomness-efficient sampling within NC1","volume":"17","author":"Healy","journal-title":"Computational Complexity"},{"key":"2026040314135210000_ref204","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","article-title":"Probability\n      inequalities for sums of bounded random variables","volume":"58","author":"Hoeffding","year":"1963","journal-title":"Journal of\n      the American Statistical Association"},{"key":"2026040314135210000_ref205","author":"Hoffman"},{"key":"2026040314135210000_ref206","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/1060590.1060689","article-title":"Key\n      agreement from weak bit agreement","author":"Holenstein","year":"2005","journal-title":"STOC\u201905:\n      Proceedings of the Annual ACM Symposium on Theory of Computing"},{"issue":"4","key":"2026040314135210000_ref207","doi-asserted-by":"crossref","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","article-title":"Expander\n      graphs and their applications","volume":"43","author":"Hoory","journal-title":"Bulletin of the AMS"},{"key":"2026040314135210000_ref208","first-page":"538","article-title":"Hard-core\n      distributions for somewhat hard problems","author":"Impagliazzo","year":"1995","journal-title":"Annual Symposium\n      on Foundations of Computer Science"},{"key":"2026040314135210000_ref209","first-page":"659","article-title":"Hardness\n      as randomness: A survey of universal derandomization","author":"Impagliazzo","year":"2002","journal-title":"Proceedings of the International Congress of Mathematicians, Vol. III (Beijing,\n      2002)"},{"issue":"2","key":"2026040314135210000_ref210","doi-asserted-by":"crossref","first-page":"564","DOI":"10.1137\/070683994","article-title":"Approximate\n      list-decoding of direct product codes and uniform hardness\n     amplification","volume":"39","author":"Impagliazzo","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"2026040314135210000_ref211","doi-asserted-by":"crossref","first-page":"1637","DOI":"10.1137\/080734030","article-title":"Uniform\n      direct product theorems: Simplified, optimized, and derandomized","volume":"39","author":"Impagliazzo","journal-title":"SIAM Journal on Computing"},{"issue":"4","key":"2026040314135210000_ref212","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1016\/S0022-0000(02)00024-7","article-title":"In search\n      of an easy witness: Exponential time vs. probabilistic polynomial\n     time","volume":"65","author":"Impagliazzo","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314135210000_ref213","article-title":"Limits on the\n      provable consequences of one-way permutations","author":"Impagliazzo","journal-title":"Advances in\n      cryptology \u2014 CRYPTO \u201988 (Santa Barbara, CA, 1988)"},{"key":"2026040314135210000_ref214","author":"Impagliazzo"},{"key":"2026040314135210000_ref215","first-page":"220","article-title":"P = BPP if E\n      requires exponential circuits: Derandomizing the XOR lemma","author":"Impagliazzo","year":"1997","journal-title":"Proceedings of the Annual ACM Symposium on Theory of Computing"},{"issue":"4","key":"2026040314135210000_ref216","doi-asserted-by":"crossref","first-page":"672","DOI":"10.1006\/jcss.2001.1780","article-title":"Randomness\n      vs time: Derandomization under a uniform assumption","volume":"63","author":"Impagliazzo","journal-title":"Journal\n      of Computer and System Sciences"},{"key":"2026040314135210000_ref217","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1109\/SFCS.1989.63486","article-title":"How to\n      recycle random bits","author":"Impagliazzo","year":"1989","journal-title":"Annual Symposium on Foundations of\n      Computer Science (Research Triangle Park, North Carolina)"},{"key":"2026040314135210000_ref218","article-title":"An explicit\n      lower bound of 5n - o(n) for Boolean\n      circuits","author":"Iwama","journal-title":"Mathematical foundations of computer science\n      2002"},{"issue":"6","key":"2026040314135210000_ref219","doi-asserted-by":"crossref","first-page":"1149","DOI":"10.1137\/0218077","article-title":"Approximating the permanent","volume":"18","author":"Jerrum","journal-title":"SIAM\n      Journal on Computing"},{"issue":"4","key":"2026040314135210000_ref220","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1145\/1008731.1008738","article-title":"A\n      polynomial-time approximation algorithm for the permanent of a matrix with nonnegative\n      entries","volume":"51","author":"Jerrum","journal-title":"Journal of the ACM"},{"issue":"4","key":"2026040314135210000_ref221","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1007\/BF02579322","article-title":"Expanders\n      obtained from affine transformations","volume":"7","author":"Jimbo","journal-title":"Combinatorica"},{"key":"2026040314135210000_ref222","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1090\/S0002-9939-1971-0279857-5","article-title":"On a sequence\n      of almost deterministic pairwise independent random variables","volume":"29","author":"Joffe","year":"1971","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"1","key":"2026040314135210000_ref223","first-page":"161","article-title":"On a set of\n      almost deterministic k-independent random variables","volume":"2","author":"Joffe","journal-title":"Annals of Probability"},{"key":"2026040314135210000_ref224","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0012-365X(72)90027-1","article-title":"Upper bounds\n      for constant weight error correcting codes","volume":"3","author":"Johnson","year":"1972","journal-title":"Discrete\n      Mathematics"},{"key":"2026040314135210000_ref225","article-title":"A new upper\n      bound for error-correcting codes","author":"Johnson","journal-title":"IRE Transactions on\n      Information Theory"},{"key":"2026040314135210000_ref226","article-title":"Derandomization: A brief overview","author":"Kabanets","journal-title":"Current Trends in Theoretical Computer Science"},{"issue":"13-1","key":"2026040314135210000_ref227","first-page":"1","article-title":"Derandomizing polynomial identity tests means proving circuit lower\n      bounds","volume":"13","author":"Kabanets","journal-title":"Computational Complexity"},{"issue":"5","key":"2026040314135210000_ref228","doi-asserted-by":"crossref","first-page":"1091","DOI":"10.1145\/210118.210136","article-title":"Eigenvalues\n      and expansion of regular graphs","volume":"42","author":"Kahale","journal-title":"Journal of the ACM"},{"key":"2026040314135210000_ref229","author":"Kahn"},{"key":"2026040314135210000_ref230","author":"Kalai"},{"issue":"1","key":"2026040314135210000_ref231","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1016\/j.jcss.2010.06.014","article-title":"Deterministic extractors for small-space\n     sources","volume":"77","author":"Kamp","journal-title":"Journal of Computer and System Sciences"},{"issue":"5","key":"2026040314135210000_ref232","doi-asserted-by":"crossref","first-page":"1231","DOI":"10.1137\/S0097539705446846","article-title":"Deterministic extractors for bit-fixing sources and exposure-resilient\n      cryptography","volume":"36","author":"Kamp","journal-title":"SIAM Journal on Computing"},{"key":"2026040314135210000_ref233","author":"Karloff"},{"key":"2026040314135210000_ref234","article-title":"A\n      time-randomness tradeoff","author":"Karp"},{"issue":"28-3","key":"2026040314135210000_ref235","first-page":"191","article-title":"Turing\n      machines that take advice","volume":"28","author":"Karp","journal-title":"L \u2019Enseignement\n      Math\u00e9matique. Revue Internationale. Ile S\u00e9rie"},{"issue":"3","key":"2026040314135210000_ref236","doi-asserted-by":"crossref","first-page":"429","DOI":"10.1016\/0196-6774(89)90038-2","article-title":"Monte Carlo\n      approximation algorithms for enumeration problems","volume":"10","author":"Karp","journal-title":"Journal of\n      Algorithms"},{"issue":"1","key":"2026040314135210000_ref237","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","article-title":"Constructing a perfect matching is in Random\n     NC","volume":"6","author":"Karp","journal-title":"Combinatorica"},{"key":"2026040314135210000_ref238","author":"Katz","journal-title":"Introduction to modern\n      cryptography. Chapman & Hall\/CRC Cryptography and Network Security"},{"key":"2026040314135210000_ref239","first-page":"80","article-title":"On the\n      efficiency of local decoding procedures for error-correcting codes","author":"Katz","year":"2000","journal-title":"Proceedings of the Annual ACM Symposium on Theory of Computing"},{"issue":"2","key":"2026040314135210000_ref240","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1090\/S0894-0347-1989-0965007-8","article-title":"An estimate for\n      character sums","volume":"2","author":"Katz","journal-title":"Journal of the American Mathematical\n      Society"},{"issue":"2","key":"2026040314135210000_ref241","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s00037-007-0226-9","article-title":"Polynomial\n      identity testing for depth 3 circuits","volume":"16","author":"Kayal","journal-title":"Computational\n      Complexity"},{"key":"2026040314135210000_ref242","author":"Kinne"},{"issue":"3","key":"2026040314135210000_ref243","doi-asserted-by":"crossref","first-page":"217","DOI":"10.1023\/A:1022949332276","article-title":"Boosting and\n      Hard-Core Set Construction","volume":"51","author":"Klivans","journal-title":"Machine Learning"},{"key":"2026040314135210000_ref244","author":"Klivans"},{"key":"2026040314135210000_ref245","author":"Knuth","journal-title":"The art of computer\n      programming. Volume 2: Seminumerical Algorithms"},{"key":"2026040314135210000_ref246","first-page":"232","article-title":"Extracting\n      randomness from generalized symbol-fixing and Markov sources","author":"K\u00f6nig","journal-title":"Proceedings of 2004 IEEE International Symposium on Information Theory"},{"key":"2026040314135210000_ref247","article-title":"Generalized\n      strong extractors and deterministic privacy amplification","author":"Koiiig","journal-title":"IMA International Conference"},{"key":"2026040314135210000_ref248","article-title":"List-decoding multiplicity codes","volume":"19","author":"Kopparty","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"2026040314135210000_ref249","doi-asserted-by":"crossref","article-title":"High-rate\n      codes with sublinear-time decoding","author":"Kopparty","DOI":"10.1145\/1993636.1993660"},{"key":"2026040314135210000_ref250","doi-asserted-by":"crossref","article-title":"Pseudorandom\n      generators for group products: extended abstract","author":"Koucky","DOI":"10.1145\/1993636.1993672"},{"key":"2026040314135210000_ref251","author":"Koutsougeras"},{"issue":"4","key":"2026040314135210000_ref252","doi-asserted-by":"crossref","first-page":"527","DOI":"10.1016\/0196-6774(92)90054-G","article-title":"How to\n      predict congruential generators","volume":"13","author":"Krawczyk","journal-title":"Journal of\n      Algorithms"},{"key":"2026040314135210000_ref253","author":"Kushilevitz","year":"1997","journal-title":"Communication\n      complexity"},{"key":"2026040314135210000_ref254","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1145\/380752.380832","article-title":"Explicit lower\n      bound of 4.5n - o(n) for Boolean\n     circuits","author":"Lachish","year":"2001","journal-title":"Annual ACM Symposium on Theory of\n      Computing"},{"key":"2026040314135210000_ref255","doi-asserted-by":"crossref","first-page":"1313","DOI":"10.1214\/aoms\/1177700007","article-title":"Pairwise\n      statistical independence","volume":"36","author":"Lancaster","year":"1965","journal-title":"Annals of Mathematical\n      Statistics"},{"issue":"4","key":"2026040314135210000_ref256","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/0020-0190(83)90044-3","article-title":"BPP and the\n      polynomial hierarchy","volume":"17","author":"Lautemann","journal-title":"Information Processing Letters"},{"key":"2026040314135210000_ref257","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/978-3-642-22953-4_7","volume-title":"Fundamentals of Computation Theory","author":"Lee","year":"2011"},{"key":"2026040314135210000_ref258","author":"Leighton","journal-title":"Introduction to Parallel\n      Algorithms and Architectures: Arrays, Trees, and Hypercubes"},{"issue":"4","key":"2026040314135210000_ref259","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1007\/BF02579323","article-title":"One way\n      functions and pseudorandom generators","volume":"7","author":"Levin","journal-title":"Combina-\n      torica"},{"key":"2026040314135210000_ref260","first-page":"438","article-title":"Checking\n      polynomial identities over any field: towards a derandomization?","author":"Lewin","year":"1999","journal-title":"Annual ACM Symposium on the Theory of Computing (Dallas, TX)"},{"key":"2026040314135210000_ref261","author":"Li","journal-title":"An Introduction to\n      Kolmogorov Complexity and its Applications. Texts in Computer Science"},{"key":"2026040314135210000_ref262","first-page":"137","article-title":"A New Approach to\n      Affine Extractors and Dispersers","author":"Li","year":"2011","journal-title":"IEEE Conference on\n      Computational Complexity"},{"key":"2026040314135210000_ref263","author":"Lidl","journal-title":"Introduction to Finite\n      Fields and their Applications"},{"issue":"2","key":"2026040314135210000_ref264","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF01200907","article-title":"Efficient\n      construction of a small hitting set for combinatorial rectangles in high\n      dimension","volume":"17","author":"Linial","journal-title":"Combinatorica"},{"issue":"4","key":"2026040314135210000_ref265","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/BF02128670","article-title":"Approximate\n      inclusion-exclusion","volume":"10","author":"Linial","journal-title":"Combinatorica"},{"key":"2026040314135210000_ref266","article-title":"New directions\n      in testing","author":"Lipton","journal-title":"Distributed computing and cryptography\n      (Princeton, NJ, 1989)"},{"key":"2026040314135210000_ref267","author":"Lovasz"},{"issue":"1","key":"2026040314135210000_ref268","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TIT.1979.1055985","article-title":"On the Shannon\n      capacity of a graph","volume":"25","author":"Lovasz","journal-title":"IEEE Transactions on Information\n      Theory"},{"key":"2026040314135210000_ref269","author":"Lovasz","journal-title":"Combinatorial Problems and\n      Exercises"},{"key":"2026040314135210000_ref270","first-page":"69","article-title":"Unconditional\n      pseudorandom generators for low-degree polynomials","volume":"5","author":"Lovett","year":"2009","journal-title":"Theory of\n      Computing. An Open Access Journal"},{"issue":"3","key":"2026040314135210000_ref271","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s004930200021","article-title":"Improved pseudorandom generators for combinatorial rectangles","volume":"22","author":"Lu","year":"(2022)","journal-title":"Combinatorica"},{"key":"2026040314135210000_ref272","doi-asserted-by":"crossref","first-page":"602","DOI":"10.1145\/780542.780630","article-title":"Extractors: optimal up to constant\n     factors","author":"Lu","year":"2003","journal-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC\n      \u201803)"},{"issue":"1-3","key":"2026040314135210000_ref273","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/j.tcs.2006.10.009","article-title":"Improved hardness amplification in NP","volume":"370","author":"Lu","year":"2007","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"2026040314135210000_ref274","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/s00037-011-0003-7","article-title":"Complexity of hard-core set proofs","volume":"20","author":"Lu","year":"2011","journal-title":"Computational Complexity"},{"key":"2026040314135210000_ref275","author":"Lubotzky","journal-title":"Discrete Groups, Expanding\n      Graphs and Invariant Measures."},{"issue":"1","key":"2026040314135210000_ref276","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1090\/S0273-0979-2011-01359-3","article-title":"Expander\n      graphs in pure and applied mathematics","volume":"49","author":"Lubotzky","journal-title":"American Mathematical\n      Society. Bulletin. New Series"},{"issue":"3","key":"2026040314135210000_ref277","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02126799","article-title":"Ramanujan\n      graphs","volume":"8","author":"Lubotzky","journal-title":"Combinatorica"},{"issue":"4","key":"2026040314135210000_ref278","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","article-title":"A simple\n      parallel algorithm for the maximal independent set problem","volume":"15","author":"Luby","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"2026040314135210000_ref279","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1016\/0022-0000(93)90033-S","article-title":"Removing\n      randomness in parallel computation without a processor penalty","volume":"47","author":"Luby","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314135210000_ref280","first-page":"18","article-title":"Deterministic Approximate Counting of Depth-2\n     Circuits","author":"Luby","year":"1993","journal-title":"ISTCS"},{"key":"2026040314135210000_ref281","author":"Luby","journal-title":"Pairwise Independence and\n      Derandomization."},{"key":"2026040314135210000_ref282","author":"MacWilliams","journal-title":"The Theory of\n      Error-correcting Codes"},{"issue":"4","key":"2026040314135210000_ref283","first-page":"71","article-title":"Explicit\n      constructions of expanders","volume":"9","author":"Margulis","journal-title":"Problemy Peredaci\n      Informacii"},{"issue":"1","key":"2026040314135210000_ref284","first-page":"51","article-title":"Explicit\n      group-theoretic constructions of combinatorial schemes and their applications in the\n      construction of expanders and concentrators","volume":"24","author":"Margulis","journal-title":"Problemy\n      Peredacci Informacii"},{"issue":"3","key":"2026040314135210000_ref285","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1017\/S0963548305007352","article-title":"Disjoint\n      decomposition of Markov chains and sampling circuits in Cayley graphs","volume":"15","author":"Martin","journal-title":"Combinatorics, Probability and Computing"},{"key":"2026040314135210000_ref286","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1109\/SFCS.1989.63529","article-title":"Conductance\n      and convergence of Markov Chains-A combinatorial treatment of\n     expanders","author":"Mihail","year":"1989","journal-title":"Annual Symposium on Foundations of Computer\n      Science (Research Triangle Park, North Carolina)"},{"key":"2026040314135210000_ref287","author":"Miller"},{"key":"2026040314135210000_ref288","author":"Miltersen","journal-title":"Handbook of Randomized\n      Computing"},{"issue":"3","key":"2026040314135210000_ref289","doi-asserted-by":"crossref","first-page":"256","DOI":"10.1007\/s00037-005-0197-7","article-title":"Derandomizing Arthur-Merlin games using hitting\n     sets","volume":"14","author":"Miltersen","journal-title":"Computational Complexity"},{"key":"2026040314135210000_ref290","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511813603","author":"Mitzenmacher","year":"2005","journal-title":"Probability and\n      Computing"},{"key":"2026040314135210000_ref291","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","author":"Motwani","year":"1995","journal-title":"Randomized\n      Algorithms"},{"key":"2026040314135210000_ref292","first-page":"248","article-title":"Maximum\n      matchings via Gaussian elimination","author":"Mucha","year":"2004","journal-title":"Symposium on\n      Foundations of Computer Science (Rome, Italy)"},{"key":"2026040314135210000_ref293","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1080\/00029890.1954.11988567","article-title":"Boolean\n      algebras in electric circuit design","volume":"61","author":"Muller","year":"1954","journal-title":"The American Mathematical\n      Monthly"},{"key":"2026040314135210000_ref294","author":"Mulmuley"},{"key":"2026040314135210000_ref295","author":"Muthukrishnan","journal-title":"Data Streams:\n      Algorithms and Applications"},{"key":"2026040314135210000_ref296","doi-asserted-by":"crossref","first-page":"838","DOI":"10.1137\/0222053","article-title":"Small-bias\n      probability spaces: Efficient constructions and applications","volume":"22","author":"Naor","year":"1993","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"2026040314135210000_ref297","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/0012-365X(91)90112-F","article-title":"On the second\n      eigenvalue of a graph","volume":"91","author":"Nilli","journal-title":"Discrete Mathematics"},{"issue":"1","key":"2026040314135210000_ref298","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF01375474","article-title":"Pseudorandom\n      bits for constant depth circuits","volume":"11","author":"Nisan","journal-title":"Combinatorica"},{"issue":"4","key":"2026040314135210000_ref299","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF01305237","article-title":"Pseudorandom\n      generators for space-bounded computation","volume":"12","author":"Nisan","journal-title":"Combinatorica"},{"issue":"1","key":"2026040314135210000_ref300","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01205052","article-title":"RL \u00c7\n      SC","volume":"4","author":"Nisan","journal-title":"Computational Complexity"},{"key":"2026040314135210000_ref301","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1006\/jcss.1997.1546","article-title":"Extracting\n      randomness: A survey and new constructions","volume":"58","author":"Nisan","year":"1999","journal-title":"Journal of\n      Computer and System Sciences"},{"key":"2026040314135210000_ref302","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/S0022-0000(05)80043-1","article-title":"Hardness vs\n      Randomness","volume":"49","author":"Nisan","year":"1994","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314135210000_ref303","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1006\/jcss.1996.0004","article-title":"Randomness\n      is linear in space","volume":"52","author":"Nisan","year":"1996","journal-title":"Journal of Computer and System\n      Sciences"},{"issue":"1","key":"2026040314135210000_ref304","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/j.jcss.2004.01.001","article-title":"Hardness amplification within NP","volume":"69","author":"O\u2019Donnell","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314135210000_ref305","author":"O\u2019Donnell"},{"key":"2026040314135210000_ref306","first-page":"285","article-title":"Correcting\n      errors beyond the Guruswami-Sudan radius in polynomial time","author":"Parvaresh","year":"2005","journal-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science"},{"issue":"1","key":"2026040314135210000_ref307","first-page":"590","article-title":"Iterating von\n      Neumann\u2019s procedure for extracting random bits","volume":"20","author":"Peres","journal-title":"The\n      Annals of Statistics"},{"key":"2026040314135210000_ref308","article-title":"Encoding and\n      error-correction procedures for the Bose- Chaudhuri codes","author":"Peterson","journal-title":"IRE\n      Transactions on Information Theory"},{"key":"2026040314135210000_ref309","article-title":"On the\n      complexity of a concentrator","author":"Pinsker","journal-title":"Annual Teletraffic\n      Conference"},{"key":"2026040314135210000_ref310","first-page":"307","article-title":"On\n      simultaneous resource bounds (Preliminary Version)","author":"Pippenger","year":"1979","journal-title":"Annual\n      Symposium on Foundations of Computer Science (San Juan, Puerto Rico)"},{"issue":"2","key":"2026040314135210000_ref311","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1145\/322123.322138","article-title":"Relations\n      among complexity measures","volume":"26","author":"Pippenger","journal-title":"Journal of the Association for\n      Computing Machinery"},{"key":"2026040314135210000_ref312","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1093\/biomet\/33.4.305","article-title":"The design of\n      optimum multi-factorial experiments","volume":"33","author":"Plackett","year":"1945","journal-title":"Biometrika"},{"key":"2026040314135210000_ref313","author":"Pless","year":"1998"},{"issue":"1","key":"2026040314135210000_ref314","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1016\/0022-314X(80)90084-0","article-title":"Probabilistic\n      algorithm for testing primality","volume":"12","author":"Rabin","journal-title":"Journal of Number\n      Theory"},{"key":"2026040314135210000_ref315","author":"Radhakrishnan"},{"issue":"2","key":"2026040314135210000_ref316","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1016\/0022-0000(88)90003-7","article-title":"Probabilistic construction of deterministic algorithms: approximating\n      packing integer programs","volume":"37","author":"Raghavan","journal-title":"Journal of Computer and System\n      Sciences"},{"key":"2026040314135210000_ref317","first-page":"4","article-title":"Mixing","author":"Randall","year":"2003","journal-title":"Symposium on Foundations of\n      Computer Science (Cambridge, MA)"},{"issue":"1","key":"2026040314135210000_ref318","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1137\/060671218","article-title":"Extractors for a\n      constant number of polynomially small minentropy independent sources","volume":"39","author":"Rao","journal-title":"SIAM Journal on Computing"},{"key":"2026040314135210000_ref319","first-page":"159","article-title":"On recycling\n      the randomness of states in space bounded computation","author":"Raz","year":"1999","journal-title":"Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999)"},{"key":"2026040314135210000_ref320","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1006\/jcss.2002.1824","article-title":"Extracting all\n      the Randomness and Reducing the Error in Trevisan\u2019s Extractors","volume":"65","author":"Raz","year":"2002","journal-title":"Journal of Computer and System Sciences"},{"issue":"4","key":"2026040314135210000_ref321","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1017\/S0963548300000870","article-title":"Constructing small sets that are uniform in arithmetic\n      progressions","volume":"2","author":"Razborov","journal-title":"Combinatorics Probability Computing"},{"issue":"4","key":"2026040314135210000_ref322","first-page":"598","article-title":"Lower bounds\n      on the dimension of schemes of bounded depth in a complete basis containing the logical\n      addition function","volume":"41","author":"Razborov","journal-title":"Akademiya Nauk SSSR. Matematicheskie\n      Zametki"},{"issue":"1","key":"2026040314135210000_ref323","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1006\/jcss.1997.1494","article-title":"Natural\n      proofs","volume":"55","author":"Razborov","year":"1997","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314135210000_ref324","article-title":"A class of\n      multiple-error-correcting codes and the decoding scheme","author":"Reed","journal-title":"IRE\n      Transactions on Information Theory"},{"key":"2026040314135210000_ref325","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1137\/0108018","article-title":"Polynomial\n      codes over certain finite fields","volume":"8","author":"Reed","year":"1960","journal-title":"Journal of the Society of\n      Industrial and Applied Mathematics"},{"key":"2026040314135210000_ref326","article-title":"On black-box\n      separations in cryptography","author":"Reingold","journal-title":"Tutorial at the Third Theory of\n      Cryptography Conference (TCC \u201806)"},{"issue":"4","key":"2026040314135210000_ref327","doi-asserted-by":"crossref","DOI":"10.1145\/1391289.1391291","article-title":"Undirected\n      connectivity in log-space","volume":"55","author":"Reingold","journal-title":"Journal of the ACM"},{"issue":"5","key":"2026040314135210000_ref328","doi-asserted-by":"crossref","first-page":"1185","DOI":"10.1137\/S0097539703431032","article-title":"Extracting\n      randomness via repeated condensing","volume":"35","author":"Reingold","journal-title":"SIAM Journal on\n      Computing"},{"key":"2026040314135210000_ref329","first-page":"76","article-title":"Dense subsets\n      of pseudorandom sets","author":"Reingold","year":"2008","journal-title":"Proceedings of the Annual IEEE\n      Symposium on Foundations of Computer Science (FOCS \u201808)"},{"key":"2026040314135210000_ref330","article-title":"Notions of\n      reducibility between cryptographic primitives","author":"Reingold","journal-title":"Proceedings\n      of the First Theory of Cryptography Conference (TCC \u201804)"},{"key":"2026040314135210000_ref331","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1145\/1132516.1132583","article-title":"Pseudorandom\n      Walks in Regular Digraphs and the RL vs. L Problem","author":"Reingold","year":"2006","journal-title":"Proceedings of the Annual ACM Symposium on Theory of Computing (STOC\n      \u201806)"},{"key":"2026040314135210000_ref332","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1109\/SFCS.2000.892006","article-title":"Entropy\n      waves, the zig-zag graph product, and new constant-degree expanders and\n      extractors","author":"Reingold","year":"2000","journal-title":"Proceedings of the Annual Symposium on\n      Foundations of Computer Science (FOCS 000)"},{"key":"2026040314135210000_ref333","article-title":"Entropy\n      waves, the zig-zag graph product, and new constant-degree expanders","volume":"155","author":"Reingold","journal-title":"Annals of Mathematics"},{"key":"2026040314135210000_ref334","article-title":"A note on\n      extracting randomness from Santha-Vazirani sources","author":"Reingold","journal-title":"Unpublished manuscript"},{"key":"2026040314135210000_ref335","first-page":"547","article-title":"On measures of\n      entropy and information","author":"Renyi","year":"1961","journal-title":"Proceedings of Berkeley Symposium\n      on Mathematics Statistics and Probability, Vol. I"},{"issue":"2","key":"2026040314135210000_ref336","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1145\/359340.359342","article-title":"A method for\n      obtaining digital signatures and public-key cryptosystems","volume":"21","author":"Rivest","journal-title":"Communications of the Association for Computing Machinery"},{"key":"2026040314135210000_ref337","first-page":"597","article-title":"Property\n      testing","author":"Ron","year":"2001","journal-title":"Handbook of Randomized Computing, Vol. I, II,\n      volume 9 of Comb. Optim."},{"key":"2026040314135210000_ref338","article-title":"Derandomized\n      squaring of graphs","author":"Rozenman","journal-title":"Proceedings of the International\n      Workshop on Randomization and Computation (RANDOM \u201805)"},{"key":"2026040314135210000_ref339","first-page":"1095","article-title":"Sublinear\n      time algorithms","author":"Rubinfeld","year":"2006","journal-title":"International Congress of Mathematicians.\n      Vol. III"},{"issue":"2","key":"2026040314135210000_ref340","doi-asserted-by":"crossref","first-page":"252","DOI":"10.1137\/S0097539793255151","article-title":"Robust\n      characterizations of polynomials with applications to program testing","volume":"25","author":"Rubinfeld","journal-title":"SIAM Journal on Computing"},{"key":"2026040314135210000_ref341","author":"Rukhin"},{"issue":"3","key":"2026040314135210000_ref342","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1145\/321958.321975","article-title":"P -complete approximation\n     problems","volume":"23","author":"Sahni","journal-title":"Journal of the ACM"},{"issue":"1","key":"2026040314135210000_ref343","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1145\/273865.273915","article-title":"Explicit\n      OR-dispersers with polylogarithmic degree","volume":"45","author":"Saks","journal-title":"Journal of the\n      ACM"},{"issue":"2","key":"2026040314135210000_ref344","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1006\/jcss.1998.1616","article-title":"BPHSPACE(S) C\n        DSPACE(S3\/2)","volume":"58","author":"Saks","journal-title":"Journal of\n      Computer and System Sciences"},{"key":"2026040314135210000_ref345","author":"Saks"},{"issue":"1","key":"2026040314135210000_ref346","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/0022-0000(86)90044-9","article-title":"Generating\n      quasirandom sequences from semirandom sources","volume":"33","author":"Santha","journal-title":"Journal of\n      Computer and System Sciences"},{"key":"2026040314135210000_ref347","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1145\/1250790.1250832","article-title":"Circuit\n      lower bounds for Merlin-Arthur classes","author":"Santhanam","year":"2007","journal-title":"STOC\u201907\n      \u2014 Proceedings of the Annual ACM Symposium on Theory of Computing"},{"key":"2026040314135210000_ref348","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511895593","author":"Sarnak","year":"1990","journal-title":"Some Applications of Modular\n      Forms."},{"key":"2026040314135210000_ref349","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","article-title":"Relationships\n      between nondeterministic and deterministic tape complexities","volume":"4","author":"Savitch","year":"1970","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"2026040314135210000_ref350","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1137\/S089548019223872X","article-title":"Chernoff-Hoeffding bounds for applications with limited\n      independence","volume":"8","author":"Schmidt","journal-title":"SIAM Journal on Discrete Mathematics"},{"issue":"4","key":"2026040314135210000_ref351","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","article-title":"Fast\n      probabilistic algorithms for verification of polynomial identities","volume":"27","author":"Schwartz","journal-title":"Journal of the ACM"},{"key":"2026040314135210000_ref352","article-title":"Recent\n      Developments in Extractors","volume":"1","author":"Shaltiel","journal-title":"Current Trends in Theoretical\n      Computer Science"},{"key":"2026040314135210000_ref353","doi-asserted-by":"crossref","article-title":"Dispersers\n      for affine sources with sub-polynomial entropy","author":"Shaltiel","DOI":"10.1109\/FOCS.2011.37"},{"key":"2026040314135210000_ref354","first-page":"21","article-title":"An\n      introduction to randomness extractors","author":"Shaltiel","year":"2011","journal-title":"Automata, languages\n      and programming. Part II, vol. 6756 of Lecture Notes in Computer Science"},{"issue":"1","key":"2026040314135210000_ref355","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/s00037-011-0006-4","article-title":"Weak\n      derandomization of weak algorithms: explicit versions of Yao\u2019s\n     lemma","volume":"20","author":"Shaltiel","journal-title":"Computational Complexity"},{"issue":"2","key":"2026040314135210000_ref356","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1145\/1059513.1059516","article-title":"Simple\n      extractors for all min-entropies and a new Pseudo-random generator","volume":"52","author":"Shaltiel","journal-title":"Journal of the ACM"},{"issue":"4","key":"2026040314135210000_ref357","doi-asserted-by":"crossref","first-page":"298","DOI":"10.1007\/s00037-007-0218-9","article-title":"Pseudorandomness for approximate counting and\n     sampling","volume":"15","author":"Shaltiel","journal-title":"Computational Complexity"},{"issue":"3","key":"2026040314135210000_ref358","doi-asserted-by":"crossref","first-page":"1006","DOI":"10.1137\/070698348","article-title":"Low-end uniform\n      hardness versus randomness tradeoffs for AM","volume":"39","author":"Shaltiel","journal-title":"SIAM Journal on\n      Computing"},{"issue":"11","key":"2026040314135210000_ref359","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1145\/359168.359176","article-title":"How to share a\n      secret","volume":"22","author":"Shamir","journal-title":"Communications of the Association for Computing\n      Machinery"},{"key":"2026040314135210000_ref360","article-title":"On the\n      generation of cryptographically strong pseudorandom sequences","author":"Shamir","journal-title":"Automata, Languages and Programming (Akko, 1981)"},{"key":"2026040314135210000_ref361","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1002\/j.1538-7305.1948.tb01338.x","article-title":"A\n      mathematical theory of communication","volume":"27","author":"Shannon","year":"1948","journal-title":"The Bell System\n      Technical Journal"},{"issue":"5-3","key":"2026040314135210000_ref362","first-page":"207","article-title":"Arithmetic\n      circuits: A survey of recent results and open questions","volume":"5","author":"Shpilka","journal-title":"Foundations and Trends\u00ae in Theoretical Computer Science"},{"key":"2026040314135210000_ref363","article-title":"Almost\n       k-wise independent sets establish hitting sets for width-3 1-branching\n      programs","author":"Sima","journal-title":"CSR"},{"key":"2026040314135210000_ref364","first-page":"330","article-title":"A complexity\n      theoretic approach to randomness","author":"Sipser","year":"1983","journal-title":"Annual ACM Symposium on\n      Theory of Computing"},{"issue":"3","key":"2026040314135210000_ref365","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1016\/0022-0000(88)90035-9","article-title":"Expanders,\n      randomness, or time versus space","volume":"36","author":"Sipser","journal-title":"Journal of Computer and\n      System Sciences"},{"key":"2026040314135210000_ref366","author":"Sipser","journal-title":"Introduction to the Theory of\n      Computation"},{"key":"2026040314135210000_ref367","doi-asserted-by":"crossref","first-page":"1710","DOI":"10.1109\/18.556667","article-title":"Expander\n      codes","volume":"42","author":"Sipser","year":"1996","journal-title":"IEEE Transactions on Information Theory"},{"key":"2026040314135210000_ref368","doi-asserted-by":"crossref","article-title":"Algebraic\n      methods in the theory of lower bounds for Boolean circuit complexity","author":"Smolensky","DOI":"10.1145\/28395.28404"},{"issue":"1","key":"2026040314135210000_ref369","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1137\/0206006","article-title":"A fast\n      Monte-Carlo test for primality","volume":"6","author":"Solovay","journal-title":"SIAM Journal on\n      Computing"},{"key":"2026040314135210000_ref370","author":"Spencer","journal-title":"Ten Lectures on the\n      Probabilistic Method"},{"key":"2026040314135210000_ref371","first-page":"29","article-title":"Spectral\n      graph theory and its applications","author":"Spielman","year":"2007","journal-title":"Symposium on Foundations\n      of Computer Science (FOCS 2007), 21-23 October 2007, Providence, RI, USA,\n     Proceedings"},{"issue":"4","key":"2026040314135210000_ref372","doi-asserted-by":"crossref","first-page":"1433","DOI":"10.1137\/S009753979630091X","article-title":"Computing\n      with very weak random sources","volume":"28","author":"Srinivasan","journal-title":"SIAM Journal on\n      Computing"},{"key":"2026040314135210000_ref373","author":"Steinke"},{"key":"2026040314135210000_ref374","first-page":"421","article-title":"Secret linear\n      congruential generators are not cryptographically secure","author":"Stern","year":"1987","journal-title":"FOCS"},{"key":"2026040314135210000_ref375","author":"Stichtenoth","journal-title":"Algebraic Function\n      Fields and Codes"},{"issue":"2","key":"2026040314135210000_ref376","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/S0022-0000(05)80007-8","article-title":"Combinatorial\n      techniques for universal hashing","volume":"48","author":"Stinson","journal-title":"Journal of Computer and\n      System Sciences"},{"key":"2026040314135210000_ref377","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1007\/BF02165411","article-title":"Gaussian\n      elimination is not optimal","volume":"13","author":"Strassen","year":"1969","journal-title":"Numerische Mathematik"},{"key":"2026040314135210000_ref378","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1006\/jcom.1997.0439","article-title":"Decoding of\n      Reed Solomon codes beyond the error-correction bound","volume":"13","author":"Sudan","year":"1997","journal-title":"Journal\n      of Complexity"},{"key":"2026040314135210000_ref379","author":"Sudan"},{"key":"2026040314135210000_ref380","author":"Sudan"},{"key":"2026040314135210000_ref381","doi-asserted-by":"crossref","first-page":"236","DOI":"10.1006\/jcss.2000.1730","article-title":"Pseudorandom\n      generators without the XOR lemma","volume":"62","author":"Sudan","year":"2001","journal-title":"Journal of Computer and\n      System Sciences"},{"issue":"2","key":"2026040314135210000_ref382","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/s00493-007-0053-2","article-title":"Lossless\n      condensers, unbalanced expanders, and extractors","volume":"27","author":"Ta-Shma","journal-title":"Combinatorica"},{"issue":"12","key":"2026040314135210000_ref383","doi-asserted-by":"crossref","first-page":"3015","DOI":"10.1109\/TIT.2004.838377","article-title":"Extractor\n      codes","volume":"50","author":"Ta-Shma","journal-title":"IEEE Transactions on Information Theory"},{"issue":"5","key":"2026040314135210000_ref384","doi-asserted-by":"crossref","first-page":"786","DOI":"10.1016\/j.jcss.2005.05.010","article-title":"Extractors from\n      Reed-Muller codes","volume":"72","author":"Ta-Shma","journal-title":"Journal of Computer and System\n      Sciences"},{"issue":"3","key":"2026040314135210000_ref385","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1137\/0605030","article-title":"Explicit\n      concentrators from generalized N -gons","volume":"5","author":"Tanner","journal-title":"SIAM\n      Journal on Algebraic Discrete Methods"},{"key":"2026040314135210000_ref386","author":"Tao"},{"key":"2026040314135210000_ref387","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511626265","author":"Terras","year":"1999","journal-title":"Fourier Analysis on Finite\n      Groups and Applications"},{"key":"2026040314135210000_ref388","author":"Tessaro"},{"issue":"4","key":"2026040314135210000_ref389","first-page":"860","article-title":"Extractors\n      and pseudorandom generators","volume":"48","author":"Trevisan","journal-title":"Journal of the ACM"},{"key":"2026040314135210000_ref390","first-page":"126","article-title":"List\n      decoding using the XOR lemma","author":"Trevisan","year":"2003","journal-title":"Proceedings of the IEEE\n      Symposium on Foundations of Computer Science"},{"key":"2026040314135210000_ref391","first-page":"347","article-title":"Some\n      applications of coding theory in computational complexity","volume":"13","author":"Trevisan","year":"2004","journal-title":"Quaderni di Matematica"},{"key":"2026040314135210000_ref392","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1060590.1060595","article-title":"On uniform\n      amplification of hardness in NP","author":"Trevisan","year":"2005","journal-title":"STOC\u201905:\n      Proceedings of the Annual ACM Symposium on Theory of Computing"},{"key":"2026040314135210000_ref393","first-page":"1111","article-title":"Pseudorandomness and combinatorial\n     constructions","author":"Trevisan","year":"2006","journal-title":"International Congress of Mathematicians.\n      Vol. III"},{"issue":"2","key":"2026040314135210000_ref394","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1145\/1556154.1556170","article-title":"Guest\n      column: Additive combinatorics and theoretical computer science","volume":"40","author":"Trevisan","journal-title":"SIGACT News"},{"key":"2026040314135210000_ref395","article-title":"Dense model\n      theorems and their applications","author":"Trevisan","journal-title":"Theory of\n      cryptography"},{"key":"2026040314135210000_ref396","first-page":"126","article-title":"Regularity,\n      boosting, and efficiently simulating every high-entropy distribution","author":"Trevisan","year":"2009","journal-title":"Proceedings of the Annual IEEE Conference on Computational Complexity (CCC\n      \u201809)"},{"key":"2026040314135210000_ref397","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s00037-007-0233-x","article-title":"Pseudorandomness and average-case complexity via uniform\n      reductions","volume":"16","author":"Trevisan","year":"2007","journal-title":"Computational Complexity"},{"key":"2026040314135210000_ref398","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1109\/SFCS.2000.892063","article-title":"Extracting\n      randomness from samplable distributions","author":"Trevisan","year":"2000","journal-title":"Proceedings of the\n      Annual Symposium on Foundations of Computer Science (FOCS \u201800)"},{"issue":"2","key":"2026040314135210000_ref399","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1016\/S0022-0000(03)00046-1","article-title":"Pseudo-random\n      generators for all hardnesses","volume":"67","author":"Umans","journal-title":"Journal of Computer and System\n      Sciences"},{"key":"2026040314135210000_ref400","author":"Vadhan"},{"key":"2026040314135210000_ref401","author":"Vadhan"},{"issue":"1","key":"2026040314135210000_ref402","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1007\/s00145-003-0237-x","article-title":"Constructing\n      locally computable extractors and cryptosystems in the bounded-storage\n     model","volume":"17","author":"Vadhan","journal-title":"Journal of Cryptology"},{"issue":"3","key":"2026040314135210000_ref403","doi-asserted-by":"crossref","first-page":"278","DOI":"10.1016\/S0022-0000(76)80041-4","article-title":"Graph-theoretic properties in computational\n     complexity","volume":"13","author":"Valiant","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"2026040314135210000_ref404","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","article-title":"The\n      complexity of computing the permanent","volume":"8","author":"Valiant","journal-title":"Theoretical Computer\n      Science"},{"issue":"11","key":"2026040314135210000_ref405","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","article-title":"A theory of\n      the learnable","volume":"27","author":"Valiant","journal-title":"Communications of the ACM"},{"key":"2026040314135210000_ref406","first-page":"739","article-title":"Estimate of\n      the number of signals in error correcting codes","volume":"117","author":"Varshamov","year":"1957","journal-title":"Doklady\n      Akademe Nauk SSSR"},{"key":"2026040314135210000_ref407","first-page":"366","article-title":"Towards a\n      strong communication complexity theory or generating quasi-random sequences from two\n      communicating slightly-random sources (extended abstract)","author":"Vazirani","year":"1985","journal-title":"Proceedings of the Annual ACM Symposium on Theory of Computing"},{"key":"2026040314135210000_ref408","article-title":"Efficiency\n      considerations in using semi-random sources (extended abstract)","author":"Vazirani"},{"issue":"4","key":"2026040314135210000_ref409","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/BF02579325","article-title":"Strong\n      communication complexity or generating quasirandom sequences from two communicating semirandom\n      sources","volume":"7","author":"Vazirani","journal-title":"Combinatorica"},{"key":"2026040314135210000_ref410","first-page":"417","article-title":"Random\n      polynomial time is equal to slightly-random polynomial time","author":"Vazirani","year":"1985","journal-title":"Annual Symposium on Foundations of Computer Science"},{"issue":"13-3","key":"2026040314135210000_ref411","first-page":"147","article-title":"The complexity\n      of constructing pseudorandom generators from hard functions","volume":"13","author":"Viola","journal-title":"Computational Complexity"},{"issue":"5","key":"2026040314135210000_ref412","doi-asserted-by":"crossref","first-page":"1387","DOI":"10.1137\/050640941","article-title":"Pseudorandom\n      bits for constant-depth circuits with few arbitrary symmetric gates","volume":"36","author":"Viola","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"2026040314135210000_ref413","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/s00037-009-0273-5","article-title":"The sum of\n       d small-bias generators fools polynomials of degree\n      d","volume":"18","author":"Viola","journal-title":"Computational Complexity"},{"key":"2026040314135210000_ref414","doi-asserted-by":"crossref","article-title":"Extractors for\n      circuit sources","author":"Viola","DOI":"10.1109\/FOCS.2011.20"},{"issue":"1","key":"2026040314135210000_ref415","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1137\/100814998","article-title":"The complexity\n      of distributions","volume":"41","author":"Viola","journal-title":"SIAM Journal on Computing"},{"key":"2026040314135210000_ref416","volume-title":"Collected Works. Vol. V: Design of Computers, Theory of Automata and Numerical\n     Analysis","author":"von Neumann","year":"1963"},{"issue":"3","key":"2026040314135210000_ref417","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1016\/0022-0000(81)90033-7","article-title":"New hash\n      functions and their use in authentication and set equality","volume":"22","author":"Wegman","journal-title":"Journal of Computer and System Sciences"},{"key":"2026040314135210000_ref418","first-page":"231","article-title":"Improving\n      exhaustive search implies superpolynomial lower bounds","author":"Williams","year":"2010","journal-title":"STOC\u201910 \u2014 Proceedings of the 2010 ACM International Symposium on Theory\n      of Computing"},{"key":"2026040314135210000_ref419","first-page":"115","article-title":"Non-uniform\n      ACC circuit lower bounds","author":"Williams","year":"2011","journal-title":"IEEE Conference on Computational\n      Complexity"},{"key":"2026040314135210000_ref420","first-page":"90","article-title":"List\n      decoding","volume":"48","author":"Wozencraft","year":"1958","journal-title":"Quarterly Progress Report, Research Laboratory of\n      Electronics, MIT"},{"key":"2026040314135210000_ref421","first-page":"80","article-title":"Theory and\n      applications of trapdoor functions (extended abstract)","author":"Yao","year":"1982","journal-title":"Annual Symposium on Foundations of Computer Science"},{"issue":"2","key":"2026040314135210000_ref422","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/s00493-011-2604-9","article-title":"Affine\n      extractors over prime fields","volume":"31","author":"Yehudayoff","journal-title":"Combinatorica"},{"issue":"1","key":"2026040314135210000_ref423","doi-asserted-by":"crossref","DOI":"10.1145\/1326554.1326555","article-title":"Towards\n      3-query locally decodable codes of subexponential length","volume":"55","author":"Yekhanin","journal-title":"Journal of the ACM"},{"key":"2026040314135210000_ref424","author":"Yekhanin","journal-title":"Locally Decodable\n      Codes"},{"key":"2026040314135210000_ref425","doi-asserted-by":"crossref","article-title":"Probabilistic\n      algorithms for sparse polynomials","author":"Zippel","DOI":"10.1007\/3-540-09519-5_73"},{"key":"2026040314135210000_ref426","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF01940870","article-title":"Simulating\n      BPP using a general weak random source","volume":"16","author":"Zuckerman","year":"1996","journal-title":"Algorithmica"},{"issue":"4","key":"2026040314135210000_ref427","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z","article-title":"Randomness-optimal oblivious sampling","volume":"11","author":"Zuckerman","journal-title":"Random Structures & Algorithms"},{"issue":"4","key":"2026040314135210000_ref428","first-page":"29","article-title":"List cascade\n      decoding (in Russian)","volume":"17","author":"Zyablov","journal-title":"Problems of Information\n      Transmission"}],"container-title":["Foundations and Trends\u00ae in Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/7\/1-3\/1\/11159605\/0400000010en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/fttcs\/article-pdf\/7\/1-3\/1\/11159605\/0400000010en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T19:01:16Z","timestamp":1777489276000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/fttcs\/article\/7\/1-3\/1\/1332723\/Pseudorandomness"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,20]]},"references-count":428,"journal-issue":{"issue":"1-3","published-print":{"date-parts":[[2012,12,20]]}},"URL":"https:\/\/doi.org\/10.1561\/0400000010","relation":{},"ISSN":["1551-305X","1551-3068"],"issn-type":[{"value":"1551-305X","type":"print"},{"value":"1551-3068","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,20]]}}}