On the Complexity of Computational Problems Regarding Distributions
type: Item
instance of: scholarly article
title: On the Complexity of Computational Problems Regarding Distributions
zbMATH Open document ID: 1343.68115
DOI: 10.1007/978-3-642-22670-0_27
author: Oded Goldreich
author: Salil Vadhan
published in: Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation
publication date: 2011-08-19T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 62E99
Mathematics Subject Classification ID: 68Q87
Mathematics Subject Classification ID: 94A17
zbMATH DE Number: 5940595
zbMATH Keywords: approximation
zbMATH Keywords: reductions
zbMATH Keywords: entropy
zbMATH Keywords: statistical difference
zbMATH Keywords: variation distance
zbMATH Keywords: sampleable distributions
zbMATH Keywords: zero-knowledge
zbMATH Keywords: promise problems
MaRDI profile type: Publication
full work available at URL: 978-3-642-22670-0 27
OpenAlex ID: W1522202519
cites work: Statistical zero-knowledge languages can be recognized in two rounds
cites work: Q4783716
cites work: The complexity of approximating entropy
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: Universal classes of hash functions
cites work: Spot-checkers
cites work: The complexity of promise problems with applications to public-key cryptography
cites work: Property testing and its connection to learning and approximation
cites work: A perfect zero-knowledge proof system for a problem equivalent to the discrete logarithm
cites work: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems
cites work: Q4542558
cites work: Q4941874
cites work: The Knowledge Complexity of Interactive Proof Systems
cites work: Q4228522
cites work: Robust Characterizations of Polynomials with Applications to Program Testing
cites work: The Wire-Tap Channel
description: scientific article