Explicit two-source extractors and resilient functions
From MaRDI portal
Publication:5361870
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
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
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
