“Helsinki Algorithms and Theory Days” took place in the University of Helsinki central campus on the 29th and 30th of August. The 56 participants enjoyed two days of talks covering various topics in the area of theoretical computer science. The event featured three invited talks, one by Prof. Andreas Björklund (IT-University of Copenhagen), one by Prof. Mika Göös (EPFL), and yet another one by Dr. Tuukka Korhonen (University of Bergen / University of Copenhagen), as well as 11 other talks contributed by the local community.

The first day wrapped up with a social dinner that brought the community together and offered additional opportunities for sharing research interests. At the end of the second day, one session was dedicated to open problems. Participants had the opportunity to ask for the floor and introduce the audience to an open research question of their choice. A guided tour of Suomenlinna concluded the second day and the entire event.

The organizers thank HIIT for sponsoring the event as well as Aalto University for additional financial support.

Andreas Björklund: Finding long cycles in graphs.

A “long cycle” is a parametrization of the well known Hamiltonian cycle. More specifically, the k,e-Long Cycle problem is the problem of detecting a cycle of length at least k that passes through edge e. This talk went through various results about this problem, showing for example that, despite the problem requiring exponential time, a colouring of vertices can help achieve faster algorithms.

Tuukka Korhonen: Minor Containment and Disjoint Paths in almost-linear time.

The talk gave an overview of the problem of determining whether a graph is the minor of another. Various techniques were presented such as the irrelevant vertex techniques. It was shown how these can be combined with recent findings in graph theory and some reductions to obtain improved algorithms for the problem of Rooted Minor Containment.

Mika Göös: Constant-Cost Communication.

Problems requiring a linear amount of bits to be solved deterministically may require only a constant amount of communication to be solved randomly. Which problems are solvable in randomized constant cost-communication? This talk described a few inhabitants of this landscape such as the equality problem and a hierarchy of problems based on Hamming distance.

Sándor Kisfaludi-Bak: The impact of curvature on geometric (intersection) graphs.

Juha Harviainen: On Sampling and Counting Directed Acyclic Graphs.

Corinna Coupette: Model-Agnostic Approximation of Constrained Forest Problems

Andreas Grigorjew: Flow decompositions and directed graph minors

Pekka Orponen: Applications of graph theory in RNA nanostructure design

Jukka Suomela: Limits of distributed computing

Juho Hirvonen: Fast and Distributed Mechanisms

Jeremias Berg: Certified Automated Reasoning

Petteri Kaski: A multilinear Johnson–Lindenstrauss transform

Arshpreet Maan: What algorithms should be studied with 100 qubits and 1M logical gates?

Russell W. F. Lai: On the Expanding Zoo of Lattice Assumptions