In this dissertation we investigate the complexity of the time-space trade-off
for sorting, element distinctness, and similar problems. We contribute new
results, techniques, tools, and definitions pertaining to time-space trade-offs
for the RAM (Random Access Machine), including new tight upper bounds
on the time-space trade-off for Sorting in a variety of RAM models and a
strong time-space trade-off lower bound for a decision problem in the RAM
(in fact the branching program) model. We thus contribute to the general
understanding of a number of fundamental combinatorial problems.
Time and space are the two most fundamental resources studied in the areas
of algorithms and computational complexity theory and it is clearly important
to study how they are related. In 1966 Cobham founded the area of
time-space trade-offs by formally proving the first time-space trade-off—for
the language of palindromes, i.e., a formulae that relate time and space in
the form of either an upper or a lower bound—in this case T · S 2  (n2).
Over the last thirty five years the area of time-space trade-offs has developed
significantly and now constitutes its own branch of algorithms and computational
complexity.
The area of time-space trade-offs deals with both upper and lower bounds
and both are interesting, theoretically as well as practically. The viewpoint
of this dissertation is theoretical, but we believe that some of our results can
find applications in practice as well.
The last four years has witnessed a number of significant breakthroughs on
proving lower bounds for decision problems, including the first non-trivial
lower bound on the unit-cost RAM.We generalize work of Ajtai and prove the
quantitatively best known lower bound in this model, namely a
(n lg n/ lg lg n)
bound on time for any RAM deciding the so-called Hamming distance problem
in space n1− .
For non-decision problems, i.e., problems with multiple outputs, much stronger
results are known. For Sorting, a fundamental problem in computer
science, Beame proved that for any RAM the time-space product satisfies
T · S 2
(n2). We prove that this bound is in fact tight (for most time
functions), i.e., we show a T · S 2 O(n2) upper bound for time between
O(n(lg lg n)2) and (roughly) O(n2). If we allow randomization in the Las
Vegas fashion the lower bound still holds, and in this case we can meet it
down to O(n lg lg n).

From a practical perspective hierarchical memory layout models are the most
interesting. Such models are called external memory models, in contrast to
the internal memory models discussed above. Despite the fact that space
might be of great relevance when solving practical problems on real computers,
no theoretical model capturing space (and time simultaneously) has
been defined. We introduce such a model and use it to prove so-called IOspace
trade-offs for Sorting. Building on the abovementioned techniques for
time-space efficient internal memory Sorting, we develop the first IO-space
efficient external memory Sorting algorithms. Further, we prove that these
algorithms are optimal using a transformation result which allows us to deduce
external memory lower bounds (on IO-space trade-offs) from already
known internal memory lower bounds (such as that of Beame)”.