Abstract
This special issue contains 7 articles which are based on extended abstracts presented at the 36th Symposium on Theoretical Aspects of Computer Science (STACS). The conference was a very special event as it was held at the University of Montpellier from March 10 to March 13, 2020, the last week before the first COVID lockdown. The extended abstracts were chosen among the top papers of those which were selected for presentation in a highly competitive peer-review process (after which only 56 papers out of 242 submissions were accepted, putting it among the most competitive conferences in Theoretical Computer Science).Compared with the original conference papers, the articles have been extended with a description of the context, full proofs, and additional results. They underwent a rigorous reviewing process, following the TOCS journal standards, completely independent from the selection process of STACS 2020.The topics of the chosen papers cover various areas of Theoretical Computer Science, that is, algorithmic graph theory, automata theory, linear dynamical systems, parameterized complexity analysis, and distributed algorithms. In what follows, we briefly describe the contributions of the papers, ordered alphabetically by author names.In the paper “Observation and Distinction. Representing Information in Infinite Games”, Dietmar Berwanger and Laurent Doyen compare two approaches for modelling imperfect information in infinite games by using finite-state automata. The first approach views information as the result of an observation process driven by a sequential Mealy machine. The second approach features indistinguishability relations described by synchronous two-tape automata. The indistinguishability-relation model turns out to be strictly more expressive than the one based on observations.Vertex Cover is one of the most studied problems in algorithmic graph theory and well established hardness results are known to the computation of both the exact and an approximate solution. The paper “Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs”, by Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich and Maximilian Katzmann, is motivated by the observation that algorithms are performing well, compared to the announced complexity bounds, on real-world networks. As a tentative explanation of this phenomenon, they studied Vertex Cover on hyperbolic random graphs, which are known to share properties with real-world networks.The paper “Typical sequences revisited – Computing width parameters of graphs” authored by Hans L. Bodlaender, Lars Jaffke and Jan Arne Telle, is a contribution to the theory of typical sequences. Typical sequences were introduced independently by Lagergren and Arnborg and by Bodlaender and Kloks in 1991 to compute treewidth and pathwidth of a graph in FPT linear time. By showing a new lemma on typical sequences, the authors show that typical sequences can be used to compute further width parameters on some digraph classes.Approximation algorithms were known to solve the Unsplittable Flow Cover problem (UFP). In their work “Fixed parameter algorithms for unsplittable flow cover, Andrés Cristi, Mathieu Mari and Andreas Wiese considered UFP under the view point of parameterized complexity. Despite a hardness result for standard parameterization (solution size), they show that under some relaxations on the demand of the solution, fixed parameterized algorithms can be obtained, including a parameterized approximation scheme.A coloring of the two dimensional grid is called valid with respect to a set P of n × m rectangular patterns if all n × m sub-patterns of the coloring are in P. Nivat’s conjecture states that such a coloring, which is in addition of low complexity, is necessarily periodic. In their paper “Decidability and Periodicity of Low Complexity Tilings”, Jarkko Kari and Etienne Moutot make very nice progress on this conjecture, which has not been resolved for 25 years.Proving circuit lower bounds via efficient circuit satisfiability algorithms seems a promising route, since instead of argueing against all circuits of a certain class, one has “just” to come up with an efficient algorithm for satisfiability. In their paper “Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms”, Nikhil Vyas and R. Ryan Williams continue this approach and present a new strong lower bound consequence of non-trivial #SAT algorithms for certain circuit classes.In their work “An Automaton Group with PSPACE-Complete Word Problem”, Jan Philipp Wächter and Armin Weiß construct an automaton group with a PSPACE-complete word problem. This proves a conjecture due to Steinberg. Furthermore, the constructed group has a provably more difficult, namely EXPSPACE-complete, compressed word problem and acts over a binary alphabet, meaning that it is optimal in terms of the alphabet size.We are grateful to the authors for their contributions and to the reviewers for their helpful reports. We also want to thank the members of the Program Committee and the Steering Committee of STACS 2020. Finally, we express our gratitude to the members of the TOCS editorial office for their cooperation when preparing this special issue.