Extracting all the randomness and reducing the error in Trevisan's extractors
From MaRDI portal
Publication:5917498
DOI10.1006/JCSS.2002.1824zbMath1020.68029OpenAlexW3138266838MaRDI QIDQ5917498
Ran Raz, Salil P. Vadhan, Omer Reingold
Publication date: 4 May 2003
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:2958609
Related Items (25)
Quantified Derandomization: How to Find Water in the Ocean ⋮ Deterministic extractors for affine sources over large fields ⋮ 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction ⋮ Short leakage resilient and non-malleable secret sharing schemes ⋮ On secret sharing, randomness, and random-less reductions for secret sharing ⋮ Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\) ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Cryptography from one-way communication: on completeness of finite channels ⋮ Nonmalleable Extractors and Codes, with Their Many Tampered Extensions ⋮ Deterministic extractors for small-space sources ⋮ An Introduction to Randomness Extractors ⋮ Proved Random Numbers Obtained from Hardware Devices ⋮ Pseudo-random graphs and bit probe schemes with one-sided error ⋮ Dispersing hash functions ⋮ Unnamed Item ⋮ Optimal explicit small-depth formulas for the coin problem ⋮ A duality between one-way functions and average-case symmetry of information ⋮ Unnamed Item ⋮ On derandomized composition of Boolean functions ⋮ Nearly optimal pseudorandomness from hardness ⋮ Non-interactive timestamping in the bounded-storage model ⋮ Multicast Routing and Design of Sparse Connectors ⋮ Explicit two-source extractors and resilient functions ⋮ Resource bounded symmetry of information revisited
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On a packing and covering problem
- Families of finite sets in which no set is covered by the union of \(r\) others
- Generating quasi-random sequences from semi-random sources
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- Expanders, randomness, or time versus space
- Expanders that beat the eigenvalue bound: Explicit construction and applications
- Hardness vs randomness
- Entropy waves, the zig-zag graph product, and new constant-degree expanders
- Randomness is linear in space
- Simulating BPP using a general weak random source
- Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs
- Learning Polynomials with Queries: The Highly Noisy Case
- Construction of extractors using pseudo-random generators (extended abstract)
- On recycling the randomness of states in space bounded computation
- Pseudorandom generators without the XOR Lemma (extended abstract)
- Extractors and pseudo-random generators with optimal seed length
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Sorting and Selecting in Rounds
- Explicit OR-dispersers with polylogarithmic degree
- Tiny families of functions with random properties: A quality-size trade-off for hashing
- Free Bits, PCPs, and Nonapproximability---Towards Tight Results
- Loss-less condensers, unbalanced expanders, and extractors
- Extracting all the randomness and reducing the error in Trevisan's extractors
This page was built for publication: Extracting all the randomness and reducing the error in Trevisan's extractors
