  Exponentiation makes the difference between the bit-size of this line and the
number (<< 2^{300}) of particles in the known Universe. The expulsion of
exponential time algorithms from Computer Theory in the 60's broke its
umbilical cord from Mathematical Logic. It created a deep gap between
deterministic computation and -- formerly its unremarkable tools -- randomness
and non-determinism. Little did we learn in the past decades about the power of
either of these two basic "freedoms" of computation, but some vague pattern is
emerging in relationships between them. The pattern of similar techniques
instrumental for quite different results in this area seems even more
interesting. Ideas like multilinear and low-degree multivariate polynomials,
Fourier transformation over low-periodic groups seem very illuminating. The
talk surveyed some recent results. One of them, given in a stronger form than
previously published, is described below.
