Preface of STACS 2013 Special Issue

Authors: Anca Muscholl Martin Dietzfelbinger

Publish Date: 2015/08/27

Volume: 58, Issue: 4, Pages: 503-505

PDF Link

Abstract

This special issue contains six articles based on extended abstracts that were presented at the 30th Symposium on Theoretical Aspects of Computer Science STACS which was held at the ChristianAlbrechtsUniversität zu Kiel Germany from February 27th to March 2nd 2013 These extended abstracts were among the top papers of those chosen for presentation at STACS 2013 in a highly competitive peerreview process the members of the program committee with chairs Thomas Wilke and Natacha Portier selected only 54 papers out of 254 submissions Compared with the original extended abstracts that appeared in the conference proceedings the articles in this issue have been extended by full proofs and additional results They underwent a further rigorous reviewing process following the TOCS standard completely independent of the selection process of STACS 2013The paper The Arithmetic Complexity of Tensor Contraction considers the fundamental arithmetic complexity class VP This class was originally defined by Valiant in the framework of his theory of arithmetic complexity as the class of sequences of polynomials with polynomially bounded degree that can be computed by polynomially sized circuits Although of quite some interest as the analog of deterministic polynomial time in arithmetic complexity this class is not too well understood so far This is partly due to the fact that no really natural characterization of it has been known In the paper polynomials in VP are characterized as functions obtainable as entries in tensors that can be computed by polynomialsize formulas with tensor contraction as the only operation This does away with a technical condition necessary in earlier related characterizations Further results emphasize the robustness of the characterization This new characterization of VP might open the path to a deeper understanding of this interesting complexity classThe paper Towards a Realistic Analysis of the QuickSelect Algorithm is a deep study in the application of methods of the probabilistic analysis of algorithms to a special version of Hoare’s QuickSelect algorithm which finds an item of a given rank in an unsorted array Here the items in the input are not atomic but strings over a fixed alphabet of symbols which are generated by quite general random processes ranging from fully random over Markov chains to processes with quite strong dependencies This approach makes it possible to compare performance of comparisonbased algorithms like QuickSort and digitalbased algorithms like RadixSort on a common ground While QuickSort has average complexity Tnlog2n in this model the authors show that the expected number of symbol comparisons is Tn with explicitly given leading constants This paper is dedicated to the memory of Philippe Flajolet the muchmissed pioneer and leading figure of the area of the probabilistic analysis of algorithmsThe paper Approximate Comparison of Distance Automata studies distance automata and the problem of approximate comparison of the functions computed by such automata Distance automata are weighted automata over the tropical semiring and they play an important role in deciding problems such as the famous starheight problem for regular languages The main result of the paper is that for any two functions f g computed by distance automata it can be decided whether f=g up to a range of error of ratio e0 the algorithm answers “yes” if f=1eg “no” if f=g and an arbitrary value otherwise This result refines the cornerstone result of the theory of regular cost functions stating that the equivalence of such functions is decidable in contrast the equivalence of weighted automata is a wellknown undecidable problemThe paper Regular Languages of Thin Trees introduces an algebraic framework for regular languages of infinite thin trees in order to obtain effective characterizations for such languages Regular languages of infinite trees have been thoroughly investigated in logic and automata theory since the founding work by Rabin and Büchi but a general algebraic formalism is still missing The novel algebraic tools introduced in this paper for languages of thin trees yield effective characterizations for commutative languages open sets in the standard topology languages definable in the temporal logic EF and languages definable among all trees in weak MSO logicThe paper Automaton Semigroups The TwoState Case contributes to the study of semigroups generated by finite Mealy automata The study of “automaton semigroups” has grown out of the study of “automaton groups” and has received much attention recently The problem of algorithmically determining from a Mealy automaton whether the semigroup it generates is finite is known to be undecidable in general This paper shows that semigroups generated by twostate invertiblereversible Mealy automata are either finite groups or free semigroups and that the finiteness problem for such semigroups is decidable thus exhibiting a new and interesting class with decidable finiteness problemThe paper The Simulated Greedy Algorithm for Several Submodular Matroid Secretary Problems returns to the venerable secretary problem in the matroid version with a submodular monotone weight function Inspecting the objects from the ground set the “secretaries” in random order select a subset that is independent in the matroid and maximizes the total weight of the chosen elements One seeks good approximation algorithms This type of problem has been intensively studied in recent years and the paper included here makes progress in terms of significant improvements of the approximation ratios for special types of matroids laminar transversal A very nice feature of the paper is that it focuses on a known intriguingly simple algorithm Observe some fraction of the object without choosing anyone and later include a newly arriving object if it improves the greedy solution for the test set and does not destroy independence It is the novel clever ideas employed in the analysis of the behavior of the algorithm that makes the paper specialWe thank the authors for submitting their papers to this issue and we thank the referees for their thorough reviews of the manuscripts which were essential in ensuring a high quality of the final versions presented here Thanks are also due to the program committee of STACS 2013 for the first selection process We also thank the editorinchief of TOCS Alan L Selman for giving us the opportunity to edit this special issue and the TOCS team for their support Finally we hope that the readers will find the articles presented in this volume interesting and enjoyable

Keywords: