Aalto computer scientists in SODA2025 and SOSA2025

News

Aalto computer scientists in SODA2025 and SOSA2025

Published: 7.1.2025

Department of Computer Science papers accepted to the ACM-SIAM Symposium on Discrete Algorithms (SODA2025) and SIAM Symposium on Simplicity in Algorithms (SOSA25).

Algorithms and theoretical computer science, illustration Matti Ahlgren/Aalto University

The SODA 2025 symposium focuses on research topics related to the design and analysis of efficient algorithms and data structures for discrete problems. The scope includes theoretical analysis, as well as experimental validation, of discrete algorithms, and the mathematical problems related to their development or limitations.

Symposium on Simplicity in Algorithms (SOSA) is a conference in theoretical computer science dedicated to advancing algorithms research by promoting simplicity and elegance in the design and analysis of algorithms.

These co-located symposiums are organised on 12-15 January 2025 in New Orleans, LA, USA.

Accepted papers

Click the title to see the authors and the abstract. Link to the paper open on different website.

Authors

Andreas Björklund, Radu Curticapean, Thore Husfeldt, Petteri Kaski, and Kevin Pratt

Abstract

In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Progr. Math. 1994] and the three-way partitioning problem. We show that under the asymptotic rank conjecture, the chromatic number of an n-vertex graph can be computed deterministically in O(1.99982^n) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the 2^n poly(n) time algorithm for chromatic number by Björklund, Husfeldt, and Koivisto [SICOMP 2009]. Viewed in the other direction, if chromatic number indeed requires deterministic algorithms to run in close to 2^n time, we obtain a sequence of explicit tensors of superlinear rank, falsifying the asymptotic rank conjecture. Our technique is a combination of earlier algorithms for detecting k-colorings for small k and enumerating k-colorable subgraphs, with an extension and derandomisation of Pratt's tensor-based algorithm for balanced three-way partitioning to the unbalanced case.

Authors

Sebastian Brandt, Yannic Maus, Ananth Narayanan, Florian Schager, and Jara Uitto

Abstract

The last five years of research on distributed graph algorithms have seen huge leaps of progress, both regarding algorithmic improvements and impossibility results: new strong lower bounds have emerged for many central problems and exponential improvements over the state of the art have been achieved for the runtimes of many algorithms. Nevertheless, there are still large gaps between the best known upper and lower bounds for many important problems. The current lower bound techniques for deterministic algorithms are often tailored to obtaining a logarithmic bound and essentially cannot be used to prove lower bounds beyond Ω(log n). In contrast, the best deterministic upper bounds, usually obtained via network decomposition or rounding approaches, are often polylogarithmic, raising the fundamental question of how to resolve the gap between logarithmic lower and polylogarithmic upper bounds and finally obtain tight bounds. We develop a novel algorithm design technique aimed at closing this gap. It ensures a logarithmic runtime by carefully combining local solutions into a globally feasible solution. In essence, each node finds a carefully chosen local solution in O(log n) rounds and we guarantee that this solution is consistent with the other nodes’ solutions without coordination. The local solutions are based on a distributed version of Hall’s theorem that may be of independent interest and motivates the title of this work. We showcase our framework by improving on the state of the art for the following fundamental problems: edge coloring, bipartite saturating matchings and hypergraph sinkless orientation. For each of the problems we improve the runtime for general graphs and provide asymptotically optimal algorithms

Authors

Petteri Kaski , Heikki Mannila, and Antonis Matakos

Abstract:

The Johnson–Lindenstrauss family of transforms constitutes a key algorithmic tool for reducing the dimensionality of a Euclidean space with low distortion of distances. Rephrased from geometry to linear algebra, one seeks to reduce the dimension of a vector space while approximately preserving inner products. We present a multilinear generalization of this bilinear (inner product) setting that admits both an elementary randomized algorithm as well as a short proof of correctness using Orlicz quasinorms.

Authors

Nick Fischer, Bernhard Haeupler, Rustam Latypov, Antti Roeyskoe, and Aurelio L. Sulser

Abstract

We give the first parallel algorithm with optimal O(m polylog m) work for the classical problem of computing Single-Source Shortest Paths in general graphs with negative-weight edges. In graphs without negative edges, Dijkstra's algorithm solves the Single-Source Shortest Paths (SSSP) problem with optimal O(m polylog m) work, but is inherently sequential. A recent breakthrough by Bernstein, Nanongkai, Wulff-Nilsen; FOCS '22 achieves the same for general graphs. Parallel shortest path algorithms are more difficult and have been intensely studied for decades. Only very recently, multiple lines of research culminated in parallel algorithms with optimal work O(m polylog m) for various restricted settings, such as approximate or exact algorithms for directed or undirected graphs without negative edges. For general graphs, the best known algorithm by [shvinkumar, Bernstein, Cao, Grunau, Haeupler, Jiang, Nanongkai, Su; ESA '24 still requires m^(1+o(1)) work. This paper presents a randomized parallel algorithm for SSSP in general graphs with near-linear work O(m polylog m) and state-of-the-art span n^(1/2+o(1)). We follow a novel bottom-up approach leading to a particularly clean and simple algorithm. Our algorithm can be seen as a near-optimal parallel black-box reduction from SSSP in general graphs to graphs without negative edges. In contrast to prior works, the reduction in this paper is both parallel and essentially without overhead, only affecting work and span by polylogarithmic factors.