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 Fall 2022, 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 pizza dinner at ITU. Pizzas will be provided, and there will be the possibility of buying your own drinks at ITU's Friday Bar (Scroll Bar).

This year, ARCO is co-located with Will Code for Drinks. If you would like to have some fun solving algorithmic problems in a friendly and social atmosphere, and also in return for free beverages, you are very welcome to join the event from 16:00 to 19:00.

Program

Talks

Ioana Bercea   -   Daisy Bloom Filters

We consider the problem of designing an approximate membership structure, i.e., filter, for the general case in which both the input and the query elements come from some (possibly distinct) distributions. We discuss the classic Bloom filter design and determine the optimal number of hash functions that an element must hash to in order to guarantee an average false positive probability at most F. We also show a matching lower bound.
This is joint work with Jakob Bæk Tejs Houen and Rasmus Pagh.

Karl A. F. Fehrs   -   The Complexity of Learning Approval-Based Multiwinner Voting Rules

We study the PAC learnability of multiwinner voting, focusing on the class of approval-based committee scoring (ABCS) rules. These are voting rules applied on profiles with approval ballots, where each voter approves some of the candidates. According to ABCS rules, each committee of k candidates collects from each voter a score, that depends on the size of the voter's ballot and on the size of its intersection with the committee. Then, committees of maximum score are the winning ones. Our goal is to learn a target rule (i.e., to learn the corresponding scoring function) using information about the winning committees of a small number of sampled profiles. Despite the existence of exponentially many outcomes compared to single-winner elections, we show that the sample complexity is still low: a polynomial number of samples carries enough information for learning the target rule with high confidence and accuracy. Unfortunately, even simple tasks that need to be solved for learning from these samples are intractable. We prove that deciding whether there exists some ABCS rule that makes a given committee winning in a given profile is a computationally hard problem. Our results extend to the class of sequential Thiele rules, which have received attention recently due to their simplicity.

Kevin Schewior   -   The Itinerant List Update Problem

We introduce the itinerant list update problem (ILU), which is a relaxation of the classic list update problem in which the pointer no longer has to return to a home location after each request. The motivation to introduce ILU arises from the fact that it naturally models the problem of track memory management in Domain Wall Memory. Both online and offline versions of ILU arise, depending on specifics of this application. First, we show that ILU is essentially equivalent to a dynamic variation of the classical minimum linear arrangement problem (MLA), which we call DMLA. Both ILU and DMLA are very natural, but do not appear to have been studied before. In this work, we focus on the offline ILU and DMLA problems. We then give an O(log^2 n)-approximation algorithm for these problems. While the approach is based on well-known divide-and-conquer approaches for the standard MLA problem, the dynamic nature of these problems introduces substantial new difficulties. We also show an Omega(log n) lower bound on the competitive ratio for any randomized online algorithm for ILU. This shows that online ILU is harder than online LU, for which O(1)-competitive algorithms, like Move-To-Front, are known.

Radu Curticapean   -   Determinants from homomorphisms

We give a new combinatorial explanation for well-known relations between determinants and traces of matrix powers. Such relations can be used to obtain polynomial-time and poly-logarithmic space algorithms for the determinant. Our new explanation avoids linear-algebraic arguments and instead exploits a classical connection between subgraph and homomorphism counts.

Rasmus Pagh   -   Improved Utility Analysis of Private CountSketch

Sketching is an important tool for dealing with high-dimensional vectors that are sparse (or well-approximated by a sparse vector), especially useful in distributed, parallel, and streaming settings. It is known that sketches can be made differentially private by adding noise according to the sensitivity of the sketch, and this has been used in private analytics and federated learning settings. The post-processing property of differential privacy implies that all estimates computed from the sketch can be released within the given privacy budget.

In this paper we consider the classical CountSketch, made differentially private with the Gaussian mechanism, and give an improved analysis of its estimation error. Perhaps surprisingly, the privacy-utility trade-off is essentially the best one could hope for, independent of the number of repetitions in CountSketch: The error is almost identical to the error from non-private CountSketch plus the noise needed to make the vector private in the original, high-dimensional domain.

Riko Jacob   -   Universal Sorting: Finding a DAG using Priced Comparisons

We resolve two open problems in sorting with priced information, introduced by [Charikar, Fagin, Guruswami, Kleinberg, Raghavan, Sahai (CFGKRS), STOC 2000]. In this setting, different comparisons have different (potentially infinite) costs. The goal is to find a sorting algorithm with small competitive ratio, defined as the ratio of its cost to the cost of the cheapest proof.

1) When all costs are in {0,1,n,\infty}, we give an algorithm that has Õ(n^{3/4}) competitive ratio. Our result refutes the hypothesis that a widely cited \Omega(n) lower bound for finding the maximum extends to sorting. This lower bound by [Gupta, Kumar, FOCS 2000] uses costs in {0,1,n, \infty} and was claimed as the reason why sorting with arbitrary costs seemed bleak and hopeless. Our algorithm generalizes the algorithms for generalized sorting (all costs are either 1 or \infty), a version initiated by [Huang, Kannan, Khanna, FOCS 2011] and addressed recently by [Kuszmaul, Narayanan, FOCS 2021].

2) We answer the problem of bichromatic sorting posed by [CFGKRS]: We are given two sets A and B of total size n, and the cost of an A-A comparison or a B-B comparison is higher than an A-B comparison. The goal is to sort A \cup B. We give a randomized algorithm with a O(polylog n) competitive ratio. Unlike most algorithms on generalized sorting that focus only on query complexity, the running time of our algorithm is at most O(n^2).

These results are obtained by introducing the universal sorting problem, which generalizes the existing framework in two important ways. First, we remove the promise of a directed Hamiltonian path in the DAG of all comparisons, which is assumed in all previous work on generalized sorting. Instead, we require that an algorithm outputs the transitive reduction of the DAG. For bichromatic sorting, when A-A and B-B comparisons cost \infty, this generalizes the well-known nuts and bolts problem. Second, we initiate an instance-based study of the universal sorting problem. Our definition of instance-optimality is inherently more algorithmic than that of the competitive ratio in that we compare the cost of a candidate algorithm to the cost of the optimal instance-aware algorithm. This unifies existing lower bounds, and opens up the possibility of an O(1)-instance optimal algorithm for the bichromatic version.

Valentin Polishchuk   -   Geometric secluded paths and planar satisfiability

We consider paths with low exposure to a 2D polygonal domain, i.e., paths which are seen as little as possible; we differentiate between integral exposure (when we care about how long the path sees every point of the domain) and 0/1 exposure (just counting whether a point is seen by the path or not). For the integral exposure, we give a PTAS for finding the minimum-exposure path between two given points in the domain; for the 0/1 version, we prove that in a simple polygon the shortest path has the minimum exposure, while in domains with holes the problem becomes NP-hard. We also highlight connections of the problem to minimum satisfiability and settle hardness of variants of planar min- and max-SAT.
Presented at The 36th International Symposium on Computational Geometry (SoCG 2020). Joint work with K. Buchin, L. Sedov, R. Voronov

Contact

Paloma Lima and Nutan Limaye
  {palt, nuli} [at] itu.dk

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