Aalto computer scientists in 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.
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.
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.
Related news
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
Department of Computer Science
We are an internationally-oriented community and home to world-class research in modern computer science.
School of Science
Science for tomorrow’s technology, innovations and businesses
- Published:
- Updated:
Read more news
This is how smart textiles can look like: self-cleaning cotton or a colour-changing print
An article by YLE Svenska about 'Beyond e-Textiles' project and 'Interlaced' exhibition at the University of Turku
Ammonia – a new green energy solution? Research project receives €2.5 million in funding
Ammonia is a promising alternative fuel for the marine industry and for storing green hydrogen, but there are many question marks over its use.
A new project in Espoo aims to improve disparities in children's learning outcomes – with the goal of preventing social segregation
Supporting children's learning skills has a major impact on their further education and employment, among other things.