Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
From MaRDI portal
Publication:3452216
DOI10.1145/1538902.1538904zbMath1325.68169OpenAlexW2090418561MaRDI QIDQ3452216
Christopher Umans, Venkatesan Guruswami, Salil P. Vadhan
Publication date: 11 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://resolver.caltech.edu/CaltechAUTHORS:20170426-160240908
Graph theory (including graph drawing) in computer science (68R10) Other types of codes (94B60) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (67)
Shift lifts preserving Ramanujan property ⋮ From graphs to keyed quantum hash functions ⋮ Expander-based cryptography meets natural proofs ⋮ Game-theoretic fairness meets multi-party protocols: the case of leader election ⋮ Improved computational extractors and their applications ⋮ Adaptive extractors and their application to leakage resilient secret sharing ⋮ Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions ⋮ Zero-Fixing Extractors for Sub-Logarithmic Entropy ⋮ Parallel Hashing via List Recoverability ⋮ Quantified Derandomization: How to Find Water in the Ocean ⋮ 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 ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ A PCP theorem for interactive proofs and applications ⋮ Derandomized parallel repetition theorems for free games ⋮ Improved constructions for non-adaptive threshold group testing ⋮ Certifiable quantum dice ⋮ List-decoding Barnes-Wall lattices ⋮ Derandomized Construction of Combinatorial Batch Codes ⋮ Universal Security for Randomness Expansion from the Spot-Checking Protocol ⋮ Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error ⋮ Simple Codes and Sparse Recovery with Fast Decoding ⋮ Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings ⋮ Extractors: low entropy requirements colliding with non-malleability ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ On rigid matrices and \(U\)-polynomials ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Singleton-type bounds for list-decoding and list-recovery, and related results ⋮ A combinatorial approach to quantum random functions ⋮ Local List Recovery of High-Rate Tensor Codes and Applications ⋮ Unnamed Item ⋮ Flavors of Compressive Sensing ⋮ Unnamed Item ⋮ Nonmalleable Extractors and Codes, with Their Many Tampered Extensions ⋮ Increasing the Output Length of Zero-Error Dispersers ⋮ Short lists for shortest descriptions in short time ⋮ Immunization against complete subversion without random oracles ⋮ Lossless dimension expanders via linearized polynomials and subspace designs ⋮ On Low-Risk Heavy Hitters and Sparse Recovery Schemes ⋮ An Introduction to Randomness Extractors ⋮ Bounded-depth circuits cannot sample good codes ⋮ Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization ⋮ Pseudo-random graphs and bit probe schemes with one-sided error ⋮ Unconditional UC-Secure Computation with (Stronger-Malicious) PUFs ⋮ Privacy amplification with asymptotically optimal entropy loss ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Four-state non-malleable codes with explicit constant rate ⋮ The complexity of the matroid-greedoid partition problem ⋮ Extractors and Lower Bounds for Locally Samplable Sources ⋮ Non-interactive timestamping in the bounded-storage model ⋮ How to extract useful randomness from unreliable sources ⋮ Low error efficient computational extractors in the CRS model ⋮ A Sample of Samplers: A Computational Perspective on Sampling ⋮ Side-channel masking with pseudo-random generator ⋮ Unnamed Item ⋮ Expander-Based Cryptography Meets Natural Proofs ⋮ Better short-seed quantum-proof extractors ⋮ Explicit two-source extractors and resilient functions ⋮ Additive Combinatorics: With a View Towards Computer Science and Cryptography—An Exposition ⋮ Certifiably Pseudorandom Financial Derivatives ⋮ Increasing the output length of zero-error dispersers ⋮ Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace ⋮ Non-malleability against polynomial tampering
This page was built for publication: Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
