27th ARCO 2022 at Malmö University

If you intend to participate, please send send a mail to bengt.nilsson.TS@mau.se. Registration for lunch/coffee/dinner may be refused at this time, but participation in presentations is still open.

Programme

Abstracts

Title: HyperLogLogLog: Cardinality Estimation With One Log More
We present HyperLogLogLog, a practical compression of the HyperLogLog sketch that compresses the sketch from $O(m\log\log n)$ bits down to $m \log_2\log_2\log_2 m + O(m)$ bits for estimating the number of distinct elements $n$ using $m$ registers. The algorithm works as a drop-in replacement that preserves all estimation properties of the HyperLogLog sketch, it is possible to convert back and forth between the compressed and uncompressed representations, and the compressed sketch maintains mergeability in the compressed domain. The compressed sketch can be updated in amortized constant time, assuming $n$ is sufficiently larger than $m$. We provide a C++ implementation of the sketch, and show by experimental evaluation against well-known implementations by Google and Apache that our implementation provides small sketches while maintaining competitive update and merge times. Concretely, we observed approximately a 40\% reduction in the sketch size. Furthermore, we obtain as a corollary a theoretical algorithm that compresses the sketch down to $m\log_2\log_2\log_2\log_2 m+O(m\log\log\log m/\log\log m)$ bits. This is joint work with Rasmus Pagh.

Title: Predecessor on the Ultra-Wide Word RAM
We consider the predecessor problem on the ultra-wide word RAM model of computation, which extends the word RAM model with ultrawords consisting of w^2 bits [TAMC, 2015]. The model supports arithmetic and boolean operations on ultrawords, in addition to scattered memory operations that access or modify w (potentially non-contiguous) memory addresses simultaneously. The ultra-wide word RAM model captures (and idealizes) modern vector processor architectures.
Our main result is a simple, linear space data structure that supports predecessor in constant time and updates in amortized, expected constant time. This improves the space of the previous constant time solution that uses space in the order of the size of the universe. Our result is based on a new implementation of the classic x-fast trie data structure of Willard [Inform. Process. Lett. 17(2), 1983] combined with a new dictionary data structure that supports fast parallel lookups.

Title: 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.

Title: Local Search, More Powerful Than You Thought
Local search is underutilized in algorithms research. Although it is a nice tool, it usually does not provide any concrete bounds on the solution. It is often thought of as a heuristic that will run quickly and will probably be close to the exact solution. This talk will give an overview of how local search can be used to obtain solutions that are guaranteed to be a close approximation of the exact solution. We will see a few examples of how the simple algorithm works.

Title: On the Complexity of List Ranking in the Parallel External Memory Model
We study the problem of list ranking in the parallel external memory (PEM) model. We observe an interesting dual nature for the hardness of the problem due to limited information exchange among the processors about the structure of the list, on the one hand, and its close relationship to the problem of permuting data, which is known to be hard for the external memory models, on the other hand. By carefully defining the power of the computational model, we prove a permuting lower bound in the PEM model. Furthermore, we present a stronger Ω((log N)^2) lower bound for a special variant of the problem and for a specific range of the model parameters, which takes us a step closer toward proving a non-trivial lower bound for the list ranking problem in the bulk-synchronous parallel (BSP) and MapReduce models. Finally, we also present an algorithm that is tight for a larger range of parameters of the model than in prior work.

Title: The Minimum Circuit Size Problem is hard for Sum of Squares
The minimum circuit size problem (MCSP), asking for the minimum size of a circuit computing a given truth-table, is a well-known and long studied problem in computational complexity. But despite decades of research it is still unknown whether MCSP is NP-hard. To make matter even worse, just establishing this is hard: Kabanetes and Cai showed that establishing NP-hardness of MCSP implies breakthrough circuit lower bounds. As such it is an important goal to at least show that certain algorithm classes cannot solve MCSP efficiently. We unconditionally establish that the MCSP problem, asking whether a truth-table has a circuit of size $s$, cannot be decided by any algorithm captured by the SoS framework of degree at most $O(s^{1-\epsilon})$. This is joint work with Per Austrin.

Title: Maintaining smaller out-orientations
The arboricity α of a graph is the minimum number of forests needed to cover the edges of the graph. The dynamic out-orientation problem is to orient the edges of a graph such that at all times the maximum out-degree is low. A well-known result of Brodal & Fagerberg is that one can maintain an orientation with maximum out-degree approximately 2α with an amortised update time of O(α+log(n)). They also show a lower bound: any algorithm maintaining an explicit orientation with at most α out-edges requires linear update time. We present the first dynamic algorithm to go below 2α out-edges while keeping the update time in O(poly( log(n), α )). More specifically, we present a fully dynamic algorithm for maintaining a ⌊(1+ ε)α⌋+2 out-orientation with a worst-case update time of O(α^2 log^3(n) ε^-6).

15:05–15:30 Thore Husfeldt: Extensor-Coding 15:30–16:00 Coffee break 16:00–16:20 Andreas Björklund: Counting Shortest Two Disjoint Paths in Cubic Planar Graphs with an NC Algorithm 16:20–16:50 Radu Curticapean: The complexity of graph motif parameters 16:50–20:00 (ca.) Hang-out and dinner