We use cookies on this website. Cookies help us deliver the best experience on our website. Read about cookies.

 Education
 Education
 Programmes and courses
 Applications and admissions
 Tuition fees
 Scholarships
 Exchange studies at Malmö University
 Study Guidance

 After admission
 After admission
 Moving to Malmö
 Preorientation
 Arrival guide

 About studies at Malmö University
 About studies at Malmö University
 Why choose Malmö University
 Understanding university studies
 Connect with current students
On the page 
 Research
 Research

 Doctoral studies
 Doctoral studies
 Doctoral courses

 Doctoral schools
 Doctoral schools
 Education, Learning and Globalisation
 Doctoral school: Learning in Multicultural Societal Contexts
 ComBine
 Swedish National Graduate School in Science and Technology Education Research
 Doctoral school: Relevancing Mathematics and Science Education (RelMaS)
 Doctoral school: Sustainable Movement Education
 Finding ways in a time of great future challenges (FinnFram)
 Doctoral school: Pedagogy and Vocational Skills
 Doctoral school: Culturally Empowering Education through Language and Literature
 Research subjects

 Prominent research
 Prominent research

 Research publications
 Research publications
 Search publications
 Malmö University Press
 Research events
 Participate in a research study
On the page 
 Collaboration and Innovation
 Collaboration and Innovation
 Areas of collaboration
 Innovation
 Collaboration with students

 Collaborate with researchers
 Collaborate with researchers
 Labs and facilities
 Culture collaboration
 Support Malmö University
On the page 
 About us
 About us

 Faculties and departments
 Faculties and departments

 Faculty of Culture and Society
 Faculty of Culture and Society
 Department of Urban Studies
 Department of Global Political Studies
 School of Arts and Communication

 Faculty of Education and Society
 Faculty of Education and Society
 Department of Childhood, Education and Society
 Department of Sports Sciences
 Department of Natural Science, Mathematics and Society
 Department of School Development and Leadership
 Department of Culture, Languages and Media
 Department of Society, Culture and Identity

 Faculty of Technology and Society
 Faculty of Technology and Society
 Department of Computer Science and Media Technology
 Department of Materials Science and Applied Mathematics
 Faculty of Odontology
 University Dental Clinic

 Find and contact Malmö University
 Find and contact Malmö University
 Visit Malmö University
 News and press
 Map of the buildings (Google Maps)
 Merchandise
 Whistleblowing
 Management and decisionmaking paths

 Vision, objectives and strategy 2025
 Vision, objectives and strategy 2025
 Global engagement
 Sustainability
 Widened recruitment and participation
 Quality assurance work at the University

 Malmö Academic Choir and Orchestra
 Malmö Academic Choir and Orchestra
 Student work – video pieces
 Alumni & Friends

 Annual Academic Celebration
 Annual Academic Celebration
 Academic traditions
 Meet our new professors
 The University in a troubled world
