16 July 2021

BARC has 4 accepted papers at STOC '21


Again four BARC papers have been accepted at the prestigious ACM Symposium on Theory of Computing, STOC, as well as one paper by the closely affiliated complexity group MIAO headed by Jakob Nordström.

BARC logo

BARC papers accepted and presented at STOC’21:

  • Load balancing with Dynamic Set of Balls and Bin by Anders Aamand, Mikkel Thorup, Jakob Knudsen (University of Copenhagen, BARC)

  • A full complexity dichotomy for immanant families by Radu Curticapean (IT University of Copenhagen, BARC)

  • A Deterministic Algorithm for the MST Problem in Constant Rounds of Congested Clique by Krzysztof Nowicki (University of Copenhagen, BARC and University of Wrocław)

  • Support of Closed Walks and Second Eigenvalue Multiplicity of Graphs by Theo McKenzie (University of California, Berkeley); Peter M. R. Rasmussen (University of Copenhagen, BARC); Nikhil Srivastava (UC Berkeley)

MIAO logoMIAO papers accepted and presented at STOC’21:

  • Automating Algebraic Proof Systems is NP-Hard by Susanna F. de Rezende (Institute of Mathematics of the Czech Academy of Sciences); Mika Göös (EPFL); Jakob Nordström (University of Copenhagen & Lund University); Toniann Pitassi (University of Toronto & IAS); Robert Robere (McGill University); Dmitry Sokolov (St. Petersburg State University & PDMI RAS)


And we also welcome Danupon Nanongkai to the team, who has presented no less than three papers at this year’s STOC:

  • Breaking the Quadratic Barrier for Matroid Intersection by Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai (KTH Royal Institute of Technology)

  • Vertex Connectivity in Poly-logarithmic Max-flows by Jason Li (Carnegie Mellon University); Danupon Nanongkai (KTH Royal Institute of Technology); Debmalya Panigrahi (Duke University); Thatchaphol Saranurak (Toyota Technological Institute at Chicago); Sorrachai Yingchareonthawornchai (Aalto University)

  • Distributed Weighted Min-Cut in Nearly-Optimal Time by Michal Dory (ETH Zurich, Switzerland); Yuval Efron (University of Toronto, Canada); Sagnik Mukhopadhyay, Danupon Nanongkai (KTH Royal Institute of Technology, Sweden)