2 November 2017

BARC is off to a flying start with 10 accepted papers for SODA'18


No less than 10 papers authored or co-authored by members of BARC at DIKU have made it to the top algorithms event of the year, the ACM-SIAM Symposium on Discrete Algorithm (SODA’18) in New Orleans.

As a newly founded research center for basic algorithms, BARC already climbs to a significant position by representing this number of papers at SODA. Additionally, head of BARC, Professor Mikkel Thorup, is Invited Plenary Speaker at the conference.

The research behind the 10 SODA accepts has been funded by an Advanced Grant from the Danish Council for Independent Research by the Marie Curie Fellowship program, and, of course, by DIKU.

- These 10 papers means that our newly started BARC center is off to a flying start, says Mikkel Thorup.

Discovery eliminates severe bottleneck for Google and Vimeo

BARC is dedicated to fundamental research of algorithms theory but the people behind it have a track record of astonishing algorithmic discoveries leading to major industrial applications.

One of those discoveries is described in the article Consistent hashing with bounded loads and is among the SODA accepts. This discovery eliminates a severe bottleneck for companies like Google and Vimeo, serving hundreds of millions of users every day and has revolutionized load balancing and allowed scaling up to today’s data traffic worldwide.


It is a general article about a theoretical discovery but has had substantial impact on the industry already by addressing assigning clients to servers in a dynamic environment where both clients and servers can leave the system. This result has since been discussed in industrial blogs such as Google’s research Blog and Vimeo’s Engineering Blog.

The 10 accepted papers

  • The Entropy of Backwards Analysis

    Mathias Bæk Tejs Knudsen and Mikkel Thorup

  • Dynamic Bridge-Finding in Õ(log² n) Amortized Time

    Jacob Holm, Eva Rotenberg and Mikkel Thorup

  • Consistent Hashing with Bounded Loads

    Vahab Mirrokni, Mikkel Thorup and Morteza Zadimoghaddam

  • A Hamiltonian Cycle in the Square of a 2-connected Graph in Linear Time
    Stephen Alstrup, Agelos Georgakopoulos, Eva Rotenberg and Carsten Thomassen 

  • Online bipartite matching with amortized O(log2 n) replacements

    Aaron Bernstein, Jacob Holm and Eva Rotenberg

  • The Bane of Low-Dimensionality Clustering

    Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg and Alan Roytman

  • Better Tradeoffs for Exact Distance Oracle in Planar Graphs

    Paweł Gawrychowski, Shay Mozes, Oren Weimann and Christian Wulff-Nilsen

  • Hierarchical Clustering: Objective Functions and Algorithms
    Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn and Claire Mathieu

  • A Fast Approximation Scheme for Low-Dimensional k-Means
Vincent Cohen-Addad

  • A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals

    Vincent Cohen-Addad, Éric Colin de Verdière and Arnaud de Mesmay

To read the full version of the paper Consistent Hashing with Bounded Loads by Vahab Mirrokni, Mikkel Thorup and Morteza Zadimoghaddam, go to https://arxiv.org/abs/1608.01350