Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > SAMPLABLE DISTRIBUTIONS:
Reports tagged with Samplable distributions:
TR00-084 | 6th November 2000

#### A Complete Problem for Statistical Zero Knowledge

We present the first complete problem for SZK, the class of (promise)
problems possessing statistical zero-knowledge proofs (against an
honest verifier). The problem, called STATISTICAL DIFFERENCE, is to
decide whether two efficiently samplable distributions are either
statistically close or far apart. This gives a new characterization
of SZK that makes ... more >>>

TR05-145 | 5th December 2005
Ronen Shaltiel

#### How to get more mileage from randomness extractors

Let $\cal C$ be a class of distributions over $\B^n$. A deterministic randomness extractor for $\cal C$ is a function $E:\B^n \ar \B^m$ such that for any $X$ in $\cal C$ the distribution $E(X)$ is statistically close to the uniform distribution. A long line of research deals with explicit constructions ... more >>>

TR10-091 | 14th May 2010
Nikolay Vereshchagin

#### An Encoding Invariant Version of Polynomial Time Computable Distributions

When we represent a decision problem,like CIRCUIT-SAT, as a language over the binary alphabet,
we usually do not specify how to encode instances by binary strings.
This relies on the empirical observation that the truth of a statement of the form CIRCUIT-SAT belongs to a complexity class $C$''
more >>>

ISSN 1433-8092 | Imprint