Deterministic extractors for small-space sources
From MaRDI portal
Publication:5894074
DOI10.1016/j.jcss.2010.06.014zbMath1232.68094OpenAlexW2593857686MaRDI QIDQ5894074
David Zuckerman, Anup Rao, Jesse Kamp, Salil P. Vadhan
Publication date: 18 January 2011
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:12724035
Markov chainspseudorandomnessrandomness extractorsbit-fixing sourcesindependent sourcessamplable sources
Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
No time to hash: on super-efficient entropy accumulation, Extractors for varieties, On secret sharing, randomness, and random-less reductions for secret sharing, Speak much, remember little: cryptography in the bounded storage model, revisited, Improved Extractors for Recognizable and Algebraic Sources, An Introduction to Randomness Extractors, Proved Random Numbers Obtained from Hardware Devices, Improving the Hadamard extractor, Extractors and Lower Bounds for Locally Samplable Sources, Extracting randomness from extractor-dependent sources, How to extract useful randomness from unreliable sources, Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition, The complexity of estimating min-entropy
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Some extremal problems arising from discrete control processes
- Generating quasi-random sequences from semi-random sources
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources
- Expanders that beat the eigenvalue bound: Explicit construction and applications
- Universal classes of hash functions
- Extracting randomness: A survey and new constructions
- Independent unbiased coin flips from a correlated biased source - a finite state Markov chain
- Constructing locally computable extractors and cryptosystems in the bounded-storage model
- Randomness is linear in space
- Simulating BPP using a general weak random source
- Extractors for a constant number of polynomially small min-entropy independent sources
- Analyzing linear mergers
- Extractors with weak random seeds
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- Privacy Amplification by Public Discussion
- MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
- Deterministic Extractors for Bit‐Fixing Sources and Exposure‐Resilient Cryptography
- Extractors and pseudorandom generators
- ESTIMATES FOR THE NUMBER OF SUMS AND PRODUCTS AND FOR EXPONENTIAL SUMS IN FIELDS OF PRIME ORDER
- Deterministic Extractors for Bit‐Fixing Sources by Obtaining an Independent Seed
- Extracting Randomness Using Few Independent Sources
- Cryptography and Coding
- Simulating independence
- Extracting all the randomness and reducing the error in Trevisan's extractors
