This volume highlights some of the key issues of theoretical computer science as they seem at the beginning of the new millennium. The text is based on columns and tutorials published in the "Bulletin of the European Association for Theoretical Computer Science" in the period 1995-2000.