Theory and Algorithms
This area forms the mathematical core of computer science. The basic goal here is to deepen our theoretical understanding of computing. On one hand, we wish to design new and improved algorithms for a given problem and analyse their performance mathematically. On the hand, we wish to prove that no algorithm for the considered problem can achieve a given performance.

We cover several research sub-areas, including:

  • approximation algorithms
  • combinatorial optimization and discrete mathematics
  • computability and computational complexity theory
  • computational geometry
  • data structures
  • dynamic and online algorithms
  • formal language and automata theory
  • formal verification
  • numerical algorithms
  • parallel and distributed algorithms
  • foundations of probability

We apply our theoretical insights to a variety of applications, among which:

  • computer graphics and computer-aided geometric design
  • model checking
  • graph and network problems
  • program analysis
  • scheduling
  • security
  • VLSI computer-aided design

We plan to refine our expertise in the above-mentioned research areas and applications, and to explore related areas and new applications. We wish to train a new generation of leading researchers in algorithms and theory.

Some references

  • F. Grandoni and V. V. Williams, Improved Distance Sensitivity Oracles via Fast Single-Source Replacement Paths, 53rd Annual {IEEE} Symposium on Foundations of Computer Science, {FOCS} 2012, New Brunswick, NJ, USA, October 20-23, 2012, 748--757 (2012),
  • F. Grandoni, A. Gupta, S. Leonardi, P. Miettinen, P. Sankowski, and M. Singh, Set Covering with Our Eyes Closed, SIAM J. Comput. 42 808--830 (2013),
  • K. Hormann, L. Kania, and C. Yap. Novel range functions via Taylor expansions and recursive Lagrange interpolation with application to real root isolation. In Proceedings of the 2021 ACM International Symposium on Symbolic and Algebraic Computation, pages 193-200, Saint Petersburg, Russia, July 2021. ACM.