Overview
The focus area on Foundations of Computing pursues fundamental research at the algorithmic and mathematical foundations of computing, integrating a broad range of expertise including multiple areas of algorithmics, artificial intelligence, computational complexity, cryptography, distributed computing, logic, and quantum computing.
Interested in joining us?
To participate in our activities, attend our open events described below. To get invited to email lists, chat channels, and so forth., please contact Petteri Kaski (Aalto University) or Mikko Koivisto (University of Helsinki). Our community is growing. See CS Theory at Aalto for a non-exhaustive list of researchers involved.
Activities
Helsinki CS Theory Seminar. A weekly series of talks on a broad scope of CS theory hosted by the Aalto University CS Theory Group. Link to seminar page.
Helsinki Logic Seminar. A weekly series of talks in mathematical logic hosted by the Helsinki Logic Group. Link to seminar page.
Foundations Friday. A monthly get-together event for the community typically consisting of a tutorial and lunch as well as follow-up activity and discussions. Link to activity page coming soon.
Research Highlights
The Shortest Even Cycle Problem is Tractable
A. Björklund, T. Husfeldt, P. Kaski.
Given a directed graph as input, we show how to efficiently find a shortest (directed, simple) cycle on an even number of vertices.
STOC’22 https://doi.org/10.1145/3519935.3520030
Deterministic (1+𝜀)-Approximate Maximum matching with poly(1/𝜀) Passes in the Semi-Streaming Model and Beyond 
M. Fischer, S. Mitrović, J. Uitto.
In the streaming setting, an input graph is given as a stream of edges and, at any time, the algorithm is allowed to keep a (roughly) linear amount of edges in memory. We give a streaming algorithm that makes a polynomial (in 𝜀) number of passes over the stream and finds an almost optimal matching.
STOC’22 https://doi.org/10.1145/3519935.3520039
Lower Bounds for Maximal Matchings and Maximal Independent Sets
A. Balliu, S. Brandt, J. Hirvonen, D. Olivetti, M. Rabie, J. Suomela.
There is a simple distributed algorithm for finding a maximal matching in a bipartite graph: nodes on one side send proposals one by one to their neighbors, and nodes on the other side accept the first proposal they get. In a graph of maximum degree Δ this takes O(Δ) rounds. We show that this is optimal: any distributed algorithm requires Ω(Δ) rounds in large networks.
J. ACM (2021) https://doi.org/10.1145/3461458
Approximating the Permanent with Deep Rejection Sampling
J. Harviainen, A. Röyskö, M. Koivisto.
Our deep rejection sampling method yields the fastest known practical approximation scheme for the permanent of nonnegative matrices. The key idea is to compute tighter upper bounds for the permanent by exact evaluation of the permanent of appropriate rectangular matrices.
NeurIPS’21 [link to online proceedings]