On the complexity of computational problems regarding distributions

DOI10.1007/978-3-642-22670-0_27MaRDI QIDQ3088193zbMATH OpenOpenAlexFDO

Authors Oded Goldreich, Salil 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

approximationentropypromise problemsreductionssampleable distributionsstatistical differencevariation distancezero-knowledge

Mathematics Subject Classification ID

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

Recommendations

• The Complexity of Approximating the Entropy
• On the learnability of discrete distributions
• Testing closeness of discrete distributions
• Communication complexity of statistical distance
• Communication complexity of statistical distance

Cites work

• A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm
• Free Bits, PCPs, and Nonapproximability---Towards Tight Results
• scientific article; zbMATH DE number 1256785 (Why is no real title available?)
• scientific article; zbMATH DE number 1775425 (Why is no real title available?)
• scientific article; zbMATH DE number 1842483 (Why is no real title available?)
• scientific article; zbMATH DE number 1418312 (Why is no real title available?)
• Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Spot-checkers
• Statistical zero-knowledge languages can be recognized in two rounds
• 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
• Universal classes of hash functions

Cited in

(16)

• Complexity of monotone modelling algorithms for discrete distributions
• Statistical difference beyond the polarizing regime
• The complexity of estimating min-entropy
• scientific article; zbMATH DE number 6474904 (Why is no real title available?)
• scientific article; zbMATH DE number 4129950 (Why is no real title available?)
• New limits to classical and quantum instance compression
• scientific article; zbMATH DE number 3909744 (Why is no real title available?)
• scientific article; zbMATH DE number 177818 (Why is no real title available?)
• Bounds from a card trick
• scientific article; zbMATH DE number 1875916 (Why is no real title available?)
• The Complexity and Distribution of Hard Problems
• Minimum circuit size, graph isomorphism, and related problems
• Communication complexity of statistical distance
• An approximate distribution for the maximum order complexity
• Distribution-free proofs of proximity
• Quantum state testing beyond the polarizing regime and quantum triangular discrimination

This page was built for publication: On the complexity of computational problems regarding distributions

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