On the page
ARCO
around Oresund (ARCO)
Algorithmic Research Cooperation, ARCO, is a collaboration between computer science departments at universities in the Öresund region.
ARCO was established in 2011 with the mission to foster collaboration, innovation, to facilitate knowledge exchange, and research partnerships in the area of algorithmic research around the Öresund region.
Workshops
ARCO organises workshops every autumn and spring to give researchers and, above all, doctoral students the opportunity to disseminate their research results within the network.
Next ARCO workshop
Welcome to the 32nd ARCO workshop on 22 November in Malmö.
The event will take place in Auditorium AS:306, "Allmänna sjukhuset", Jan Waldenströms gata 25, 214 28 Malmö.
To get there, get off the commuter train at station "Triangeln", the second stop on the Swedish side if you come from Denmark. Then walk south for about 10 minutes until you reach Jan Waldenströms gata 25.
Programme
09.00  10.00 Coffee and mingle
Chair: Thore Husfeldt
10.00  10.20 LinearTime Algorithms for kEdgeConnected Components, kLean Tree Decompositions, and More, Tuukka Korhonen
10.20  10.40 Revisiting Local Computation of PageRank: Simple and Optimal, Hanzhi Wang
10.4011.00 Monotone BoundedDepth Complexity of Homomorphism Polynomials, Prateek Dwivedi
11.0011.10 Paus
Chair: Valentin Polishchuk
11.1011.30 Hitting all longest paths in Hfree graphs, Amir Nikabadi
11.3011.50 Local Correction of Low Degree Polynomials, Amik Raj Behera
11.5012.10 An Optimal Randomized Algorithm for Finding the Saddlepoint, Frederik Haagensen
12.1012.30 Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems, Lars Rohwedder
12.3013.30 Lunch
13.301400 Business meeting
Chair: Suzanna Rezende
14,0014.20 Online Bin Covering with Frequency Predictions, Magnus Berg
14.2014.40 LPS via LCS, Rolf Fagerberg
14.4015.00 Pure Binary Finger Search Trees, Casper Rysgaard
15.0015.30 Coffee
Chair: Kim Skak Larsen
15.3015.50 A New Perspective on Adaptive Sorting Based on Persistence, Jens Kristian Refsgaard Schou
15.5016.10 Sweeping a Domain with LineofSight Between Covisible Agents, Kien C. Huynh
16.1016.30 An Improved Lower Bound on the Number of Pseudoline Arrangements, Justin Dallant
18.30 Dinner
Abstracts for the workshop 22 November
Lars Rohwedder
Sensitivity, Proximity and FPT Algorithms for Exact Matroid Problems
We consider the problem of finding a basis of a matroid with weight exactly equal to a given target. Here weights can be discrete values from {Delta,...,Delta} or more generally mdimensional vectors of such discrete values. We resolve the parameterized complexity completely, by presenting an FPT algorithm parameterized by Delta and m for arbitrary matroids. Prior to our work, no such algorithms were known even when weights are in {0,1}, or arbitrary Delta and m=1. Our main technical contributions are new proximity and sensitivity bounds for matroid problems, independent of the number of elements. These bounds imply FPT algorithms via matroid intersection. Joint work with Friedrich Eisenbrand and Karol Węgrzycki.
Jens Kristian Refsgaard Schou
PersiSort: A New Perspective on Adaptive Sorting Based on Persistence
Adaptive sorting exploits the structure of a partially sorted listin particular, the sorted segments of a list called runsto improve its performance.
Persistent homology, on the other hand, is a topological data analysis tool that captures a space's topological features at different scales.
In this paper, we combine these two seemingly unrelated concepts and introduce a new perspective on adaptive sorting.
We introduce a new stable sorting algorithm, referred to as the Persistence Sort (or PersiSort in short), which utilizes the persistence pairs among the local extrema of a list.
Given a list of $n$ elements containing $r$ runs with run entropy $H$, we prove, for the first time, that any adaptive sorting algorithm that uses the twowaymerge subroutine (AdaptMerge) of Carlsson \etal~(1990) performs $\Oh{nH}=\Oh{n\log r}$ comparisons to merge precomputed runs based on its predetermined merge policy, and is therefore worstcase optimal.
Using PersiSort, we then provide a new way to analyze adaptive sorting with a persistencebased arrangement of runs.
Unlike previous work such as PowerSort and TimSort, PersiSort does not consider the number of elements in each run but the values of elements in the sorting process.
We finally discuss the scenarios when PersiSort outperforms several stateoftheart adaptive sorting algorithms.
Magnus Berg
Online Bin Covering with Frequency Predictions
We study the bin covering problem where a multiset of items from a fixed set S ⊆ (0,1] must be split into disjoint subsets while maximizing the number of subsets whose contents sum to at least 1. We focus on the online discrete variant, where S is finite, and items arrive sequentially. In the purely online setting, we show that the competitive ratios of best deterministic (and randomized) algorithms converge to 1/2 for large S, similar to the continuous setting. Therefore, we consider the problem under the prediction setting, where algorithms may access a vector of frequencies predicting the frequency of items of each size in the instance. In this setting, we introduce a family of online algorithms that perform nearoptimally when the predictions are correct. Further, we introduce a second family of more robust algorithms that presents a tradeoff between the performance guarantees when the predictions are perfect and when predictions are adversarial. Finally, we consider a stochastic setting where items are drawn independently from any fixed but unknown distribution of S. Using results from the PAClearnability of probabilities in discrete distributions, we introduce a purely online algorithm whose averagecase performance is nearoptimal with high probability for all finite sets S and all distributions of S.
Kien C. Huynh
Sweeping a Domain with LineofSight Between Covisible Agents
We consider sweeping a polygonal domain using variablelength segments whose endpoints can be considered to be mobile agents moving with bounded speeds; a point in the domain is swept when it belongs to one of the segments. The objective is to sweep the domain as quickly as possible. We show that the problem is NPhard even in simple polygons and even for a single segment (two agents), and give constantfactor approximation algorithms, both for simple polygons and polygons with holes.
Our approximations are obtained by introducing a new type of "window partition" of the polygon, which may find other applications. For domains with holes, our results are based on a nontrivial topological argument proving a surprising fact: a connected subset of the domain, whose points are not traced by the agents, may contain at most one hole.
Casper Rysgaard
Pure Binary Finger Search Trees
We present dynamic binary search trees where each node only stores a value and pointers to its parent and its children. We denote such binary search trees pure binary search trees. Our structure supports finger searches in worstcase $O(\lg d)$ time, where $d$ is the rank difference between the node given by the finger and the node found by the search. Inserting a new node with a successor or predecessor value for a node pointed to by a finger and deleting a node in the tree pointed to by a finger are supported in amortized $O(1)$ time and worstcase $O(\lg n)$ time, where $n$ is the number of nodes in the tree. The temporary working space during the operations is $O(1)$ words.
The result is obtained by an alternative representation of the redblack trees by Guibas and Sedgewick [FOCS 1978] that encodes bits of information in the tree structure, generalizing the encoding of 23trees by Brown [IPL 1979], and rearranging the nodes in a redblack tree ("folding" left and right paths) such that the predecessor and successor of a node can always be found in worstcase constant time. The same time bounds can easily be obtained by, say, redblack trees and AVL trees augmented with pointers to the predecessor and successor of each node. The novelty of our result is that we store no extra information than the binary tree structure. The structure can be represented by two pointers per value, i.e., the same representation as a doubly linked list.
Rolf Fagerberg
LPS via LCS
Two standard textbook problems illustrating dynamic programming are to find the longest common subsequence (LCS) of two strings and to find the longest palindromic subsequence (LPS) of a single string. A popular claim is that the LPS of a string can be computed as the LCS of the string and its reversal. We investigate the correctness of this claim.
Tuukka Korhonen
LinearTime Algorithms for kEdgeConnected Components, kLean Tree Decompositions, and More
The kedgeconnected components of a graph are defined by putting two vertices u and v into the same component if they cannot be separated from each other by cutting less than k edges (it can be shown that this is indeed an equivalence relation among the vertices). We give an algorithm for computing the kedgeconnected components of a given graph that works in lineartime when k is any constant, solving a longstanding problem in graph algorithms. We also give lineartime algorithms for other problems about finding edge cuts or vertex separators of size less than k and decomposing a graph along them.
Amik Raj Behera
Local Correction of LowDegree Polynomials
Local correction refers to the algorithmic task of recovering a local piece of information about a codeword from its corrupted version, and the challenge is to do this by making very few queries to the corrupted codeword.
Evaluations of lowdegree polynomials over finite fields form a code with good properties and have been studied extensively. In our work, we consider the setting where lowdegree polynomials are over product sets and not over a vector space. Without the rich algebraic properties of vector spaces, the task of local correction becomes significantly difficult and requires new approaches, more combinatorial in flavor.
We will see the results regarding local (list) correction and see a couple of combinatorial tasks that we understand in the way to design these algorithms. This is based on a joint work with Prashanth Amireddy, Manaswi Paraashar, Srikanth Srinivasan, and Madhu Sudan.
Low Degree Local Correction Over the Boolean Cube
Hanzhi Wang
Revisiting Local Computation of PageRank: Simple and Optimal
PageRank is an important graph analysis metric, initially proposed by the founders of Google to compute the importance ranking of web pages on the Google search engine. In 2007, Reid Andersen, Christian Borgs, Jennifer Chayes, John E. Hopcroft, Vahab S. Mirrokni, and ShangHua Teng began studying the problem of computing PageRank contributions on large graphs, i.e., given a target node t in a graph, finding all nodes in the graph that significantly affect the PageRank score of t. They jointly proposed the ApproxContributions algorithm, which uses local search on large graphs to compute these PageRank contributions. Since its proposal, the ApproxContributions algorithm has received widespread attention and has become a cornerstone algorithm for PageRank computation, with various modifications widely applied to a variety of graph analysis problems. However, the ApproxContributions algorithm has long lacked meaningful analytical results regarding worstcase computational complexity.
In this talk, I will revisit the ApproxContributions algorithm and present a concise analysis establishing an optimal upper bound on its worstcase time complexity under the arccentric graphaccess model. Furthermore, I will discuss how our optimal analysis of ApproxContributions helps bridge the longstanding theoretical gap between the upper and lower bounds on the time complexity for computing singlenode PageRank, a crucial query problem in PageRank computation.
This is based on joint work with Zhewei Wei, JiRong Wen, and Mingji Yang.
Prateek Dwivedi
Monotone BoundedDepth Complexity of Homomorphism Polynomials
For every fixed graph H, it is known that homomorphism counts from H and colourful Hsubgraph counts can be determined in O(n^{t+1}) time on nvertex input graphs G, where t is the treewidth of H. On the other hand, a running time of n^{o(t / \log t)} would refute the exponentialtime hypothesis. Komarath et al. studied algebraic variants of these counting problems, i.e., homomorphism and subgraph polynomials for fixed graphs H. In recent work, we characterize the power of monotone boundeddepth circuits for homomorphism and colourful subgraph polynomials. This leads us to a natural hierarchy of graph parameters, which capture the width of tree decompositions for H when the underlying tree is required to have depth at most \Delta. We prove monotone circuit lower bounds for productdepth \Delta circuits computing homomorphism polynomial for H. This allows us to derive an optimal depth hierarchy theorem for monotone boundeddepth circuits through graphtheoretic arguments.
Frederik Haagensen
An Optimal Randomized Algorithm for Finding the Saddlepoint
A saddlepoint of an n × n matrix is an entry that is the maximum of its row and the minimum
of its column. Saddlepoints give the value of a twoplayer zerosum game, corresponding to its
purestrategy Nash equilibria; efficiently finding a saddlepoint is thus a natural and fundamental
algorithmic task.
For finding a strict saddlepoint (an entry that is the strict maximum of its row and the strict
minimum of its column) we recently gave an O(n log∗ n)time algorithm, improving the O(n log n)
bounds from 1991 of Bienstock, Chung, Fredman, Schäffer, Shor, Suri and of Byrne and Vaserstein.
In this paper, we present an optimal O(n)time algorithm for finding a strict saddlepoint based on
random sampling. Our algorithm, like earlier approaches, accesses matrix entries only via unitcost
binary comparisons. For finding a (nonstrict) saddlepoint, we extend an existing lower bound to
randomized algorithms, showing that the trivial O(n^2) runtime cannot be improved even with the
use of randomness
Amir Nikabadi
Hitting all longest paths in Hfree graphs
Under what conditions does a connected graph G have a vertex that intersects all of its longest paths? This question has been resolved for certain graph families, including split graphs, graphs of treewidth at most 2, and graphs of matching numbers at most 3. However, it is still unclear whether other graphs characterized by a finite set of forbidden induced subgraphs yield a positive answer to this question.
I will try to prove that if G is a connected graph that does not contain any of the following as an induced subgraph:
(i) K_{1,3} together with a graph H of size at most 5, or
(ii) P_5 along with any of the following graphs: triangle, paw, or diamond,
then G admits a vertex intersecting all of its longest paths.
Based on a joint work with Paloma T. Lima.
Justin Dallant
An Improved Lower Bound on the Number of Pseudoline Arrangements
Arrangements of pseudolines are classic objects in discrete and computational geometry. They have been studied with increasing intensity since their introduction almost 100 years ago. The study of the number B_n of nonisomorphic simple arrangements of n pseudolines goes back to Goodman and Pollack, Knuth, and others. It is known that Bn is in the order of 2^Θ(n^2) and finding asymptotic bounds on b_n=log_2(Bn)/n^2 remains a challenging task. In 2011, Felsner and Valtr showed that 0.1887≤b_n≤0.6571 for sufficiently large n. The upper bound remains untouched but in 2020 Dumitrescu and Mandal improved the lower bound constant to 0.2083. Their approach utilizes the known values of B_n for up to n=12.
We tackle the lower bound by utilizing dynamic programming and the LindströmGesselViennot lemma. Our new bound is b_n≥0.2721 for sufficiently large n. The result is based on a delicate interplay of theoretical ideas and computer assistance.
31st ARCO 2024
DTU, Copenhagen 12 April 2024
Programme
 First session (chaired by Teresa Anna Steiner),
 Christian Janos Lebeda, ITU: "Better Differentially Private Approximate Histograms and Heavy Hitters using the MisraGries Sketch"
 Anna Brötzner, MAU: "Flips in Odd Matchings"
