  There are many ways of establishing upper bounds on fluctuations of random
variables, but there is no systematic approach for lower bounds. As a result,
lower bounds are unknown in many important problems. This paper introduces a
general method for lower bounds on fluctuations. The method is used to obtain
new results for the stochastic traveling salesman problem, the stochastic
minimal matching problem, the random assignment problem, the
Sherrington-Kirkpatrick model of spin glasses, first-passage percolation and
random matrices. A long list of open problems is provided at the end.
