Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes

DOI10.1145/1538902.1538904zbMATH Open1325.68169OpenAlexW2090418561MaRDI QIDQ3452216FDOQ3452216

Authors: Christopher Umans, Venkatesan Guruswami, Salil 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

Recommendations

• Loss-less condensers, unbalanced expanders, and extractors
• Lossless condensers, unbalanced expanders, and extractors
• List Decoding and Pseudorandom Constructions
• Extractors for Three Uneven-Length Sources
• Extracting all the randomness and reducing the error in Trevisan's extractors

zbMATH Keywords

expander graphscondenserserror-correcting codeslist decodingrandomness extractors

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Other types of codes (94B60)

Cited In (71)

• Improving the space-bounded version of Muchnik's conditional complexity theorem via ``naive derandomization
• Expander-Based Cryptography Meets Natural Proofs
• Additive combinatorics: with a view towards computer science and cryptography -- an exposition
• Title not available (Why is that?)
• Bounded-depth circuits cannot sample good codes
• List-decoding Barnes-Wall lattices
• Parallel Hashing via List Recoverability
• Title not available (Why is that?)
• Unconditional UC-Secure Computation with (Stronger-Malicious) PUFs
• Immunization against complete subversion without random oracles
• From graphs to keyed quantum hash functions
• An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy
• Privacy amplification with asymptotically optimal entropy loss
• Lossless dimension expanders via linearized polynomials and subspace designs
• Expander-based cryptography meets natural proofs
• Universal Security for Randomness Expansion from the Spot-Checking Protocol
• Title not available (Why is that?)
• Game-theoretic fairness meets multi-party protocols: the case of leader election
• Derandomized construction of combinatorial batch codes
• The complexity of the matroid-greedoid partition problem
• Increasing the output length of zero-error dispersers
• Pseudo-random graphs and bit probe schemes with one-sided error
• On Low-Risk Heavy Hitters and Sparse Recovery Schemes
• Improved computational extractors and their applications
• Flavors of Compressive Sensing
• Non-interactive timestamping in the bounded-storage model
• Local List Recovery of High-Rate Tensor Codes and Applications
• Title not available (Why is that?)
• On rigid matrices and \(U\)-polynomials
• Extractors and lower bounds for locally samplable sources
• Title not available (Why is that?)
• Zero-fixing extractors for sub-logarithmic entropy
• Quantified Derandomization: How to Find Water in the Ocean
• Explicit two-source extractors and resilient functions
• Short lists for shortest descriptions in short time
• Better short-seed quantum-proof extractors
• How to extract useful randomness from unreliable sources
• Low error efficient computational extractors in the CRS model
• Side-channel masking with pseudo-random generator
• A sample of samplers: a computational perspective on sampling
• Extractor codes
• Four-state non-malleable codes with explicit constant rate
• An introduction to randomness extractors
• Non-malleability against polynomial tampering
• Corrigendum: Explicit Construction of a Small Epsilon-Net for Linear Threshold Functions
• Increasing the Output Length of Zero-Error Dispersers
• A PCP theorem for interactive proofs and applications
• Submodular Functions: Learnability, Structure, and Optimization
• Derandomized parallel repetition theorems for free games
• A combinatorial approach to quantum random functions
• Title not available (Why is that?)
• Shift lifts preserving Ramanujan property
• Local Correlation Breakers and Applications to Three-Source Extractors and Mergers
• Improved constructions for non-adaptive threshold group testing
• Certifiable quantum dice
• Adaptive extractors and their application to leakage resilient secret sharing
• List Decoding and Pseudorandom Constructions
• Title not available (Why is that?)
• Extractors: low entropy requirements colliding with non-malleability
• Certifiably Pseudorandom Financial Derivatives
• Paradigms for Unconditional Pseudorandom Generators
• Title not available (Why is that?)
• Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace
• Title not available (Why is that?)
• Nonmalleable Extractors and Codes, with Their Many Tampered Extensions
• Singleton-type bounds for list-decoding and list-recovery, and related results
• Sampling Graphs without Forbidden Subgraphs and Unbalanced Expanders with Negligible Error
• Simple Codes and Sparse Recovery with Fast Decoding
• Almost Chor-Goldreich sources and adversarial random walks
• Nearly optimal pseudorandomness from hardness
• Improved List-Decodability and List-Recoverability of Reed–Solomon Codes via Tree Packings

This page was built for publication: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452216)