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.
   
   

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.