Explicit two-source extractors and resilient functions

DOI10.1145/2897518.2897528zbMath1376.68101OpenAlexW2417650483MaRDI QIDQ5361870

David Zuckerman, Eshan Chattopadhyay

Publication date: 29 September 2017

Published in: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2897518.2897528

zbMATH Keywords

pseudorandomnessresilient functionRamsey graphrandomness extractortwo-source extractor

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Combinatorics in computer science (68R05) Generalized Ramsey theory (05C55) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (31)

Non-malleable codes for bounded parallel-time tampering ⋮ Improved computational extractors and their applications ⋮ Ramsey properties of algebraic graphs and hypergraphs ⋮ No time to hash: on super-efficient entropy accumulation ⋮ Local Correlation Breakers and Applications to Three-Source Extractors and Mergers ⋮ An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy ⋮ Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture ⋮ Unnamed Item ⋮ Induced Subgraphs With Many Distinct Degrees ⋮ The work of Mark Braverman ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Tight Upper and Lower Bounds for Leakage-Resilient, Locally Decodable and Updatable Non-malleable Codes ⋮ Tight upper and lower bounds for leakage-resilient, locally decodable and updatable non-malleable codes ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ An algebraic inverse theorem for the quadratic Littlewood-Offord problem, and an application to Ramsey graphs ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ Counting rectangles and an improved restriction estimate for the paraboloid in $F_p^3$ ⋮ Extracting randomness from extractor-dependent sources ⋮ Low error efficient computational extractors in the CRS model ⋮ Unnamed Item ⋮ Multi-source non-malleable extractors and applications ⋮ AN EXPLICIT TWO‐SOURCE EXTRACTOR WITH MIN‐ENTROPY RATE NEAR ⋮ Near-optimal pseudorandom generators for constant-depth read-once formulas ⋮ Proof of a conjecture on induced subgraphs of Ramsey graphs ⋮ Large cliques and independent sets all over the place ⋮ Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs ⋮ Lower bounds for matrix factorization

This page was built for publication: Explicit two-source extractors and resilient functions