Oded Goldreich

Some Useful Trivial Tricks

under construction...

Following are some useful trivialities regarding randomness and computations. Although trivial, these tricks are often useful in avoiding irrelevant technicalities.

Statistical Distance

The statistical distance between two random variables $X$ and $Y$, denoted $DELTA(X,Y)$, can be defined in two equivalent ways: (1) half of the sum of the absolute value of the pointwise distances, and (2) the maximum discrepency between the probability of some event. That is,
      &=& \frac12\cdot\sum_v\vert{\sf Pr}[X=v]-{\sf Pr}[Y=v]\vert \\
      &=& \max_{S}\{{\sf Pr}[X\in S]-{\sf Pr}[Y\in S]\} \end{eqnarray*}

In some situations one of these definitions is more convenient to work with than the other. The following trivial facts are useful.

Defining security

In many definitions the adversary is given the security paramter in unary, in order to allow it to run in time polynomial in that parameter. An alternative convention postulates that the objects considered with security paramter $n$ have length that is polynomially related to $n$ (and that $n$ can be efficiently reconstructed from their length). Tyically, this convention may be enforced by replacing the object $x$ by the augmented object $x'=(1^n,x)$.

Computational Indistinguishability


Probablistic Proof Systems

Back to Oded Goldreich's homepage.