Programme

In the field of computational logic, two classes of finite automata are considered fundamental: deterministic and nondeterministic automata (DFAs and NFAs). In a more fine-grained approach three natural intermediate classes were introduced, defined by restricting the number of accepting runs of the input NFA. The classes are called: unambiguous, finitely ambiguous, and polynomially ambiguous finite automata. It was observed that central problems, like equivalence, become tractable when the input NFA is restricted to some of these classes. This naturally brought interest into problems determining whether an input NFA belongs to the intermediate classes. I will present a nearly complete characterization of the fine-grained complexity of these problems: the respective quadratic and cubic running times of Allauzen et al. are optimal under the Orthogonal Vectors hypothesis or the \(k\)-Cycle hypothesis, for alphabets with at least two symbols. This is based on the work available at https://arxiv.org/abs/2501.14725.

The aim of this talk is to spark your interest in one of the three central hypotheses in fine-grained complexity: the All-Pairs Shortest Path (APSP) conjecture. The conjecture asserts that no algorithm can compute pairwise distances in a graph faster than \(O(n^{3-a})\) time for any \(a > 0\). I will demonstrate how this assumption can be used not only to prove the conditional optimality of your own algorithms, but also be used to speed them up. We will briefly cover why you should definitely know about the conjecture (even if you are not from the field), and where to find more. Along the way, I will also mention open problems and recent results, both my own and from others.

We study the complexity of verifying algebraic identities on finite structures. While previous work gave an optimal randomized algorithm for testing associativity, whether distributivity could be verified in subcubic time remained open. We resolve this by giving an \(O(|S|^\omega)\)-time algorithm for distributivity, together with a matching conditional lower bound based on the Triangle Detection Hypothesis. We propose arithmetic progression detection in small universes as a consequential algorithmic challenge: we show that unless we can detect 4-term arithmetic progressions in a set \(X \subseteq \{1,\dots,N\}\) in time \(O(N^{2-\varepsilon})\), then (a) the 3-uniform 4-hyperclique hypothesis is true, and (b) verifying certain identities requires running time \(|S|^{3-o(1)}\). Finally, we classify a large family of 3-variable identities into three complexity classes: quadratic, \(O(|S|^\omega)\), or cubic (all with matching conditional lower bounds), and obtain near-optimal algorithms for verifying whether a finite algebraic structure is a field or a ring.

Given \(k\) nondeterministic finite automata (NFA), constructing an NFA that recognises the intersection of their languages is a basic problem in automata theory. We observe that the classical Cartesian product construction is non-optimal in the worst case, namely when the automata have many transitions. For a fixed alphabet, the Cartesian product of two NFA may have \(\Theta(m^2)\) transitions if these NFA have at most \(n\) states and \(m\) transitions each.
In this talk, we give alternative constructions with \(O(m n)\) transitions, and more generally with \(O(m n^{k-1})\) transitions for the intersection of \(k\) NFA (for fixed \(k \ge 2\) and alphabet \(\Sigma\)). This yields a faster algorithm for the NFA intersection emptiness problem (NFA IE), which we prove optimal unless there is a breakthrough in combinatorial algorithms for detecting \((k+1)\)-cliques in undirected graphs (i.e., under the Combinatorial \(k\)-Clique Hypothesis). Finally, we show that these constructions also provide a faster certification scheme for NFA IE, suggesting that a tight fine-grained reduction from Boolean satisfiability (SAT) to NFA IE is unlikely. This is joint work with Dmitry Chistikov.