News

Aalto computer scientists in STOC 2024

Published: 20.6.2024

Two papers from the field of computer science were accepted to STOC 2024.

The 56th ACM Symposium on Theory of Computing (STOC 2024) is sponsored by the ACM Special Interest Group on Algorithms and Computation Theory and will be held on 24-28 June 2024 at the Sheraton Vancouver Wall Centre in Vancouver, British Columbia, Canada.

STOC 2024

Accepted papers

In alphabetical order. Click the title to see the authors and the abstract.

Authors

Andreas Björklund (IT University of Copenhagen); Petteri Kaski (Aalto University)

Abstract

Strassen's asymptotic rank conjecture [{\em Progr.~Math.}~120~(1994)] claims a strong submultiplicative upper bound on the rank of a three-tensor obtained as an iterated Kronecker product of a constant-size base tensor. The conjecture, if true, most notably would put square matrix multiplication in quadratic time. We note here that some more-or-less unexpected algorithmic results in the area of exponential-time algorithms would also follow. Specifically, we study the so-called set cover conjecture, which states that for any $\epsilon>0$ there exists a positive integer constant $k$ such that no algorithm solves the $k$-Set Cover problem in worst-case time $\bO((2-\epsilon)^n|\mathcal F|\operatorname{poly}(n))$. The $k$-Set Cover problem asks, given as input an $n$-element universe $U$, a family $\mathcal F$ of size-at-most-$k$ subsets of $U$, and a positive integer $t$, whether there is a subfamily of at most $t$ sets in $\mathcal F$ whose union is $U$. The conjecture was formulated by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh~in the monograph {\em Parameterized Algorithms} [Springer,~2015], but was implicit as a hypothesis already in Cygan, Dell, Lokshtanov, Marx, Nederlof, Okamoto, Paturi, Saurabh, and Wahlstr{\"{o}}m~[CCC~2012, {\em ACM~Trans.~Algorithms}~2016], there conjectured to follow from the Strong Exponential Time Hypothesis. We prove that if the asymptotic rank conjecture is true, then the set cover conjecture is false. Using a reduction by Krauthgamer and Trabelsi [STACS~2019], in this scenario we would also get an $\bO((2-\delta)^n)$-time randomized algorithm for some constant $\delta>0$ for another well-studied problem for which no such algorithm is known, namely that of deciding whether a given $n$-vertex directed graph has a Hamiltonian cycle.

Link to the paper

Authors

Xavier Coiteux-Roy, Francesco d'Amore, Rishikesh Gajjala, Fabian Kuhn, François Le Gall, Henrik Lievonen, Augusto Modanese, Marc-Olivier Renou, Gustav Schmid, Jukka Suomela

Abstract

We give an almost complete characterization of the hardness of c-coloring χ-chromatic graphs with distributed algorithms, for a wide range of models of distributed computing. In particular, we show that these problems do not admit any distributed quantum advantage. To do that: 1) We give a new distributed algorithm that finds a c-coloring in χ-chromatic graphs in ̃(n1α) rounds, with α=⌊c−1χ−1⌋. 2) We prove that any distributed algorithm for this problem requires Ω(n1α) rounds. Our upper bound holds in the classical, deterministic LOCAL model, while the near-matching lower bound holds in the non-signaling model. This model, introduced by Arfaoui and Fraigniaud in 2014, captures all models of distributed graph algorithms that obey physical causality; this includes not only classical deterministic LOCAL and randomized LOCAL but also quantum-LOCAL, even with a pre-shared quantum state. We also show that similar arguments can be used to prove that, e.g., 3-coloring 2-dimensional grids or c-coloring trees remain hard problems even for the non-signaling model, and in particular do not admit any quantum advantage. Our lower-bound arguments are purely graph-theoretic at heart; no background on quantum information theory is needed to establish the proofs.

Link to the paper

Jukka Suomela studies the limitations and efficiency of computation

Associate Professor Jukka Suomela is a theoretical computer scientist, who works with very hard mathematical problems to uncover the limits and possibilities that computers hold