Kfir Barhum, Thomas Holenstein

We present a new framework for proving fully black-box

separations and lower bounds. We prove a general theorem that facilitates

the proofs of fully black-box lower bounds from a one-way function (OWF).

Loosely speaking, our theorem says that in order to prove that a fully black-box

construction does ...
more >>>

YiHsiu Chen, Mika G\"o{\"o}s, Salil Vadhan, Jiapeng Zhang

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 >>>