Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ENTROPY FLATTENING:
Reports tagged with Entropy Flattening:
TR18-119 | 21st June 2018
YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang

#### A Tight Lower Bound for Entropy Flattening

Revisions: 1

We study \emph{entropy flattening}: Given a circuit $\mathcal{C}_X$ implicitly describing an $n$-bit source $X$ (namely, $X$ is the output of $\mathcal{C}_X$ on a uniform random input), construct another circuit $\mathcal{C}_Y$ describing a source $Y$ such that (1) source $Y$ is nearly \emph{flat} (uniform on its support), and (2) the Shannon ... more >>>

ISSN 1433-8092 | Imprint