Algorithms on Graphs
Graphs form a mathematical model of a network of nodes joined by links. Methods to model and approximate large graphs find applications in analyzing complex networks such as Facebook and LinkedIn. Graph algorithms are used to solve problems where the input can be encoded by a graph, which include navigation, routing and scheduling problems.
Approximation and Online Algorithms
It is not always possible or practical to compute the best possible solution to an optimization problem because, initially, the input may not be fully known. Approximation and online algorithms deliver solutions that are guaranteed to have cost within a certain percentage of the optimum and they do so in a timely manner.
Automata Theory and Model Checking
Model checking is the dominating approach to deep bug discovery in critical systems. Based on automata theory, model checking is nowadays a key part of the development process at companies including Facebook, Intel and Microsoft.
Verification and Controller Synthesis
In our cutting-edge research on computer-aided verification, algorithm design meets game theory to produce optimal procedures and complexity bounds for analysing and synthesising massively concurrent systems that operate on very large data.