On the randomness complexity of efficient sampling

DOI10.1145/1132516.1132615MaRDI QIDQ2931431zbMATH OpenOpenAlexFDO

Authors Bella Dubrov, Yuval Ishai

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

derandomizationcompressionpseudorandom generatorssecure computationinformation-theoretic cryptographyrandomness complexity

Mathematics Subject Classification ID

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

Recommendations

• Randomness-Efficient Sampling Within NC 1
• Randomness-efficient sampling within NC\(^{1}\)
• scientific article; zbMATH DE number 1097580
• Randomness-efficient curve samplers
• Efficient sampling of random permutations
• On the complexity of binary samples
• Sampling algorithms: lower bounds and applications
• On the efficiency of determinant sampling
• Pseudorandomness for approximate counting and sampling

Cited in

(30)

• On subset-resilient hash function families
• On bounded storage key agreement and one-way functions
• scientific article; zbMATH DE number 5763326 (Why is no real title available?)
• Computational indistinguishability: A sample hierarchy
• Brahms
• Infeasibility of instance compression and succinct PCPs for NP
• On Seed-Incompressible Functions
• scientific article; zbMATH DE number 1256745 (Why is no real title available?)
• Limits of preprocessing
• Basing Weak Public-Key Cryptography on Strong One-Way Functions
• scientific article; zbMATH DE number 4186980 (Why is no real title available?)
• Low communication complexity protocols, collision resistant hash functions and secret key-agreement protocols
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions
• Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits
• Placing conditional disclosure of secrets in the communication complexity universe
• Making the best of a leaky situation: zero-knowledge PCPs from leakage-resilient circuits
• Sampling lower bounds: Boolean average-case and permutations
• Incompressible functions, relative-error extractors, and the power of nondeterministic reductions (extended abstract)
• Adversarially robust property-preserving hash functions
• Collision-resistance from multi-collision-resistance
• Language compression and pseudorandom generators
• Collision Resistance from Multi-collision Resistance
• Pseudorandom generators with optimal seed length for non-Boolean poly-size circuits
• (Inefficient prover) ZAPs from hard-to-invert functions
• Instance compression, revisited
• Quantum advantage from one-way functions
• The gap is sensitive to size of preimages: collapsing property doesn't go beyond quantum collision-resistance for preimages bounded hash functions
• One-Way Functions and (Im)perfect Obfuscation
• On the efficiency of determinant sampling
• scientific article; zbMATH DE number 7561745 (Why is no real title available?)

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

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