ARCO (Algorithmic Research Cooperation around Øresund) is a network for promoting collaboration in research within algorithms around the Øresund Region. The idea is to meet twice per year for a one-day workshop.

In Spring 2025, we meet at the IT University of Copenhagen.

The program consists of contributed talks and longer breaks for networking and catching up on recent news. We end the day with an informal (self-paid) pizza dinner at ITU. There will be the possibility of buying your own drinks at ITU's Friday Bar (Scroll Bar).

Program

Talks

Lukas Retschmeier (KU)   -   Optimal Bounds for Private Minimum Spanning Trees via Input Perturbation

Abstract: We study the problem of privately releasing an approximate minimum spanning tree (MST). Given a graph G = (V, E, \vec{W}) where V is a set of n vertices, E is a set of m undirected edges, and \vec{W} \in \mathbb{R}^{|E|} is an edge-weight vector, our goal is to publish an approximate MST under edge-weight differential privacy, as introduced by Sealfon in PODS 2016, where V and E are considered public and the weight vector is private. Our neighboring relation is \ell_\infty-distance on weights: for a sensitivity parameter \Delta_\infty, graphs G = (V, E, \vec{W}) and G' = (V, E, \vec{W}') are neighboring if \|\vec{W}-\vec{W}'\|_\infty \leq \Delta_\infty. Existing private MST algorithms face a trade-off, sacrificing either computational efficiency or accuracy. We show that it is possible to get the best of both worlds: With a suitable random perturbation of the input that does not suffice to make the weight vector private, the result of any non-private MST algorithm will be private and achieves a state-of-the-art error guarantee. Furthermore, by establishing a connection to Private Top-k Selection [Steinke and Ullman, FOCS '17], we give the first privacy-utility trade-off lower bound for MST under approximate differential privacy, demonstrating that the error magnitude, \tilde{O}(n^{3/2}), is optimal up to logarithmic factors. That is, our approach matches the time complexity of any non-private MST algorithm and at the same time achieves optimal error. We complement our theoretical treatment with experiments that confirm the practicality of our approach.
Joint work with Rasmus Pagh, Hao Wu, Hanwen Zhang.

Sarita de Berg (ITU)   -   Clustering with Few Disks to Minimize the Sum of Radii

Abstract: Given a set of n points in the Euclidean plane, the k-MinSumRadius problem asks to cover this point set using k disks with the objective of minimizing the sum of the radii of the disks. After a long line of research on related problems, it was finally discovered that this problem admits a polynomial time algorithm; however, the running time of this algorithm is O(n^{881}), and its relevance is thereby mostly of theoretical nature. A practically and structurally interesting special case of the k-MinSumRadius problem is that of small k. For the 2-MinSumRadius problem, a near-quadratic time algorithm with expected running time O(n^2 \log^2 n \log^2 \log n)$ was given over 30 years ago. We present the first improvement of this result, namely, a near-linear time algorithm to compute the 2-MinSumRadius that runs in expected O(n \log^2 n \log^2 \log n) time. We generalise this result to any constant dimension. Additionally, we give a near-quadratic time algorithm for 3-MinSumRadius in the plane. All of these algorithms rely on insights that uncover a surprisingly simple structure of optimal solutions: we can specify a linear number of lines out of which one separates one of the clusters from the remaining ones in an optimal solution.

Faith Ellen (SDU)   -   Distributed Graph Algorithms with Predictions

Abstract: We initiate the study of distributed graph algorithms with predictions in synchronous message passing systems. Each node in the graph is given a prediction, which is some extra information about the problem instance that may be incorrect.The better the prediction, the fewer rounds the algorithm should perform. We present a framework for evaluating distributed graph algorithms with predictions and some methods for transforming existing algorithms without predictionsto effectively use predictions. Our approach is illustrated using the Maximal Independent Set problem.
This is joint work with Joan Boyar and Kim Skak Larsen

Arthur da Cunha (Aarhus)   -   Optimal Parallelization of Boosting

Abstract: We begin with a review of the classic learning theory technique known as Boosting, which transforms weak learners—those performing just slightly better than random guessing—into highly accurate ones. We then explore approaches to accelerate this process through parallelization.

Ioana Bercea (KTH)   -   Locally Uniform Hashing

