List of accepted papers

ESA 2016 Accepted Papers

Markus Chimani and Tilo Wiedera. An ILP-based Proof System for the Crossing Number Problem
Lukasz Kowalik, Juho Lauri and Arkadiusz Socala. On the fine-grained complexity of rainbow coloring
Moran Feldman, Moshe Tennenholtz and Omri Weinstein. Distributed Signaling Games
Mikkel Abrahamsen and Bartosz Walczak. Outer Common Tangents and Nesting of Convex Hulls in Linear Time and Constant Workspace
Raphael Clifford, Markus Jalsenius and Benjamin Sach. Cell-probe lower bounds for bit stream computation
Jean Cardinal, John Iacono and Aurélien Ooms. Solving $k$-SUM using few linear queries
Marcin Bienkowski, Martin Böhm, Jaroslaw Byrka, Marek Chrobak, Christoph Dürr, Lukáš Folwarczný, Łukasz Jeż, Jiří Sgall, Nguyen Kim Thang and Pavel Veselý. Online Algorithms for Multi-Level Aggregation
Karl Bringmann, László Kozma, Shay Moran and N.S. Narayanaswamy. Hitting Set for hypergraphs of low VC-dimension
Hiro Ito. Every property is testable on a natural class of scale-free multigraphs
Dror Rawitz and Adi Rosén. Online Budgeted Maximum Coverage
Chris Schwiegelshohn and Uwe Schwiegelshohn. The Power of Migration for Online Slack Scheduling
Clément Maria and Jonathan Spreer. Admissible colourings of 3-manifold triangulations for Turaev-Viro type invariants
Nathanaël François, Frederic Magniez, Michel De Rougemont and Olivier Serre. Streaming Property Testing of Visibly Pushdown Languages
Moritz Baum, Thomas Bläsius, Andreas Gemsa, Ignaz Rutter and Franziska Wegner. Scalable Exact Visualization of Isocontours in Road Networks via Minimum-Link Paths
Melika Abolhassani, T-H. Hubert Chan, Fei Chen, Hossein Esfandiari, Mohammadtaghi Hajiaghayi, Hamid Mahini and Xiaowei Wu. Beating Ratio 0.5 for Weighted Oblivious Matching Problems
Isaac B. Goldstein, Tsvi Kopelowitz, Moshe Lewenstein and Ely Porat. How Hard is it to Find (Honest) Witnesses?
Ely Porat, Eduard Shahbazian and Roei Tov. New Parameterized Algorithms for APSP in Directed Graphs
Jian Li and Wei Zhan. Almost All Even Yao-Yao Graphs Are Spanners
Huang Lingxiao, Jian Li, Jeff Phillips and Haitao Wang. $\varepsilon$-Kernel Coresets for Stochastic Points
George Christodoulou, Martin Gairing, Sotiris Nikoletseas, Christoforos Raptopoulos and Paul Spirakis. Strategic Contention Resolution with Limited Feedback
Sathish Govindarajan, Rajiv Raman, Saurabh Ray and Aniket Basu Roy. Packing and Covering with Non-piercing regions
Matthias Mnich, Virginia Vassilevska Williams and Laszlo Vegh. A 7/3-Approximation for Feedback Vertex Sets in Tournaments
Jesper Nederlof. Finding Large Set Covers Faster via the Representation Method
Daniel Neuen. Graph Isomorphism for unit square graphs
Haitao Wang. On the Geodesic Centers of Polygonal Domains
Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal and Rishi Saket. On the Hardness of Learning Sparse Parities
Guy Blelloch, Jeremy Fineman, Phillip B. Gibbons, Yan Gu and Julian Shun. Efficient Algorithms with Asymmetric Read and Write Costs
Pavel Kolev and Kurt Mehlhorn. A Note On Spectral Clustering
Xiaohui Bei, Jugal Garg, Martin Hoefer and Kurt Mehlhorn. Computing Equilibria in Markets with Budget-Additive Utilities
Stefan Edelkamp and Armin Weiß. BlockQuicksort: How Branch Mispredictions don't affect Quicksort
Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan and Pan Xu. New Algorithms, Better Bounds, and a Novel Model for Online Stochastic Matching
Casper Kejlberg-Rasmussen, Tsvi Kopelowitz, Seth Pettie and Mikkel Thorup. Faster Worst Case Deterministic Dynamic Connectivity
Jean-Lou De Carufel, Matthew Katz, Matias Korman, André van Renssen, Marcel Roeloffzen and Shakhar Smorodinsky. On interference among moving sensors and related problems
Chien-Chung Huang and Sebastian Ott. A Combinatorial Approximation Algorithm for Graph Balancing with Light Hyper Edges
Thomas Kesselheim and Andreas Tönnis. Think Eternally: Improved Algorithms for the Temp Secretary Problem and Extensions
Ralf Borndörfer, Heide Hoppmann and Marika Karbstein. Separation of Cycle Inequalities for the Periodic Timetabling Problem
Subhash Khot and Rishi Saket. Hardness of Bipartite Expansion
Monika Henzinger and Stefan Neumann. Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning
Stephen Alstrup, Søren Dahlgaard, Mathias Bæk Tejs Knudsen and Ely Porat. Sublinear Distance Labeling
Eduard Eiben, Robert Ganian, Kustaa Kangas and Sebastian Ordyniak. Counting Linear Extensions: Parameterizations by Treewidth
Krzysztof Fleszar, Matthias Mnich and Joachim Spoerhase. New Algorithms for Maximum Disjoint Paths Based on Tree-Likeness
Édouard Bonnet and Tillmann Miltzow. Parameterized Hardness of Art Gallery Problems
Gramoz Goranci, Monika Henzinger and Mikkel Thorup. Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time
Christoph Dürr, Christian Konrad and Marc Renault. On the Power of Advice and Randomization for Online Bipartite Matching
Stefan Kratsch. A randomized polynomial kernelization for Vertex Cover with a smaller parameter
Giorgio Lucarelli, Kim Thang Nguyen, Abhinav Srivastav and Denis Trystram. Online Non-preemptive Scheduling in a Resource Augmentation Model based on Duality
Erin Chambers, Irina Kostitsyna, Maarten Löffler and Frank Staals. Homotopy Measures for Representative Trajectories
Andrew Drucker, Jesper Nederlof and Rahul Santhanam. Exponential Time Paradigms Through the Polynomial Time Lens
Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas and Takeaki Uno. Approximation and Hardness of Token Swapping
Greg Bodwin and Sebastian Krinninger. Fully Dynamic Spanners with Worst-Case Update Time Guarantees
Thomas Bläsius, Tobias Friedrich and Anton Krohmer. Hyperbolic Random Graphs: Separators and Treewidth
Adam Kunysz. The Strongly Stable Roommates Problem
Quirijn W. Bouts, Irina Kostitsyna, Marc van Kreveld, Wouter Meulemans, Willem Sonke and Kevin Verbeek. Mapping polygons to the grid with small Hausdorff and Fréchet distance
Ruta Mehta, Ioannis Panageas, Georgios Piliouras and Sadra Yazdanbod. The Complexity of Genetic Diversity
Davide Bilò, Luciano Gualà, Stefano Leucci and Guido Proietti. Compact and Fast Sensitivity Oracles for Single-Source Distances
Tamal Dey, Dayu Shi and Yusu Wang. SimBa: An Efficient Tool for Approximating Rips-filtration Persistence via Simplicial Batch-collapse
Petra Berenbrink, Tom Friedetzky, Peter Kling, Frederik Mallmann-Trenn and Christopher Wastell. Plurality Consensus in Arbitrary Graphs: Lessons Learned from Load Balancing
Kiril Solovey and Dan Halperin. Sampling-based bottleneck pathfinding with applications to Frechet matching
Huck Bennett, Daniel Dadush and Noah Stephens-Davidowitz. On the Lattice Distortion Problem
Krishnendu Chatterjee, Rasmus Ibsen-Jensen and Andreas Pavlogiannis. Optimal Reachability and a Space-Time Tradeoff for Distance Queries in Constant-Treewidth Graphs
Guy Even, Moti Medina and Adi Rosen. A Constant Approximation Algorithm for Scheduling Packets on Line Networks
Lasse Kliemann, Christian Schielke and Anand Srivastav. A Streaming Algorithm for the Undirected Longest Path Problem
Michele Borassi and Emanuele Natale. KADABRA is an ADaptive Algorithm for Betweenness via Random Approximation
Riley Murray, Megan Chao and Samir Khuller. Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms
Juha Kärkkäinen and Dominik Kempa. Faster External Memory LCP Array Construction
Alantha Newman, Heiko Roeglin and Johanna Seif. The Alternating Stock Size Problem and the Gasoline Puzzle
Edouard Bonnet, Laszlo Egri and Daniel Marx. Fixed-parameter Approximability of Boolean MinCSPs
Cameron Chalk, Eric Martinez, Robert Schweller, Luis Vega, Andrew Winslow and Tim Wylie. Optimal Staged Self-Assembly of General Shapes
Joshua Wang and Tim Roughgarden. The Complexity of the k-means Method
Michael Crouch, Andrew McGregor, Gregory Valiant and David P. Woodruff. Stochastic Streams: Sample Complexity vs. Space Complexity
Shay Golan, Tsvi Kopelowitz and Ely Porat. Streaming Pattern Matching with d Wildcards
Tobias Arndt, Danijar Hafner, Thomas Kellermeier, Simon Krogmann, Armin Razmjou, Martin Krejca, Ralf Rothenberger and Tobias Friedrich. Probabilistic Routing for On-Street Parking Search
Matti Karppa, Petteri Kaski, Jukka Kohonen and Padraig Ó Catháin. Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
Radu Curticapean. Counting matchings with k unmatched vertices in planar graphs
Thomas Bläsius, Tobias Friedrich, Anton Krohmer and Sören Laue. Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane
Andreas S. Schulz and José Verschae. Min-sum scheduling under precedence constraints

Revised 28.02.2024