Scope
The European Symposium on Algorithms (ESA) is one of the premier conferences on algorithms. It is organized in collaboration with the European Association for Theoretical Computer Science (EATCS) and is a part of ALGO 2022.
Important Dates
- Paper submission deadline: April 21, 23:59 AoE. (EasyChair submission system)
- Notification: June 18
- Camera ready: July 3
- LIPIcs receives files: July 8
- Proceedings published: September 2
- Conference: September 5-7, 2022, in Potsdam, Germany (early on Monday – late on Wednesday)
Call for Papers
The symposium seeks original algorithmic contributions for problems with relevant theoretical and/or practical applications. Papers with a strong emphasis on the theoretical analysis of algorithms should be submitted to Track A, while papers reporting on the results of extensive experimental evaluations and/or providing original contributions to the engineering of algorithms for practical applications should be submitted to Track B. Submissions that prove or explain known results in a much clearer, simpler or more elegant way than done before should be submitted to track S. There will be a Best Student Paper Award as well as a Best Paper Award, both sponsored by EATCS. In order for a paper to be considered for the Best Student Paper Award, all of its authors are required to be students.
Paper submission and proceedings
Papers should be submitted electronically via the EasyChair submission system. The ESA 2022 proceedings will be published in the Leibniz International Proceedings in Informatics (LIPIcs) series.
Submission Guidelines
Authors are invited to submit an extended abstract or full paper of at most 11 pages excluding the title page, references, and an optional appendix. The submission should be typeset using a 10-point or larger font in a single-column format with ample spacing throughout and 2cm margins all around on A4-size paper. We recommend, but not strictly require, making your initial submission adhere to LIPIcs publication guidelines. Proofs omitted due to space constraints must be placed in an appendix. This appendix can even comprise an entire full version of the paper. The appendix will be read by the program committee members at their discretion. In particular, appendices of accepted papers are not going to be published in the proceedings. The main part of the submission should therefore contain a clear technical presentation of the merits of the paper, including a discussion of the paper’s importance within the context of prior work and a description of the key technical and conceptual ideas used to achieve its main claims. These guidelines are strict: submissions deviating significantly from these guidelines risk being rejected without consideration of their merits. Papers should be submitted electronically via the EasyChair submission system. Results previously published (or scheduled for publication) in another conference proceedings or journal will not be accepted at ESA. Simultaneous submission to other conferences with published proceedings, or to multiple tracks of ESA 2022, is also not permitted. By submitting a paper the authors acknowledge that in case of acceptance, at least one of the authors must register at ALGO 2022, attend the conference, and present the paper.
Double-Blind Reviewing
The conference will employ a lightweight double-blind reviewing process. Submissions should not reveal the identity of the authors in any way. In particular, authors’ names, affiliations, and email addresses should not appear at the beginning or in the body of the submission. Authors should ensure that any references to their own related work is in the third person (e.g., not “We build on our previous work …” but rather “We build on the work of …”). The purpose of the double-blind reviewing is to help PC members and external reviewers come to an initial judgment about the paper without bias, not to make it impossible for them to discover the authors if they were to try. Nothing should be done in the name of anonymity that weakens the submission or makes the job of reviewing the paper more difficult. In particular, important references should not be omitted or anonymized. In addition, authors should feel free to disseminate their ideas or draft versions of their paper as they normally would. For example, authors may post drafts of their papers on the web, submit them to arXiv, and give talks on their research ideas. In case there exist publicly available versions of the submission online, the authors might mention this in their submission (without providing references/links), and briefly explain the differences if any. Alternatively, they might communicate the details to the chairs, who will keep them confidential unless revealing them to the PC is needed for a fair judgment. Authors with further questions on double-blind reviewing are encouraged to contact the PC chairs.
Topics
Papers presenting original research in all areas of algorithmic research are sought, including but not limited to:
- Algorithm engineering
- Algorithmic aspects of networks
- Algorithmic game theory
- Algorithmic Data Science
- Approximation algorithms
- Computational biology
- Computational finance
- Computational geometry
- Combinatorial optimization
- Data compression
- Data structures
- Databases and information retrieval
- Distributed and parallel computing
- Graph algorithms
- Hierarchical memories
- Heuristics and meta-heuristics
- Mathematical programming
- Mobile computing
- Online algorithms
- Parameterized algorithms
- Pattern matching
- Quantum computing
- Randomized algorithms
- Scheduling and resource allocation problems
- Streaming algorithms
Announcement: ESA Track S
This year, the European Symposium on Algorithms ESA’22 will have a Track S (for Simplicity) inviting contributions that simplify algorithmic results.
We would like to expand the community around simplification of algorithmic
results, encourage and reward research towards simplification and clarity.
We find that simpler algorithms are easier to implement, bridging the gap
between theory and practice, and we find that new simple or elegant proofs
are easier to understand and to teach, and may contain interesting new
insights whose relevance only the future will reveal.
Scope: We invite submissions that prove or explain known results in a
much clearer, simpler or more elegant way than done before. Submissions
that improve on the state of the art from a theoretical or practical
viewpoint should instead be submitted to tracks A or B.
Paper assessment: Contingent on being in scope for ESA, submitted
papers will primarily be judged on the simplicity and elegance of their
proofs or algorithms, and the clarity of their presentation.
Track S will run as an experiment for the 2022 ESA in Potsdam, Germany.
It will have its own PC and PC chair, and the submission/acceptance
deadlines follow the schedule for tracks A and B.
Accepted Papers
The proceedings are available here.
- Galactic Token Sliding
- Adaptive-Adversary-Robust Algorithms via Small Copy Tree Embeddings
- An Improved Algorithm for Finding the Shortest Synchronizing Words
- Correlated Stochastic Knapsack with a Submodular Objective
- Counting Simplices in Hypergraph Streams
- Online metric allocation and time-varying regularization
- Lyndon Arrays Simplified
- There and Back Again: On Applying Data Reduction Rules by Undoing Others
- Combining Predicted and Live Traffic with Time-Dependent A* Potentials
- A Local Search Algorithm for Large Maximum Weight Independent Set Problems
- Tight Bounds for Online Matching in Bounded-Degree Graphs with Vertex Capacities
- Learning-Augmented Query Policies for Minimum Spanning Tree with Uncertainty
- Cardinality estimation using Gumbel distribution
- Improved Search of Relevant Points for Nearest-Neighbor Classification
- Maximum Weight b-Matchings in Random-Order Streams
- Longest Cycle above Erdős–Gallai Bound
- Computing Smallest Convex Intersecting Polygons
- Improved bounds for online balanced graph re-partitioning
- Intersection Searching amid Tetrahedra in 4-space and Efficient Continuous Collision Detection
- A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension
- Polynomial kernel for immersion hitting in tournaments
- Dynamic Coloring of Unit Interval Graphs with Limited Recourse Budget
- Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
- Computing the $4$-Edge-Connected Components of a Graph: An Experimental Study
- List Colouring Trees in Logarithmic Space
- Simple worst-case optimal adaptive prefix-free coding
- Enumerating Minimal Connected Dominating Sets
- O(1) Steiner Point Removal in Series-Parallel Graphs
- Classical and quantum algorithms for variants of Subset-Sum via dynamic programming
- Vertex Sparsifiers for Hyperedge Connectivity
- Approximate Circular Pattern Matching
- Multi-Dimensional Stable Roommates in 2-Dimensional Euclidean Space
- Hardness of Token Swapping on Trees
- Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs
- Faster Path Queries in Colored Trees via Sparse Matrix Multiplication and Min-Plus Product
- Approximation Algorithms for ROUND-UFP and ROUND-SAP
- Near Optimal Algorithm for Fault Tolerant Distance Oracle and Single Source Replacement Path problem
- Improved Polynomial-Time Approximations for Clustering with Minimum Sum of Radii or Diameters
- Distinct Elements in Streams: An Algorithm for the (Text) Book
- A simpler QPTAS for scheduling jobs with precedence constraints
- Maximizing Sums of Non-monotone Submodular and Linear Functions: Understanding the Unconstrained Case
- Scheduling Kernels via Configuration LP
- Bounding and Computing Obstacle Numbers of Graphs
- A Polynomial-Time Algorithm for 1/3-Approximate Nash Equilibria in Bimatrix Games
- Finding a Cluster in Incomplete Data
- Turbocharging Heuristics for Weak Coloring Numbers
- Techniques for Generalized Colorful k-Center Problems
- On the External Validity of Average-Case Analyses of Graph Algorithms
- Width Helps and Hinders Splitting Flows
- Search-Space Reduction via Essential Vertices
- Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold (extended abstract)
- Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs
- Online Spanners in Metric Spaces
- An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions
- Fast RSK correspondence by doubling search
- The Price of Hierarchical Clustering
- When Are Cache-Oblivious Algorithms Cache Adaptive? A Case Study of Matrix Multiplication and Sorting
- Data structures for node connectivity queries
- Average sensitivity of the Knapsack Problem
- Resource Sharing Revisited: Local Weak Duality and Optimal Convergence
- An Empirical Evaluation of $k$-Means Coresets
- Simple Dynamic Spanners with Near-optimal Recourse against an Adaptive Adversary
- Chromatic $k$-Nearest Neighbor Queries
- Fast Computation of Zigzag Persistence
- TSP in a Simple Polygon
- The Pareto cover problem
- Embedding phylogenetic trees in networks of low treewidth
- Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings
- Computing NP-hard Repetitiveness Measures via MAX-SAT
- Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited
- (In-)Approximability Results for Interval, Resource Restricted, and Low Rank Scheduling
- Localized geometric moves to compute hyperbolic structures on triangulated 3-manifolds
- Faster Approximate Covering of Subcurves under the Fréchet Distance
- Hedonic Games and Treewidth Revisited
- Determinants from homomorphisms
- Non-Adaptive Edge Counting and Sampling via Bipartite Independent Set Queries
- Conditional Lower Bounds for Dynamic Geometric Measure Problems
- Efficient Fréchet distance queries for segments
- Abstract morphing using the Hausdorff distance and Voronoi diagrams
- On Polynomial Kernels for Traveling Salesperson Problem and its Generalizations
- ParGeo: A Library for Parallel Computational Geometry
- SAT Backdoors: Depth Beats Size
- Taming graphs with no large creatures and skinny ladders
- A Unified Framework for Hopsets
- Submodular Maximization Subject to Matroid Intersection on the Fly
- Approximation Algorithms for Continuous Clustering and Facility Location Problems
- Sparse Temporal Spanners with Low Stretch
- Optimizing the Safe Flow Decompositions in DAGs
- Spanner Approximations in Practice
- Computing treedepth in polynomial space and linear fpt time
- Faster algorithm for Unique (k,2)-CSP
- Simple Streaming Algorithms for Edge Coloring
Committees
Chairs
- Shiri Chechik (track A), Tel Aviv University
- Gonzalo Navarro (track B), Universidad de Chile
- Eva Rotenberg (track S), Technical University of Denmark
Steering Committee
- Hannah Bast (chair), Albert-Ludwigs-Universität Freiburg
- Shiri Chechik, Tel Aviv University
- Fabrizio Grandoni, IDSIA, USI-SUPSI
- Robert Krauthgamer, The Weizmann Institute of Science
- Petra Mutzel (Chair), University of Bonn
- Gonzalo Navarro, Universidad de Chile
- Rasmus Pagh , University of Copenhagen
- Eva Rotenberg, Technical University of Denmark
- Peter Sanders, Karlsruhe Institute of Technology (KIT)
- Sabine Storandt, University of Konstanz
PC members (Track A)
- Mikkel Abrahamsen, University of Copenhagen
- Peyman Afshani, Aarhus University
- Pankaj K. Agarwal, Duke University
- Sepehr Assadi, Rutgers University
- Per Austrin, KTH
- Leonid Barenboim, The Open University of Israel
- Surender Baswana, IIT Kanpur
- Maike Buchin, Ruhr University Bochum
- Jaroslaw Byrka, University of Wrocław
- Diptarka Chakraborty, National University of Singapore
- Shiri Chechik (chair), Tel Aviv University
- Vincent Cohen-Addad, Google Research
- Mark de Berg, TU Eindhoven
- Mahsa Derakhshan, UC Berkley and Northeastern University
- Michael Dinitz, Johns Hopkins University
- Michal Dory, ETH Zurich
- Matthias Englert, University of Warwick
- Thomas Erlebach, Durham University
- Fedor Fomin, University of Bergen
- Dimitris Fotakis, National Technical University of Athens
- Hsin Hao Su, Boston College
- Martin Hoefer, Goethe University
- Ravishankar Krishnaswamy, Microsoft Research
- Janardhan Kulkarni, Microsoft Research
- Divyarthi Mohan, Tel Aviv University
- Shay Mozes, Reichman University
- Wolfgang Mulzer, Freie Universität Berlin
- Ofer Neiman, Ben-Gurion University
- Aleksandar Nikolov, University of Toronto
- Sigal Oren, Ben-Gurion University
- Fahad Panolan, IIT Hyderabad
- Adi Rosén, FILOFOCS – CNRS
- Sushant Sachdeva, University of Toronto
- Stefan Schmid, University of Vienna and TU Berlin
- Roy Schwartz, Technion
- Bruce Shepherd, University of British Columbia
- Shay Solomon, Tel Aviv University
- Xiaorui Sun, University of Illinois
- Dimitrios Thilikos, LIRMM, Université de Montpellier, CNRS
- Ohad Trabelsi, The University of Michigan
- Oren Weimann, University of Haifa
- Philip Wellnitz, Max Planck Institute for Informatics
- Raphael Yuster, University of Haifa
PC members (Track B)
- Diego Arroyuelo, Universidad Técnica Federico Santa María
- Philip Bille, Danmarks Tekniske Universitet
- Thomas Bläsius, Karlsruhe Institute of Technology
- Christina Boucher, University of Florida
- Sándor Fekete, Technische Universität Braunschweig
- José Fuentes-Sepúlveda, Universidad de Concepción
- Gramoz Goranci, Universitat Wien
- Giuseppe Italiano, Università degli studi di Roma “Tor Vergata”
- Shweta Jain, University of Utah
- Dominik Kempa, Stony Brook University
- Veli Mäkinen, University of Helsinki
- Catherine McGeoch, Amherst College
- David Mount, University of Maryland
- Gonzalo Navarro (chair), Universidad de Chile
- Steven Skiena, Stony Brook University
- Matthias Stallmann, North Carolina State University
PC members (Track S)
- Josh Alman, Columbia University
- Michael Bender, Stony Brook University
- Karl Bringmann, Saarland University
- Raphaël Clifford, University of Bristol
- Anne Driemel, Universität Bonn
- Paweł Gawrychowski, University of Wrocław
- Monika Henzinger, University of Vienna
- John Iacono, Université libre de Bruxelles
- Tomasz Kociumaka, University of California, Berkeley
- Irina Kostitsyna, Eindhoven University of Technology
- William Kuszmaul, Massachusetts Institute of Technology
- Rasmus Kyng, ETH Zürich
- Kitty Meeks, University of Glasgow
- Marcin Pilipczuk, University of Warsaw
- Kent Quanrud, Purdue University
- Eva Rotenberg (chair), Technical University of Denmark
- Shikha Singh, Williams College
- Jukka Suomela, Aalto University
- Haitao Wang, Utah State University
- Andreas Wiese, TU Munich
- Anna Zych-Pawlewicz, University of Warsaw
Invited Speakers
- Virginia Vassilevska Williams, Massachusetts Institute of Technology
- Simon Puglisi, University of Helsinki
Proceedings
The ESA 2022 proceedings will be published in the Leibniz International Proceedings in Informatics (LIPIcs) series.