Abstract: Hashing is a commonly used technique for getting improved algorithms. Most analyses, however, assume access to fully-random hash functions, which is unrealistic in terms of the resources available to the algorithm. A fundamental line of work has thus been to design realistic hash functions (with small space and fast evaluation time) that make the algorithm perform almost as if it used fully-random hash functions. In this talk, we will review one such hash function, called a tornado tabulation hash function, that provides state-of-the-art randomness guarantees for several fundamental algorithms. In particular, we will define and discuss one key property that it exhibits, that of local uniformity, only used technique for getting improved algorithms. Most analyses, however, assume access to fully-random hash functions, which is unrealistic in terms of the resources available to the algorithm. A fundamental line of work has thus been to design realistic hash functions (with small space and fast evaluation time) that make the algorithm perform almost as if it used fully-random hash functions. In this talk, we will review one such hash function, called a tornado tabulation hash function, that provides state-of-the-art randomness guarantees for several fundamental algorithms. In particular, we will define and discuss one key property that it exhibits, that of local uniformity.

Magnus Merrild (Aarhus)   -   The Contiguous Art Gallery Problem is Polynomial Time Solvable

Abstract: In the field of Visibility problems, the Art Gallery Problem is one of, if not the most famous problem. The problem is to find the minimum number of guards that can see all points in a polygon. The guards can be placed anywhere in the polygon, and they can see all points in their visibility polygon. The problem is $\exists \R$-complete, and most natural variants area also $NP$-hard. We study a variant of the Art Gallery Problem, called the Contiguous Art Gallery Problem, where the goal is to guard the boundary of the polygon and guards can only see one contiguous part of the boundary of the polygon. We show that this problem can be solved in polynomial time using a greedy algorithm.

Tim Seppelt (ITU)   -   Symmetric Algebraic Circuits and Homomorphism Polynomials

Abstract: The central open question of algebraic complexity is whether VP is unequal to VNP, which is saying that the permanent cannot be represented by families of polynomial-size algebraic circuits. For symmetric algebraic circuits, this has been confirmed by Dawar and Wilsenach (2020) who showed exponential lower bounds on the size of symmetric circuits for the permanent. In this work, we set out to develop a more general symmetric algebraic complexity theory. Our main result is that a family of symmetric polynomials admits small symmetric circuits if and only if they can be written as a linear combination of homomorphism counting polynomials of graphs of bounded treewidth. We also establish a relationship between the symmetric complexity of subgraph counting polynomials and the vertex cover number of the pattern graph. This is joint work with Anuj Dawar and Benedikt Pago.

Jonas Klausen (KU)   -   Online Sorting and Online TSP: Randomized, Stochastic, and High-Dimensional

Abstract: In the online sorting problem, n items are revealed one by one and have to be placed (immediately and irrevocably) into empty cells of a size-n array. The goal is to minimize the sum of absolute differences between items in consecutive cells. This natural problem was recently introduced by Aamand, Abrahamsen, Beretta, and Kleist (SODA 2023) as a tool in their study of online geometric packing problems. They showed that when the items are reals from the interval [0,1] a competitive ratio of O(√n) is achievable, and no deterministic algorithm can improve this ratio asymptotically.
In this presentation, we extend and generalize the study of online sorting in three directions:
- randomized: we settle the open question of Aamand et al. by showing that the O(√n) competitive ratio for the online sorting of reals cannot be improved even with the use of randomness;
- stochastic: we consider inputs consisting of n samples drawn uniformly at random from an interval, and give an algorithm with an improved competitive ratio of Õ(n^{1/4}). The result reveals connections between online sorting and the design of efficient hash tables;
- high-dimensional: we show that Õ(√n)-competitive online sorting is possible even for items from ℝ^d, for arbitrary fixed d, in an adversarial model. This can be viewed as an online variant of the classical TSP problem where tasks (cities to visit) are revealed one by one and the salesperson assigns each task (immediately and irrevocably) to its timeslot. Along the way, we also show a tight O(log n)-competitiveness result for uniform metrics, i.e., where items are of different types and the goal is to order them so as to minimize the number of switches between consecutive items of different types.
This presentation is based on a paper presented at ESA'24 which is available at https://doi.org/10.4230/LIPIcs.ESA.2024.5.

Contact

Holger Dell, Paloma Lima and Eva Rotenberg
  {hold, palt, erot} [at] itu.dk

IT University of Copenhagen
Rued Langgaards Vej 7
DK-2300 København S, Denmark