10 BARC papers accepted for SODA and SOSA 2023
Basic Algorithm Research Copenhagen is represented at next year’s SODA and SOSA conferences to be held in Florence, Italy, January 22-25, 2023. In total 10 papers are accepted in relation to BARC members.
Hybrid: SIAM Symposium on Simplicity in Algorithms (SOSA23) has accepted four papers authored or co-authored by members of the BARC team:
Simple Set Sketching
Jakob Bæk Tejs Houen, Rasmus Pagh, and Stefan Walzer
Estimating the Effective Support Size in Constant Query Complexity (Link to follow)
Shyam Narayanan and Jakub Tetek
Splay Top Trees
Jacob Holm, Eva Rotenberg, and Alice Ryhl
Sampling an Edge in $O(n/\sqrt{m} + \log \varepsilon^{-1})$ Time via Bernoulli Trial Simulation (Link to follow)
Talya Eden, Shyam Narayanan, and Jakub Tetek
The full list of accepted papers at SOSA ’23
The ACM-SIAM Symposium on Discrete Algorithms (SODA23) focuses on research topics related to efficient algorithms and data structures for discrete problems and has accepted six papers authored or co-authored by members of the BARC team:
Massively Parallel Computation and Sublinear-Time Algorithms for Embedded Planar Graphs
Jakub Tetek and Jacob Holm (BARC, University of Copenhagen)
A Nearly Tight Analysis of Greedy k-means++
Jakub Tetek (BARC, University of Copenhagen); Christoph Grunau, Václav Rozhoň, Ahmet Alper Özüdoğru (ETH Zurich)
Faster Computation of 3-Edge-Connected Components in Digraphs (link to follow)
Loukas Georgiadis (University of Ioannina, Greece); Evangelos Kipouridis (BARC, University of Copenhagen); Charis Papadopoulos (University of Ioannina, Greece); Nikos Parotsidis (Google Research, Switzerland)
Fully Dynamic Exact Edge Connectivity in Sublinear Time (Link to follow)
Gramoz Goranci (University of Glasgow); Monika Henzinger (University of Vienna); Danupon Nanongkai (BARC, University of Copenhagen); Thatchaphol Saranurak (University of Michigan); Mikkel Thorup (BARC, University of Copenhagen); Christian Wulff-Nilsen (Department of Computer Science, University of Copenhagen)
Online Sorting and Translational Packing of Convex Polygons
Anders Aamand (MIT); Mikkel Abrahamsen (BARC, University of Copenhagen); Lorenzo Beretta (BARC, University of Copenhagen); Linda Kleist (TU Braunschweig)
Fair Cuts, Approximate Isolating Cuts, and Approximate Gomory-Hu Trees in Near-Linear Time
Jason Li (UC Berkeley); Danupon Nanongkai (BARC, University of Copenhagen); Debmalya Panigrahi (Duke University); Thatchaphol Saranurak (University of Michigan)
Furthermore, our guest and visiting professor from the University of Warsaw, Marcin Pilipczuk, has three papers accepted to SODA ’23:
Fixed-parameter tractability of Directed Multicut with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation
Meike Hatzel (National Institute of Informatics, Tokyo, Japan); Lars Jaffke (Department of Informatics, University of Bergen, Bergen, Norway); Paloma T. Lima (IT University of Copenhagen, Denmark); Tomáš Masařík (University of Warsaw, Poland); Marcin Pilipczuk (University of Warsaw); Roohani Sharma (Max Planck Institute for Informatics, Germany); Manuel Sorge (TU Wien)
Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
Eun Jung Kim (LAMSADE, Paris-Dauphine University); Stefan Kratsch (HU Berlin); Marcin Pilipczuk (University of Warsaw); Magnus Wahlstrom (Royal Holloway University of London)
A tight quasi-polynomial bound for Global Label Min-Cut
Lars Jaffke (University of Bergen, Norway); Paloma T. Lima (IT University of Copenhagen, Denmark); Tomáš Masařík and Marcin Pilipczuk (University of Warsaw, Poland); Ueverton S. Souza (Fluminense Federal University, Brazil and University of Warsaw, Poland)
The full list of accepted papers at SODA ’23