An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
From MaRDI portal
Publication:5073519
DOI10.1137/17M1133245OpenAlexW2988618147MaRDI QIDQ5073519
Dean Doron, Avraham Ben-Aroya, Amnon Ta-Shma
Publication date: 3 May 2022
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/17m1133245
Ramsey theory (05D10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Constructing Ramsey graphs from Boolean function representations
- The influence of large coalitions
- Almost \(k\)-wise independence versus \(k\)-wise independence
- Intersection theorems with geometric consequences
- The Shannon capacity of a union
- 2-source dispersers for \(n^{o(1)}\) entropy, and Ramsey graphs beating the Frankl-Wilson construction
- Low rank co-diagonal matrices and Ramsey graphs
- Linear degree extractors and the inapproximability of max clique and chromatic number
- A Sample of Samplers: A Computational Perspective on Sampling
- Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
- Extractors with weak random seeds
- Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity
- A note on constructive methods for ramsey numbers
- Explicit Resilient Functions Matching Ajtai-Linial
- Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
- Improved non-malleable extractors, non-malleable codes and independent source extractors
- Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources
- MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS
- Two-source dispersers for polylogarithmic entropy and improved ramsey graphs
- Explicit two-source extractors and resilient functions
- Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers
- Key Derivation without Entropy Waste
- Extractors for Circuit Sources
- New independent source extractors with exponential improvement
- Extracting Randomness Using Few Independent Sources
- Some remarks on the theory of graphs
- Extracting all the randomness and reducing the error in Trevisan's extractors
- Simulating independence
- Lower bounds for some Ramsey numbers
This page was built for publication: An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
