Complexity theory typically studies the complexity of computing a function $h(x) : \{0,1\}^n \to \{0,1\}^m$ of a given input $x$. We advocate the study of the complexity of generating the distribution $h(x)$ for uniform $x$, given random bits.

Our main results are:

\begin{itemize}
\item There are explicit $AC^0$ circuits of ... more >>>

We study the power of non-uniform attacks against one-way
functions and pseudorandom generators.

Fiat and Naor show that for every function
$f: [N]\to [N]$
there is an algorithm that inverts $f$ everywhere using
(ignoring lower order factors)
time, space and advice at most $N^{3/4}$.

We show that ... more >>>

Consider a communication network represented by a directed graph $G=(V,E)$ of $n$ nodes and $m$ edges. Assume that edges in $E$ are
partitioned into two sets: a set $C$ of edges with a fixed
non-negative real cost, and a set $P$ of edges whose \emph{price} should instead be set by ... more >>>