Four papers accepted to SODA (Symposium on Discrete Algorithms)

Four research papers from the “Big Data Algorithms” research group have been accepted for presentation at the A*-ranked ACM-SIAM Symposium on Discrete Algorithms (SODA). SODA is the top conference in the field of algorithms and one of the most prestigious conferences in theoretical computer science. In 2025, the conference will take place in mid-January in New Orleans.

The “Big Data Algorithms” research group has been based at the University of Salzburg since 2022 and is led by Prof. Sebastian Forster. All four publications were developed as part of the DynASoAr project, funded through an ERC Starting Grant secured by Forster. The goal of the project is to study dynamic algorithms that can efficiently adapt to changes in input data.

Professor Forster, together with his PhD student Antonis Skarlatos, investigated a problem in unsupervised machine learning known as consistent clustering. The question they addressed is: How can a set of dynamically changing points be grouped around a given number of centers so that the distances of the points to the centers are minimized while ensuring the selected centers change as little as possible? The two computer scientists proved that a single center change after each update to the point set is sufficient, thus improving the previously known bound of two center changes.

Dutch researcher Tijn de Vos, together with a colleague from the Technical University of Denmark, developed new algorithms for determining the connectivity and local density of dynamically changing graphs. This work significantly surpassed a 20-year-old bound. A key result leading to this achievement was a structural finding on the decomposition of graphs into acyclic subgraphs.

De Vos has been at the University of Salzburg since 2020 and successfully defended his dissertation at the end of November.

Dr. Aditi Dudeja, a postdoctoral researcher in the DynASoAr project, is represented with two contributions. Dudeja earned her PhD at Rutgers University and has been at the University of Salzburg for a year as an expert in matching problems. In her first paper submitted to the conference, Dudeja and her former colleagues studied coloring problems in dynamic graphs.

The topic of her second contribution is finding optimal matchings in dynamic graphs. Dudeja and her coauthors demonstrated that, in many cases, existing algorithms for “static” graphs can be utilized without significantly compromising the quality of the solution.