A Sample of Samplers: A Computational Perspective on Sampling

DOI10.1007/978-3-642-22670-0_24zbMath1343.68297OpenAlexW198177064MaRDI QIDQ3088190

Oded Goldreich

Publication date: 19 August 2011

Published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22670-0_24

zbMATH Keywords

samplingrandom walks on graphsexpander graphspairwise independent random variablesrandomness complexityinformation-theoretic lower boundssaving randomness

Mathematics Subject Classification ID

Randomized algorithms (68W20) Sampling theory in information and communication theory (94A20) Random walks on graphs (05C81) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

Well-mixing vertices and almost expanders, The Untold Story of $$\mathsf {SBP}$$, A classification of the probabilistic polynomial time hierarchy under fault tolerant access to oracle classes, Compact proofs of retrievability, An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy, Derandomized parallel repetition theorems for free games, Unnamed Item, Unnamed Item, How to recover a secret with \(O(n)\) additions, Expander graphs and their applications, Simple Optimal Hitting Sets for Small-Success RL, How to get more mileage from randomness extractors, Lower bounds against sparse symmetric functions of ACC circuits: expanding the reach of \#SAT algorithms, Amplification and Derandomization without Slowdown, Pseudorandom Pseudo-distributions with Near-Optimal Error for Read-Once Branching Programs, Increasing the Output Length of Zero-Error Dispersers, Must the communication graph of MPC protocols be an expander?, Unnamed Item, Unnamed Item, Reusable fuzzy extractors for low-entropy distributions, Imperfect gaps in Gap-ETH and PCPs, Fast Interactive Coding against Adversarial Noise

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Eigenvalues, geometric expanders, sorting in rounds, and Ramsey theory
• Lower bounds for sampling algorithms for estimating the average
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• On the power of two-point based sampling
• Explicit constructions of linear-sized superconcentrators
• Universal classes of hash functions
• Randomness in interactive proofs
• Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
• Expander graphs and their applications
• Shift Register Sequences – A Retrospective Account
• Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs
• Eigenvalues and expansion of regular graphs
• Tiny families of functions with random properties: A quality-size trade-off for hashing
• Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
• Sampling algorithms