Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with KL divergence:
TR11-141 | 2nd November 2011
Salil Vadhan, Colin Jia Zheng

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