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.
   
   

Foundations of Cryptography

Dennis Hofheinz, Professor

Our goal is to provide practical cryptographic building blocks that come with rigorously proven security guarantees. These building blocks should be efficient enough for the use in large-scale modern information systems, and their security should be defined and formally analyzed in a mathematically rigorous manner. More specifically, we are particularly interested in the design and analysis of cryptographic building blocks in the public-key setting. This covers common primitives like public-key encryption and digital signatures, specifically in realistic modern scenarios (such as settings with a huge number of users). On the other hand, we work on new cryptographic building blocks such as indistinguishability obfuscation.
   

Computational Complexity, Optimization, and Estimation

David Steurer, 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.

Algorithms and Optimization

Rasmus Kyng, Assistant Professor

Our research is focused on answering foundational questions in fast algorithms, optimization, and fine-grained complexity theory. Modern algorithms often combine optimization and continuous methods with data structures and combinatorial techniques, and our research attempts to push the boundaries of this paradigm. We also connect theory to applied work by developing and implementing provably correct algorithms that perform well in practice.
   

Algorithms and Didactics

Dennis Komm, Associate Professor

Our group is particularly interested in questions that investigate the influence of additional information in various computational models, for example, when certain properties of a solution to be computed are known a priori.