We discuss the problem of recognizing regular languages in a variant of the streaming model of computation, called the sliding window model. In this model, we are given a size of the sliding window n and a stream of symbols. At each time instant, we must decide whether the suffix of length n of the current stream (``the window'') belongs to a given regular language.

In this work, we make an important step forward and combine the sliding window model with the property testing setting, which results in ultra-efficient algorithms for all regular languages. Informally, a sliding window property tester must accept the active window if it belongs to the language and reject it if it is far from the language. We consider deterministic and randomized sliding window property testers with one-sided and two-sided errors. In particular, we show that for any regular language, there is a deterministic sliding window property tester that uses logarithmic space and a randomized sliding window property tester with two-sided error that uses constant space.

The talk is based on a joint work with Ganardi, Hucke, and Lohrey published in ISAAC 2019.

The General Adjoint Functor Theorem of Freyd has a straightforward extension to the enriched setting. There is also a Weak Adjoint Functor Theorem, due to Kainen, and providing a sufficient condition for the existence of a weak left adjoint, where weakness refers to the existence but not uniqueness of factorizations. I will report on recent joint work with Steve Lack and Lukas Vokrinek, in which we prove a weak adjoint functor theorem in the enriched context. This actually contains the other three theorems as special cases. Our base for enrichment will be a monoidal model category. Our motivating example involves simplicially enriched categories, where the base category of simplicial sets is equipped with the Joyal model structure. The theorem then has applications to the Riehl-Verity theory of infinity-cosmoi.

We will discuss the emerging substructures in graphs with degree constraints, digraphs, acyclic digraphs, and 2-CNF below the point of their respective phase transitions. While long time ago, probabilistic method allowed to establish the location of the transition points, sometimes without establishing the fine structure inside the window, more and more refined methods gradually become available. With analytic combinatorics as a main tool, we will see what exactly is happening when a random structure approaches its boiling point. Based on joint works with Elie de Panafieu and Vlady Ravelomanana.

Suppose that you want to check whether a graph satisfies some (graph) property. The goal is to minimize the number of queries to the adjacency matrix. You are given as an “untrusted hint” an isomorphic copy of the graph. You must always be correct, but the number of queries made is only measured when the hint is correct. Do such unlabeled certificates help? In the worst case? Per instance?

In this talk I will discuss labeled and unlabeled certificates, in particular in the context of ``instance optimality“. This is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively.

Joint work with Tomer Grossman and Ilan Komargodski

Suppose that you want to check whether a graph satisfies some (graph) property. The goal is to minimize the number of queries to the adjacency matrix. You are given as an “untrusted hint” an isomorphic copy of the graph. You must always be correct, but the number of queries made is only measured when the hint is correct. Do such unlabeled certificates help? In the worst case? Per instance?

In this talk I will discuss labeled and unlabeled certificates, in particular in the context of ``instance optimality”. This is a measure of goodness of an algorithm in which the performance of one algorithm is compared to others per input. This is in sharp contrast to worst-case and average-case complexity measures, where the performance is compared either on the worst input or on an average one, respectively.

Joint work with Tomer Grossman and Ilan Komargodski

Symmetry is a fundamental concept in mathematics, the sciences, and beyond. Understanding symmetries is often crucial for understanding structures. In computer science, we are mainly interested in the symmetries of combinatorial structures. Computing the symmetries of such a structure is essentially the same as deciding whether two structures are the same (“isomorphic”). Algorithmically, this is a difficult task that has received a lot of attention since the early days of computing. It is a major open problem in theoretical computer science to determine the precise computational complexity of this “Graph Isomorphism Problem”.

One of the earliest applications of isomorphism testing was in chemistry, more precisely chemical information systems. Today, applications of isomorphism testing and symmetry detection are ubiquitous in computing. Prominent examples appear in optimisation, malware detection, and machine learning. However, in many of these applications, we only need to decide if two structures are sufficiently similar, rather than exactly the same. It turns out that determining how similar two structures are is an even harder computational problem than deciding whether they are isomorphic.

My talk will be an introduction to algorithmic aspects of symmetry and similarity, ranging from the fundamental complexity theoretic “Graph Isomorphism Problem” to applications in optimisation and machine learning.

Categorical abstraction is a powerful organizing principle in computer algebra. In this talk, we explain the concept of constructive category theory and how we implement this concept in our software project CAP-Categories, algorithms, programming. In CAP it is possible to implement higher algorithms and data structures using basic categorical operations as primitives, which in turn often rely on classical algorithms in computer algebra like the computation of Gröbner bases. As an example, we show how our categorical framework can be used for computing with finitely presented functors.

We will discuss the expressive and computational power of Ordinary Differential Equations (ODEs). We present the general theory of discrete ODEs for computation theory, we illustrate this with various examples of algorithms, and we provide several implicit characterizations of complexity and computability classes.