On the Complexity of Computational Problems Regarding Distributions

DOI10.1007/978-3-642-22670-0_27zbMath1343.68115OpenAlexW1522202519MaRDI QIDQ3088193

Oded Goldreich, Salil P. Vadhan

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_27

zbMATH Keywords

entropyapproximationreductionspromise problemszero-knowledgevariation distancesampleable distributionsstatistical difference

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Measures of information, entropy (94A17) Statistical distribution theory (62E99) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

New Limits to Classical and Quantum Instance Compression, AND-compression of NP-complete problems: streamlined proof and minor observations, Statistical difference beyond the polarizing regime, Bounds from a card trick, Minimum Circuit Size, Graph Isomorphism, and Related Problems, Communication Complexity of Statistical Distance

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Statistical zero-knowledge languages can be recognized in two rounds
• Universal classes of hash functions
• A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm
• Spot-checkers
• Property testing and its connection to learning and approximation
• The complexity of approximating entropy
• The complexity of promise problems with applications to public-key cryptography
• The Knowledge Complexity of Interactive Proof Systems
• The Wire-Tap Channel
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• Robust Characterizations of Polynomials with Applications to Program Testing