Four BARC papers and two MIAO papers accepted for FOCS’20

With the following 6 papers BARC and MIAO will be well represented at the 61st Annual IEEE Symposium on Foundation on Computer Science, held as a virtual conference due to COVID-19 , November 16 - 19, 2020.

Near-Optimal Decremental SSSP in Dense Weighted Digraphs
Aaron Bernstein; Maximilian P. Gutenberg; Christian Wulff-Nilsen
Affiliations: Rutgers University New Brunswick, Department of Computer Science; University of Copenhagen; University of Copenhagen

 

Framework for $\exists\mathbb R$-Completeness of Two-Dimensional Packing Problems
Mikkel Abrahamsen; Tillmann Miltzow; Nadja Seiferth
Affiliations: University of Copenhagen; Utrecht University; Freie Universitdt Berlin

 

Subsets and Supermajorities: Optimal Hashing-based Set Similarity Search
Thomas D. Ahle; Jakob B. T. Knudsen
Affiliations: BARC, IT University of Copenhagen; BARC, University of Copenhagen

 

Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
Aaron Bernstein; Maximilian Probst Gutenberg; Thatchaphol Saranurak
Affiliations: Rutgers University; University of Copenhagen; TTIC

 

Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity
Susanna F. de Rezende; Or Meir; Jakob Nordström; Toniann Pitassi; Robert Robere; Marc Vinyals
Affiliations: Institute of Mathematics of the Czech Academy of Sciences; University of Haifa; University of Copenhagen and Lund University; University of Toronto and Institute for Advanced Study; DIMACS and Institute for Advanced Study; Technion

 

KRW Composition Theorems via Lifting
Susanna F. de Rezende; Or Meir; Jakob Nordström; Toniann Pitassi; Robert Robere
Affiliations: Mathematical Institute of the Czech Academy of Sciences.; University of Haifa; University of Copenhagen and Lund University; University of Toronto; DIMACS and University of Toronto and Institute for Advanced Study

Link to all accepted papers for FOCS 2020.