Department of Computer Science
Informationsecurity and
Cryptography
|
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
|
Combinatorial Structures and Algorithms |
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. |
Foundations of Cryptography |
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 |
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 |
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 |
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. |
Combinatorial Optimization |
The main focus of our research is on combinatorial optimization, with a particular emphasis on developing approximation algorithms for core problems within this field. Concrete examples of such problems include the Traveling Salesman Problem, Steiner Tree, and Connectivity Augmentation. |