Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > KL DIVERGENCE:
Reports tagged with KL divergence:
TR11-141 | 2nd November 2011

#### Characterizing Pseudoentropy and Simplifying Pseudorandom Generator Constructions

Revisions: 3

We provide a characterization of pseudoentropy in terms of hardness of sampling: Let $(X,B)$ be jointly distributed random variables such that $B$ takes values in a polynomial-sized set. We show that $B$ is computationally indistinguishable from a random variable of higher Shannon entropy given $X$ if and only if there ... more >>>

TR19-059 | 18th April 2019
Rohit Agrawal

#### Samplers and extractors for unbounded functions

Revisions: 1

Blasiok (SODA'18) recently introduced the notion of a subgaussian sampler, defined as an averaging sampler for approximating the mean of functions $f:\{0,1\}^m \to \mathbb{R}$ such that $f(U_m)$ has subgaussian tails, and asked for explicit constructions. In this work, we give the first explicit constructions of subgaussian samplers (and in fact ... more >>>

ISSN 1433-8092 | Imprint