{"corpus_id":14031194,"paper_sha":"0a385cf3c6eb2826b136d4fae192dec526069547","doi":"10.1145/100216.100244","arxiv_id":null,"pmid":null,"pmcid":null,"mag_id":2007671490,"dblp_id":"conf/stoc/NaorN90","acl_id":null,"title":"Small-bias probability spaces: efficient constructions and applications","year":1990,"publication_date":"1990-04-01","venue":"Symposium on the Theory of Computing","journal":{"name":null,"pages":"213-223","volume":null},"journal_issn":null,"journal_title":null,"publication_types":["JournalArticle"],"pubmed_pub_types":null,"s2_fields_of_study":["Mathematics","Computer Science"],"reference_count":57,"citation_count":855,"influential_citation_count":105,"is_open_access":false,"arxiv_categories":null,"arxiv_license":null,"arxiv_journal_ref":null,"mesh_headings":null,"chemicals":null,"comments_corrections":null,"source_flags":1,"s2_open_access_pdf_url":null,"s2_open_access_landing_url":null,"s2_open_access_license":null,"s2_open_access_status":null,"pmc_open_access_pdf_url":null,"pmc_open_access_landing_url":null,"pmc_open_access_license":null,"pmc_open_access_status":null,"unpaywall_open_access_pdf_url":null,"unpaywall_open_access_landing_url":null,"unpaywall_open_access_license":null,"unpaywall_open_access_status":null,"abstract":"We show how to efficiently construct a small probability space on n binary random variables such that for every subset, its parity is either zero or one with \"almost\" equal probability. They are called e-biased random variables. The number of random bits needed to generate the random variables is O(logn log ~). Thus, if e is polynomially small, then the size of the sample space is also polynomial. e-biased random variables can be used to construct \"almost\" k-wise independent random variables where e is a function of k. Applications are shown to derandomization of algorithms, reducing the number of random bits required by certain randomized algorithms, exhaustive testing of combinatorial circuits, communication complexity and construction of hash functions.","claims":[{"public_id":"cl_63c26341227a332a51993c077676a570","status":"active","text":"A small probability space on n binary random variables can be constructed efficiently so that every subset has parity zero or one with nearly equal probability.","confidence":0.98,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_63c26341227a332a51993c077676a570"},{"public_id":"cl_2076ac1a6993dbf478deb0034a448cf8","status":"active","text":"The construction uses O(log n log ~) random bits, and when e is polynomially small the sample space size is polynomial.","confidence":0.94,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_2076ac1a6993dbf478deb0034a448cf8"},{"public_id":"cl_da7470527ef68418e2c0cdfeaa4cf870","status":"active","text":"These constructions have applications to derandomization, reducing random-bit usage in randomized algorithms, exhaustive testing of combinatorial circuits, communication complexity, and hash function construction.","confidence":0.92,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_da7470527ef68418e2c0cdfeaa4cf870"},{"public_id":"cl_4187945e97fbc21138eb3eda31017cc3","status":"active","text":"e-biased random variables can be used to construct almost k-wise independent random variables, with e chosen as a function of k.","confidence":0.96,"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/claims/cl_4187945e97fbc21138eb3eda31017cc3"}],"concepts":[{"public_id":"co_00c03ec91fadd81ac1b3e985e78362c6","status":"active","name":"e-biased random variables","description":"Binary random variables whose every subset parity is close to uniformly distributed, within bias e.","types":["random variables"],"aliases":["biased random variables"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_00c03ec91fadd81ac1b3e985e78362c6"},{"public_id":"co_1f2b3400880b94b43f5165bfea276892","status":"active","name":"almost k-wise independent random variables","description":"Random variables whose joint distributions on subsets of size up to k are nearly independent.","types":["random variables"],"aliases":["approximate k-wise independent random variables"],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_1f2b3400880b94b43f5165bfea276892"},{"public_id":"co_4e4759d539e8a219a886c1c10f48e812","status":"active","name":"randomized algorithms","description":"Algorithms that use random choices during execution.","types":["algorithm class"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_4e4759d539e8a219a886c1c10f48e812"},{"public_id":"co_4e5b5b86ddf9f5a18120ad8ef5c4d7db","status":"active","name":"sample space","description":"The set of possible outcomes used to realize the random variables.","types":["mathematical object"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_4e5b5b86ddf9f5a18120ad8ef5c4d7db"},{"public_id":"co_576f0c276c072a278e7d9f94b5f0065a","status":"active","name":"exhaustive testing of combinatorial circuits","description":"A testing application in which combinatorial circuits are checked across many input configurations.","types":["application"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_576f0c276c072a278e7d9f94b5f0065a"},{"public_id":"co_57c5312d21cd6b7eec251adee0c042e3","status":"active","name":"n binary random variables","description":"A collection of n random variables, each taking values in {0,1}.","types":["random variables"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_57c5312d21cd6b7eec251adee0c042e3"},{"public_id":"co_8dbf01785d0fe35feaf622cfe75cef5d","status":"active","name":"k-wise independence","description":"A property in which any k variables are jointly independent.","types":["property"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_8dbf01785d0fe35feaf622cfe75cef5d"},{"public_id":"co_ab8a8e7fdb4e0da3b0d2151b0b23c0e8","status":"active","name":"communication complexity","description":"A complexity-theoretic setting concerned with the amount of communication needed between parties to compute a function.","types":["research area"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_ab8a8e7fdb4e0da3b0d2151b0b23c0e8"},{"public_id":"co_be57793bab1ce6d57aa723af73b08754","status":"active","name":"random bits","description":"Random bits used to sample or generate the random variables in a construction.","types":["resource"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_be57793bab1ce6d57aa723af73b08754"},{"public_id":"co_c09436ab28556a30d98f605ff0187667","status":"active","name":"small probability space","description":"A probability space with a limited number of outcomes used to generate random variables efficiently.","types":["mathematical object"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_c09436ab28556a30d98f605ff0187667"},{"public_id":"co_d40e17394ccc66fa7d98daf4ca4cbb00","status":"active","name":"derandomization of algorithms","description":"The use of pseudorandom constructions to reduce or eliminate randomness in algorithms.","types":["application"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_d40e17394ccc66fa7d98daf4ca4cbb00"},{"public_id":"co_feaf2ba7a0a6869daf3c2ce5a59c869c","status":"active","name":"hash functions","description":"Functions that map inputs into hash values for randomized or algorithmic use.","types":["function"],"aliases":[],"contributors":[{"id":1,"public_id":"12632b8b5f","public_label":"Anonymous (12632b8b5f)","roles":["extraction"],"url":"https://sah.borca.ai/u/12632b8b5f"}],"url":"https://sah.borca.ai/concepts/co_feaf2ba7a0a6869daf3c2ce5a59c869c"}],"external_ids":{"DOI":"10.1145/100216.100244","ArXiv":null,"PubMed":null,"PubMedCentral":null,"MAG":2007671490,"DBLP":"conf/stoc/NaorN90","ACL":null},"open_access":{"is_open_access":false,"pdf_url":null,"landing_url":"https://sah.borca.ai/papers/14031194","source":null,"pdf_url_source":null,"license":null,"reason":"pdf_url_not_indexed"},"reference_availability":{"status":"available","references_indexed":true,"full_text_available":false,"full_text_source":null,"count_basis":"semantic_scholar_metadata","extraction_status":"not_applicable","reason":null},"source":{"provider":"episteme2","base_corpus":"semantic_scholar_dump","freshness_mode":"unknown","basis":["semantic_scholar_metadata","postgres_metadata"],"limits":["paper metadata is based on indexed upstream scholarly datasets","claims and concepts are available only for extracted papers","absence of claims or concepts means no extracted graph data is available in this response"],"status":"available","degraded":false,"degraded_reasons":[],"diagnostics":{"status":"available","degraded":false,"degraded_reasons":[],"metadata_status":"available","graph_status":"available","abstract_status":"available"},"source_flags":1},"paper_id":635529,"paper_uid":"72a89810-f76f-495f-a91c-346bd09de7e1","canonical_identity":{"paper_id":635529,"paper_uid":"72a89810-f76f-495f-a91c-346bd09de7e1","identity_status":"available","lookup_basis":"semantic_scholar_external_id","compatibility_path":"corpus_id"},"url":"https://sah.borca.ai/papers/14031194"}