(short break)  Kasper Green Larsen, Aarhus: "Bagging is an Optimal PAC Learner"
 Lasse Wulf, DTU: "A large and natural Class of Sigma2 and Sigma3 complete Problems in Bilevel and Robust Optimization"
 Second session (chaired by Ivor van der Hoog),
 Lene Monrad Favrholdt, SDU: "Online Unit Profit Knapsack with Predictions"
 Jack Tor Stade, KU: "Hardness of Packing Simple Polygons with Unit Squares"
 Juliette M.V. Vlieghe, DTU: "Sparsity Parametrised Edge Colouring"
 Third session (chaired by Lasse Wulf),
 Andy Oertel, Lund: "Certified 01 Integer Linear Programming"
 Duri Andrea Janett, KU: "Supercritical Tradeoffs for Resolution Depth Versus Width"
 Amik Raj Behera, Aarhus: "Local Correction of Linear Functions"
30th ARCO 2023
SDU Odense, 24 November 2023.
Programme
09:00 – 10:00 Welcome and coffee
10:00 – 10:20 Kevin Schewior (SDU): Threshold Testing and SemiOnline Prophet Inequalities
10:20 – 10:40 Sudarshan Shyam (AU): EnvyFreeness under Generalized Assignment Constraints
10:40 – 11:00 Noel Arteche (Lund): Quantum Automatability
11:00 – 11:15 Coffee Break
11:15 – 11:35 Aniket Basu Roy (AU): Packing Fréchet Balls
11:35 – 11:55 Anna Brötzner (Malmö): m Watchmen’s Routes in Minbar Polygons
11:55 – 12:15 Camilla Okkels (ITU): MultiLevel LocalitySensitive Hashing for SubQuadratic Time DBSCAN Clustering
12:15 – 13:00 Lunch Break (sandwiches provided)
13:00 – 13:20 Arthur da Cunha (AU): Revisiting the Random Subset Sum Problem
13:20 – 13:40 Jens Kristian Refsgaard Schou (AU): Functional Point Location
13:40 – 14:00 Coffee Break
14:00 – 14:20 Mingmou Liu (KU): SparsityDimension TradeOffs for Oblivious Subspace Embeddings
14:20 – 14:40 George Osipov (Linköping): Almost Satisfiable Systems of Linear Equations
14:40 – 15:10 Coffee Break with Cake
15:10 – 15:30 Hao Wu (KU): Tight Data Access Bounds for Private Topk Selection
15:30 – 15:50 Teresa Anna Steiner (DTU): Differential Privacy with Strings Attached
15:50 – 16:10 Joel Daniel Andersson (KU): A Smooth Binary Mechanism for Efficient Private Continual Observation
16:10 – 16:30 Coffee Break
16:30 – 16:50 Daniel Rutschmann (DTU): Triangulations Admit Dominating Sets of Size 2n/7
16:50 – 17:10 Jonas Conneryd (Lund): Graph Colouring Is Hard on Average for Polynomial Calculus
17:10 – 17:30 Anders Yeo (SDU): Digraph Partitioning Generalizing MaxCut
17:30 – 20:00 Dinner (pizza provided)
29th ARCO 2023
KU Copenhagen 21 April 2023.
Programme
09:30 – 10:00 Arrivals and welcome (Coffee served)
10:00 – 10:20 Riko Jacob: Universal Sorting: Finding a DAG using Priced Comparisons
10:20 – 10:40 Niv Dayan: Scaling Database Storage Engines
10:40 – 11:00 Tamalika Mukherjee: Differentially Private L2Heavy Hitters in the Sliding Window Model
11:00 – 11:20 Coffee break
11:20 – 11:40 Magnus Berg: Online Minimum Spanning Trees with Weight Predictions
11:40 – 12:00 Bengt J. Nilsson: Online Bin Covering of Vectors with a Little Advice
12:00 – 13:00 Lunch
13:00 – 13:20 Mikkel Abrahamsen: Partitioning a Polygon Into Small Pieces
13:20 – 13:40 Aniket Basu Roy: Covering Orthogonal Polygons with Rectangles
13:40 – 14:00 Coffee break
14:00 – 14:20 Hanwen Zhang: Minimum Star Partitions of Simple Polygons in Polynomial Time
14:20 – 14:40 Marcin Pilipczuk: On metric embeddings of planar graphs
14:40 – 15:00 Coffee break
15:00 – 15:20 Mingmou Liu: Lower Bounds for Sparse Oblivious Subspace Embeddings
15:20 – 15:40 Zhile Jiang: Computing better approximate pure Nash equilibria in cut games via semidefinite programming
16:30 – Pizza and Open Problems
28th ARCO 2022
ITU Copenhagen 11 November 2022
Programme
09:45 – 10:00 Arrival and welcome
10:00 – 10:30 Rasmus Pagh: Improved Utility Analysis of Private CountSketch
10:30 – 11:00 Coffee
11:00 – 11:30 Valentin Polishchuk: Geometric secluded paths and planar satisfiability
11:30 – 12:00 Kevin Schewior: The Itinerant List Update Problem
12:00 – 13:30 Lunch
13:30 – 14:00 Ioana Bercea: Daisy Bloom Filters
14:00 – 14:30 Karl A. F. Fehrs: The Complexity of Learning ApprovalBased Multiwinner Voting Rules
14:30 – 15:00 Coffee
15:00 – 15:30 Radu Curticapean: Determinants from homomorphisms
15:30 – 16:00 Riko Jacob: Universal Sorting: Finding a DAG using Priced Comparisons
16:00 – 19:00 Will Code for Drinks / Informal pizza dinner at ITU
27th ARCO 2022
Malmö University, 6 May 2022.
Programme
10:30 – 11:00 Welcome and coffee
11:00 – 11:30 Matti Karppa: HyperLogLogLog: Cardinality Estimation With One Log More
11:30 – 12:00 Tord Stordalen: Predecessor on the UltraWide Word RAM
12:00 – 13:40 Lunch
13.40 – 14:00 Ioana Bercea: Daisy Bloom Filters
14:00 – 14:30 Erik Krohn: Local Search, More Powerful Than You Thought
14:30 – 15:00 Riko Jacob: On the Complexity of List Ranking in the Parallel External Memory Model
15:00 – 15:40 Coffee break
15:40 – 16:10 Kilian Risse: The Minimum Circuit Size Problem is hard for Sum of Squares
16:10 – 16:30 Aleksander Bjørn Grodt Christiansen: Maintaining smaller outorientations
17:30 – Dinner