16 April 2024

9 papers accepted to STOC'24 by BARC members and affiliates


The 56th Annual ACM Symposium on Theory of Computing will boast 9 BARC related presentations.

BARC logo

BARC and affiliates will present 9 exciting papers at this year’s ACM Symposium on Theory of Computing (STOC) held in Vancouver, Canada, June 24-28:

  • Combinatorial Correlation Clustering
    Vincent Cohen-Addad (Google Research, France); Marcin Pilipczuk (University of Warsaw); David Rasmussen Lolck, Mikkel Thorup, Shuyi Yan, Hanwen Zhang (University of Copenhagen)

  • Better coloring of 3-colorable graphs
    Ken-ichi Kawarabayashi (National Institute of Informatics, The University of Tokyo); Mikkel Thorup (University of Copenhagen); Hirotaka Yoneda (The University of Tokyo)

  • On the Power of Homogeneous Algebraic Formulas
    Hervé Fournier (IMJ-PRG, Université Paris Cité); Nutan Limaye (IT University of Copenhagen); Srikanth Srinivasan (University of Copenhagen); Sébastien Tavenas (Université Savoie Mont Blanc, CNRS, LAMA)

  • Local Correction of Linear Functions over the Boolean Cube
    Prashanth Amireddy (Harvard University); Amik Raj Behera (Aarhus University); Manaswi Paraashar, Srikanth Srinivasan (University of Copenhagen); Madhu Sudan (Harvard University)
  • Approximate Earth Mover's Distance in Truly-Subquadratic Time
    Lorenzo Beretta (BARC, University of Copenhagen); Aviad Rubinstein (Stanford University)

  • Minimum Star Partitions of Simple Polygons in Polynomial Time
    Mikkel Abrahamsen (University of Copenhagen); Joakim Blikstad (KTH Royal Institute of Technology & Max Planck Institute for Informatics); André Nusser, Hanwen Zhang (University of Copenhagen)
  • Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
    Tuomas Hakoniemi (University of Helsinki); Nutan Limaye (IT University of Copenhagen); Iddo Tzameret (Imperial College London)

  • The Asymptotic Rank Conjecture and the Set Cover Conjecture are not Both True
    Andreas Björklund (IT University of Copenhagen); Petteri Kaski (Aalto University)

Professor Amir Yehudayoff has a paper accepted at this year’s STOC conference based on work done prior to joining BARC: 

  • Local Borsuk-Ulam, Stability, and Replicability
    Zachary Chase, Bogdan Chornomaz, Shay Moran (Technion); Amir Yehudayoff (Technion-IIT)

To see the full list of accepted papers, click here.