Department of Computer Science

Institute of Theoretical Computer Science

Mission statements of the groups

Informationsecurity and Cryptography

Ueli Maurer, Professor

Information is becoming a crucial if not the most important resource of the economy and the society at large. Information differs radically from other resources; for instance, it can be copied without cost, it can be communicated at the speed of light, and it can be destroyed without leaving traces. This poses new challenges for the protection of this new resource and of intellectual property in general. Information security, in particular cryptography, is an enabling technology that is vital for the development of the information society. Our missions are
  • to contribute to understanding the foundations of, and finding practical solutions for, known and emerging information security problems,
  • to foresee and identify future issues in information security,
  • to advance the theory of information security and cryptography as scientific disciplines,
  • to teach our core competences to university students as well as other academic and non-academic audiences,
  • to be a center of competence and a contact point for research institutions, the business sector, government administrations, the media, and the public at large, in all questions related to information security,
  • to think about the impact of information technology on the society and the economy,
  • and to enjoy the pleasure of research and teaching motivated students.


Combinatorial Structures and Algorithms

Angelika Steger, Professor

The main research interests of our group lie in the areas of combinatorial structures and algorithms, discrete mathematics, and combinatorial optimization. In particular we are interested in probabilistic methods, random graphs and algorithms, graph theory, and combinatorics. In addition to our theoretical work we select every few years a new "challenge" that allows us to demonstrate, use, and improve methods from modern theoretical computer science by working on a challenging "real world" application, see here for details.

Theory of Combinatorial Algorithms

Emo Welzl, Professor

Our goals are to provide good teaching for the students, a fruitful research environment for Ph.D. students and to achieve scientific findings (Erkenntnisgewinn) to be published in leading journals and conferences of theoretical computer science and discrete mathematics, the areas of our interest.

Algorithms, Data Structures, and Applications

Peter Widmayer, Professor

We feel that algorithms research benefits from a certain breadth of topics, and we have been aiming to cover that breadth in a particular way that we want to continue to explore. In terms of computer science methods, our interest ranges from hard combinatorial and geometric optimization problems across data structures for large data sets and complex operations to distributed data handling and processing. In terms of application scenarios, we plan to continue the study of transportation problems such as railway optimization and control; of mobile phone antenna optimization problems such as placement, frequency assignment, and adaptivity; of proteomics problems such as database search and data analysis problems; of web related problems such as fault tolerant data handling and processing in a large network. All of these problems will be studied under a variety of conditions and objectives. In terms of mode of operation, we feel that it is important to be part of a research effort already in the modelling phase, carry all the way through the abstraction and solution phase to the phase of implementing and experimenting with algorithms and data structures. We are aware of the danger inherent in such an approach: Too much breadth certainly comes with a lack of depth, and too little breadth leads to a lack of cross-fertilizing experience. Our goal is to balance both in a way that allows us to do fundamental research and application development at the same time, and not disregard the area in between.

Mohsen Ghaffari, Assistant Professor


Computational Complexity, Optimization, and Estimation

David Steurer, Assistant Professor

Our goal is to develop a better understanding of what kind of problems admit efficient algorithms and what problems are intractable. Toward this goal we investigate meta-algorithms that apply to a wide range of problems in a canonical way and achieve for many problems the best-known guarantees. One of the most promising examples of such a meta-algorithm is sum-of-squares. In recent years, we have used sum-of-squares to push the state-of-the-art for many optimization and estimation problems, e.g., small-set expansion, dictionary learning, (overlapping) community detection, tensor decomposition and completion. We also investigate the optimality of sum-of-squares with respect to restricted computational models, e.g., based on semidefinite-programming relaxations.