Tag Info

New answers tagged


The $X_i$ could be distributed differently, but does not have to be. The idea of an ensemble is just that the distributions are related somehow. A way to think of this is that, $X_i$ could be the distribution of the output from some randomized algorithm given input $i$. Consider, for example, the algorithm that on input $i$ outputs a uniformly random ...


No, $X = \{X_n\}_{n \in \mathbf{N}}$ means $X = X_1, X_2, \ldots$ where each $X_i$ is a distribution. So one could let each $X_i$ be the uniform distribution on strings of length $i$. That means there is a polynomial $q$ such that for all $n$ and $x$, if $X_n$ assigns non-zero probability to $x$ then the length of $x$ is at most $q(i\hspace{.02 in})$. ...

Top 50 recent answers are included