This area forms the mathematical core of computer science. The basic goal is to deepen our theoretical understanding of computing. On one hand, we aim to design new and improved algorithms for a given problem and analyse their performance mathematically. On the other hand, we aim to prove that no algorithm for the considered problem can achieve a given performance.
Area leaders:
Theory and Algorithms - IDSIA NEW
Scientific area
SUPSI Image Focus
-
Approximation algorithms
-
Formal language and automata theory
-
Combinatorial optimization and diescrete mathematics
-
Formal verification
-
Computability and computational complexity theory
-
Numerical algorithms
-
Computational geometry
-
Parallel and distributed algorithms
-
Data Structures
-
Foundations of probability
-
Dynamic and online algorithms
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
- 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), https://doi.org/10.1109/FOCS.2012.17
- 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), https://doi.org/10.1137/100802888
- 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.