ESA 2021 Accepted Papers

Sariel Har-Peled and Timothy Zhou. Improved Approximation Algorithms for Tverberg Partitions
Benoit Larose, Petar Marković, Barnaby Martin, Daniel Paulusma, Siani Smith and Stanislav Živný. QCSP on Reflexive Tournaments
Eden Pelleg and Stanislav Živný. Additive Sparsification of CSPs
Michał Dębski, Marta Piecyk and Paweł Rzążewski. Faster 3-coloring of small-diameter graphs
Sepehr Assadi, Deeparnab Chakrabarty and Sanjeev Khanna. Graph Connectivity and Single Element Recovery via Linear and OR Queries
Jasper C.H. Lee, Jerry Li, Christopher Musco, Jeff Phillips and Wai Ming Tai. Finding an Approximate Mode of a Kernel Density Estimate
Lars Gottesbüren, Tobias Heuer, Peter Sanders, Christian Schulz and Daniel Seemaier. Deep Multilevel Graph Partitioning
Markus Anders and Pascal Schweitzer. Parallel Computation of Combinatorial Symmetries
Thomas Bläsius, Simon D. Fink and Ignaz Rutter. Synchronized Planarity with Applications to Constrained Planarity Problems
Florian Wörz and Jan-Hendrik Lorenz. Evidence for Long-Tails in SLS Algorithms
Nikhil Ayyadevara and Ashish Chiplunkar. The Randomized Competitive Ratio of Weighted $k$-Server is at Least Exponential
Ryoga Mahara. Extension of Additive Valuations to General Valuations on the Existence of EFX
Mark de Berg, Morteza Monemizadeh and Yu Zhong. k-Center Clustering with Outliers in the Sliding-Window Model
Grigorios Loukides and Solon Pissis. Bidirectional String Anchors: a New String Sampling Mechanism
Hendrik Fichtenberger, Monika Henzinger and Wolfgang Ost. Differentially Private Algorithms for Graphs Under Continual Observation
Saman Ahmadi, Guido Tack, Daniel Harabor and Philip Kilby. Bi-objective Search with Bi-directional A*
Claire Mathieu and Hang Zhou. A Simple Algorithm for Graph Reconstruction
Hu Ding. Stability Yields Sublinear Time Algorithms for Geometric Optimization in Machine Learning
Tomas Martinez-Munoz and Andreas Wiese. FPT and FPT-approximation algorithms for Unsplittable Flow on Trees
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul, Ely Porat and Clifford Stein. Incremental Edge Orientation in Forests
Joergen Bang-Jensen, Kristine Vitting Klinkby and Saket Saurabh. k-Distinct Branchings Admits a Polynomial Kernel
Krzysztof Potępa. Faster Deterministic Modular Subset Sum
Maor Akav and Liam Roditty. A unified approach for all pairs approximate shortest paths in weighted undirected graphs
Moses Ganardi. Compression by Contracting Straight-Line Programs
Aaron Bernstein, Aditi Dudeja and Seth Pettie. Incremental SCC Maintenance in Sparse Graphs
Timothy M. Chan and Zhengcheng Huang. Dynamic Colored Orthogonal Range Searching
Timothy M. Chan. All-Pairs Shortest Paths for Real-Weighted Undirected Graphs with Small Additive Error
Yishu Wang, Arnaud Mary, Marie-France Sagot and Blerina Sinaimeri. A general framework for enumerating equivalence classes of solutions
Éric Colin de Verdière and Thomas Magnard. An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes
Thomas Bläsius, Tobias Friedrich and Christopher Weyand. Efficiently Computing Maximum Flows in Scale-Free Networks
Jean Cardinal, John Iacono and Grigorios Koumoutsos. Worst-Case Efficient Dynamic Geometric Independent Set
Zdenek Dvorak and Abhiruk Lahiri. Approximation schemes for bounded distance problems on fractionally treewidth-fragile graphs
Davide Bilò, Sarel Cohen, Tobias Friedrich and Martin Schirneck. Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles
Marilena Leichter, Benjamin Moseley and Kirk Pruhs. An Efficient Reduction of a Gammoid to a Partition Matroid
Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner and Sebastian Wild. Hypersuccinct Trees – New universal tree source codes for optimal compressed tree data structures and range minima
Simon D. Fink, Matthias Pfretzschner and Ignaz Rutter. Experimental Comparison of PC-Trees and PQ-Trees
William Maxwell and Amir Nayyeri. Generalized max-flows and min-cuts in simplicial complexes
Evripidis Bampis, Christoph Dürr, Thomas Erlebach, Murilo S. de Lima, Nicole Megow and Jens Schlöter. Orienting (hyper)graphs under explorable stochastic uncertainty
Jean Cardinal, Justin Dallant and John Iacono. An Instance-optimal Algorithm for Bichromatic Rectangular Visibility
Klaus Jansen and Malin Rau. Closing the gap for single resource constraint scheduling
Sujoy Bhore and Csaba Toth. Online Euclidean Spanners
Daniel Neuen. Isomorphism Testing Parameterized by Genus and Beyond
Thomas Bläsius, Tobias Friedrich and Maximilian Katzmann. Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry
Pavel Dvořák, Michal Koucký, Karel Král and Veronika Slívová. Data Structures Lower Bounds and Popular Conjectures
Lin Chen, Hossein Esfandiari, Thomas Fu, Vahab Mirrokni and Qian Yu. Feature Cross Search via Submodular Optimization
Yaron Fairstein, Ariel Kulik and Hadas Shachnai. Modular and Submodular Optimization with Multiple Knapsack Constraints via Fractional Grouping
Karthekeyan Chandrasekaran and Weihang Wang. $\ell_p$-norm Multiway Cut
Daniel Dadush, Zhuan Khye Koh, Bento Natura and László A. Végh. An Accelerated Newton-Dinkelbach Method and its Application to Two Variables Per Inequality Systems
Radu Curticapean, Holger Dell and Thore Husfeldt. Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths
Kolja Junginger, Ioannis Mantas, Evanthia Papadopoulou, Martin Suderland and Chee Yap. Certified Approximation Algorithms for the Fermat Point and n-Ellipses
Fabrizio Grandoni, Tobias Mömke and Andreas Wiese. Faster (1+epsilon)-approximation for Unsplittable Flow on a Path via resource augmentation and back
Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń and Wiktor Zuba. Hardness of Detecting Abelian and Additive Square Factors in Strings
Zhiyang He, Jason Li and Magnus Wahlström. Near-linear-time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs
Marek Cygan, Alexander Kulikov, Ivan Mihajlin, Maksim Nikolaev and Grigory Reznikov. Minimum Common String Partition: Exact Algorithms
Nico Bertram, Jonas Ellert and Johannes Fischer. Lyndon Words Accelerate Suffix Sorting
Alexander Braun, Matthias Buttkus and Thomas Kesselheim. Asymptotically Optimal Welfare of Posted Pricing for Multiple Items with MHR Distributions
Evangelos Kosinas, Loukas Georgiadis and Giuseppe F. Italiano. Computing the 4-Edge-Connected Components of a Graph in Linear Time
Yassine Hamoudi. Quantum Sub-Gaussian Mean Estimator
Thomas Lavastida, Benjamin Moseley, R. Ravi and Chenyang Xu. Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing
Guillaume Sagnol and Daniel Schmidt Genannt Waldschmidt. Restricted Adaptivity in Stochastic Scheduling
Daniel Lokshtanov, Subhash Suri and Jie Xue. Efficient Algorithms for Least Square Piecewise Polynomial Regression
David Caballero, Timothy Gomez, Robert Schweller and Tim Wylie. Covert Computation in Staged Self-Assembly: Verification is PSPACE-complete
Therese Biedl, Anna Lubiw, Anurag Murty Naredla, Peter Dominik Ralbovsky and Graeme Stroud. Distant Representatives for Rectangles in the Plane
Anna Lubiw and Anurag Murty Naredla. The Visibility Center of a Simple Polygon
Ramanujan M. Sridharan. On Approximate Compressions for Connected Minor-hitting Sets
Alejandro Flores-Velazco and David Mount. Boundary-Sensitive Approach for Approximate Nearest-Neighbor Classification
Leon Kellerhals, Malte Renken and Philipp Zschoche. Parameterized Algorithms for Diverse Multistage Problems
Ojas Parekh and Kevin Thompson. Beating Random Assignment for Approximating Quantum 2-Local Hamiltonian Problems
Panagiotis Charalampopoulos, Tomasz Kociumaka, Solon Pissis and Jakub Radoszewski. Faster Algorithms for Longest Common Substring
Boris Klemz. Convex drawings of hierarchical graphs in linear time, with applications to planar graph morphing
Katrin Casel, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits and Ziena Zeif. Balanced Crown Decomposition for Connectivity Constraints
Carlos Alegría, Ioannis Mantas, Evanthia Papadopoulou, Marko Savić, Hendrik Schrezenmaier, Carlos Seara and Martin Suderland. The Voronoi Diagram of Rotating Rays with applications to Floodlight Illumination
Dominik Kempa and Ben Langmead. Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing
Katarzyna Paluch and Mateusz Wasylkiewicz. Restricted t-matchings via half-edges
David Lee, Samuel McCauley, Shikha Singh and Max Stein. Telescoping Filter: A Practical Adaptive Filter
Younan Gao and Meng He. Space Efficient Two-Dimensional Orthogonal Colored Range Counting
Sepehr Assadi and Shay Solomon. Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach
Jana Cslovjecsek, Friedrich Eisenbrand, Michał Pilipczuk, Moritz Venzin and Robert Weismantel. Efficient sequential and parallel algorithms for multistage stochastic integer programming using proximity
Peter Sanders, Marvin Williams and Roman Dementiev. Engineering MultiQueues: Fast Relaxed Concurrent Priority Queues
Wojciech Nadara, Mateusz Radecki, Marcin Smulewicz and Marek Sokołowski. Determining 4-edge-connected components in linear time