STACS 2023

The Symposium on Theoretical Aspects of Computer Science—STACS—will take place from 7th March to 9th March 2023 in Universitat Hamburg, Hamburg, Germany. It starts right away—tomorrow.

I cannot go to this one, but it has been a strong theory conference over the past. And I wish I could go to this one. Ken says the same. He recalls that the two of us connected in a big way at STACS 1994 in Caen, France.

For the first time, STACS 2023 will consist of two tracks, A and B, to facilitate the work of the program committee(s). Track A is dedicated to algorithms and data structures, complexity and games. Track B will cover automata, logic, semantics and theory of programming.

The conference is chaired by Petra Berenbrink and Mamadou Kanté for track A, Anuj Dawar and Patricia Bouyer-Decitre for track B.

Invited Speakers

There are three invited speakers. Here are their titles and talk descriptions:

Eva Rotenberg (Technical University of Denmark): Amortised Analysis of Dynamic Data Structures.

In dynamic data structures, one is interested in efficiently facilitating queries to a data set, while being able to efficiently perform updates as the data set undergoes changes. Often, relaxing the efficiency measure to the amortised setting allows for simpler algorithms. A well-known example of a data structure with amortised guarantees is the splay tree by Sleator and Tarjan.

Karoliina Lehtinen (CNRS, Aix-Marseille Univercity, LIS, Marseille, France ): A brief history of history-determinism.

Most nondeterministic automata models are more expressive, or at least more succinct, than their deterministic counterparts; however, this comes at a cost, as deterministic automata tend to have better algorithmic properties. History-deterministic automata are an intermediate model that allows a restricted form of nondeterminism: all nondeterministic choices must be resolvable on-the-fly, with only the knowledge of the word prefix read so far—as opposed to general nondeterminism, which allows for guessing the future of the word. History-deterministic automata combine some of the algorithmic benefits of determinism with some of the increased power of nondeterminism, thus enjoying (some of) the best of both worlds.

Moshe Vardi (Rice University): Logical Algorithmics: From Theory to Practice.

The standard approach to algorithm development is to focus on a specific problem and develop for it a specific algorithm. Codd’s introduction of the relational model in 1970 included two fundamental ideas:

(1) Relations provide a universal data representation formalism, and

(2) Relational databases can be queried using first-order logic.

Realizing these ideas required the development of a meta-algorithm, which takes a declarative query and executes it with respect to a database. In this talk, I will describe this approach, which I call Logical Algorithmics, in detail, and explore its profound ramification.

Selected Papers

Here are a few of the accepted papers:

• Edouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez and Stephan Thomasse. Twin-width V: linear minors, modular counting, and matrix multiplication.

• Charles Paperman, Sylvain Salvati and Claire Soyez-Martin. An algebraic approach to vectorial programs.

• Pascal Baumann, Roland Meyer and Georg Zetzsche. Regular Separability in Buchi Vector Addition Systems

• Monika Henzinger, Stefan Neumann, Harald Racke and Stefan Schmid. Dynamic Maintenance of Monotone Dynamic Programs and Applications.

• Satyadev Nandakumar and Subin Pulari. Real numbers equally compressible in every base.

See this for all the papers. That is a complete list.

Open Problems

I highlighted the above papers for personal reasons—hmmm.