On the randomness complexity of efficient sampling

DOI10.1145/1132516.1132615zbMath1301.68261OpenAlexW1980147712MaRDI QIDQ2931431

Yuval Ishai, Bella Dubrov

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1132516.1132615

zbMATH Keywords

compressionderandomizationpseudorandom generatorssecure computationinformation-theoretic cryptographyrandomness complexity

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Cryptography (94A60) Randomized algorithms (68W20) Sampling theory in information and communication theory (94A20)

Related Items (14)

One-Way Functions and (Im)perfect Obfuscation ⋮ Incompressible functions, relative-error extractors, and the power of nondeterministic reductions ⋮ Infeasibility of instance compression and succinct PCPs for NP ⋮ Collision-resistance from multi-collision-resistance ⋮ The gap is sensitive to size of preimages: collapsing property doesn't go beyond quantum collision-resistance for preimages bounded hash functions ⋮ Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Basing Weak Public-Key Cryptography on Strong One-Way Functions ⋮ Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits ⋮ Placing conditional disclosure of secrets in the communication complexity universe ⋮ Sampling Lower Bounds: Boolean Average-Case and Permutations ⋮ A Mathematical Problem for Security Analysis of Hash Functions and Pseudorandom Generators ⋮ On subset-resilient hash function families

This page was built for publication: On the randomness complexity of efficient sampling