Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
From MaRDI portal
Publication:4943700
DOI10.1137/S0895480197329508zbMath1023.94025OpenAlexW2035532007WikidataQ62398496 ScholiaQ62398496MaRDI QIDQ4943700
Amnon Ta-Shma, Jaikumar Radhakrishnan
Publication date: 19 March 2000
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895480197329508
Extremal problems in graph theory (05C35) Applications of graph theory (05C90) Measures of information, entropy (94A17) Applications of graph theory to circuits and networks (94C15)
Related Items
Sampling Correctors ⋮ The size‐Ramsey number of trees ⋮ Condensed Unpredictability ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ Shannon Entropy Versus Renyi Entropy from a Cryptographic Viewpoint ⋮ On complexity of linear operators on the class of circuits of depth 2 ⋮ An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy ⋮ Unnamed Item ⋮ Constructions of given-depth and optimal multirate rearrangeably nonblocking distributors ⋮ Metric Pseudoentropy: Characterizations, Transformations and Applications ⋮ Lower bounds for complexity of Boolean circuits of finite depth with arbitrary elements ⋮ Lower Bounds for Depth-2 and Depth-3 Boolean Circuits with Arbitrary Gates ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Variations on Muchnik's conditional complexity theorem ⋮ How to get more mileage from randomness extractors ⋮ Weak derandomization of weak algorithms: explicit versions of Yao's lemma ⋮ Bounded-Retrieval Model with Keys Derived from Private Data ⋮ Increasing the Output Length of Zero-Error Dispersers ⋮ Min-rank conjecture for log-depth circuits ⋮ Lossless dimension expanders via linearized polynomials and subspace designs ⋮ Short lists with short programs in short time ⋮ An Introduction to Randomness Extractors ⋮ Extractor Lower Bounds, Revisited ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ Privacy amplification with asymptotically optimal entropy loss ⋮ Entropy of operators or why matrix multiplication is hard for depth-two circuits ⋮ Simple extractors via constructions of cryptographic pseudo-random generators ⋮ Extractors from Reed-Muller codes ⋮ Unnamed Item ⋮ Optimal Sparse Designs for Process Flexibility via Probabilistic Expanders ⋮ Lower bounds for matrix factorization ⋮ Inapproximability of b-Matching in k-Uniform Hypergraphs ⋮ How to extract useful randomness from unreliable sources ⋮ A Sample of Samplers: A Computational Perspective on Sampling ⋮ Unnamed Item ⋮ Better short-seed quantum-proof extractors ⋮ Representing \((0,1)\)-matrices by Boolean circuits ⋮ Lower bounds for matrix factorization ⋮ Increasing the output length of zero-error dispersers ⋮ Can We Construct Unbounded Time-Stamping Schemes from Collision-Free Hash Functions? ⋮ Efficient Construction of Rigid Matrices Using an NP Oracle ⋮ Estimating security of the quantum key distribution from the guesswork ⋮ Quantum Authentication and Encryption with Key Recycling ⋮ Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization
