ABSTRACT. We study networks of processes that all execute the same finite-state protocol and communicate via broadcasts. We are interested in two problems with a parameterized number of processes: the synchronization problem which asks whether there is an execution which puts all processes on a given state; and the repeated coverability problem which asks if there is an infinite execution where a given transition is taken infinitely often. Since both problems are undecidable in the general case, we investigate those problems when the protocol is Wait-Only, i.e., it has no state from which a process can both broadcast and receive messages. We establish that the synchronization problem becomes Ackermann-complete, and the repeated coverability problem is in ExpSpace and PSpace-hard.

ABSTRACT. In the \textsc{Telephone Broadcast} problem we are given a graph $G=(V,E)$ with a designated source vertex $s\in V$. Our goal is to transmit a message, which is initially known only to $s$, to all vertices of the graph by using a process where in each round an informed vertex may transmit the message to one of its uninformed neighbors. The optimization objective is to minimize the number of rounds.

Following up on several recent works, we investigate the structurally parameterized complexity of \textsc{Telephone Broadcast}. In particular, we first strengthen existing NP-hardness results by showing that the problem remains NP-complete on graphs of bounded tree-depth and also on cactus graphs which are one vertex deletion away from being path forests. Motivated by this (severe) hardness, we study several other parameterizations of the problem and obtain FPT algorithms parameterized by vertex integrity (generalizing a recent FPT algorithm parameterized by vertex cover by Fomin, Fraigniaud, and Golovach~[TCS 2024]) and by distance to clique, as well as FPT approximation algorithms parameterized by clique-cover and cluster vertex deletion. Furthermore, we obtain structural results that relate the length of the optimal broadcast protocol of a graph $G$ with its pathwidth and tree-depth. By presenting a substantial improvement over the best previously known bound for pathwidth (Aminian, Kamali, Seyed-Javadi, and Sumedha~[arXiv 2025]) we exponentially improve the approximation ratio achievable in polynomial time on graphs of bounded pathwidth from $\mathcal{O}(4^\mathrm{pw})$ to $\mathcal{O}(\mathrm{pw})$.

ABSTRACT. Imagine you are a computer scientist who enjoys attending conferences or workshops within the year. Sadly, your travel budget is limited, so you must select a subset of events you can travel to.

When you are aware of all possible events and their costs at the beginning of the year, you can select a subset of the possible events that maximizes your happiness and is within your budget.

On the other hand, if you are blind about the options, you will likely have a hard time when trying to decide if you want to register somewhere or not, and will likely regret decisions you made in the future.

These scenarios can be modeled by knapsack variants, either by an offline or an online problem. However, both scenarios are somewhat unrealistic:

Usually, you will not know the exact costs of each workshop at the beginning of the year. The online version, however, is too pessimistic, as you might already know which options there are and how much they cost roughly. At some point, you have to decide whether to register for some workshop, but then you are aware of the conference fee and the flight and hotel prices.

We model this problem within the setting of online knapsack with estimates: in the beginning, you receive a list of potential items with their estimated size as well as the accuracy of the estimates. Then, the items are revealed one by one in an online fashion with their actual size, and you need to decide whether to take one or not. In this article, we show a best-possible algorithm for each estimate accuracy delta (i.e., when each actual item size can deviate by +/- delta from the announced size) for both the simple knapsack and the simple knapsack with removability.

ABSTRACT. String diagrammatic calculi have become increasingly popular in fields such as quantum theory, circuit theory, probabilistic programming, and machine learning, where they enable resource-sensitive and compositional algebraic analysis. Traditionally, the equations of diagrammatic calculi only axiomatise exact semantic equality. However, reasoning in these domains often involves approximations rather than strict equivalences.

In this work, we develop a quantitative framework for diagrammatic calculi, where one may axiomatise notions of distance between string diagrams. Unlike similar approaches, such as the quantitative theories introduced by Mardare et al., this requires us to work in a monoidal rather than a cartesian setting. We define a suitable notion of monoidal theory, the syntactic category it freely generates, and its models, where the concept of distance is established via enrichment over a quantale. To illustrate the framework, we provide examples from probabilistic and linear systems analysis.

ABSTRACT. We study the possibility of scaling down algorithmic information quantities in tuples of correlated strings. In particular, we address a question raised by Alexander Shen: whether, for any triple of strings (a, b, c), there exists a string z such that each conditional Kolmogorov complexity (C(a|z), C(b|z), C(c|z)) is approximately half of the corresponding unconditional Kolmogorov complexity. We provide a negative answer to this question by constructing a triple (a, b, c) for which no such string z exists. Our construction is based on combinatorial properties of incidences in finite projective planes and relies on recent bounds on point-line incidences over prime fields, obtained using tools from additive combinatorics and algebraic methods (notably results by Bourgain-Katz-Tao and Stevens-De Zeeuw). As an application, we show that this impossibility yields lower bounds on the communication complexity of secret key agreement protocols in certain settings. These results reveal algebraic obstructions to efficient information exchange and highlight a separation in information-theoretic behavior between fields with and without proper subfields.

ABSTRACT. Alternating parity automata (APAs) provide a robust formalism for modelling infinite behaviours and play a central role in formal verification. Despite their widespread use, the algebraic theory underlying APAs has remained largely unexplored. In recent work, a notation for non-deterministic finite automata (NFAs) was introduced, along with a sound and complete axiomatisation of their equational theory via right-linear algebras. In this paper, we extend that line of work, in particular to the setting of infinite words. We present a dualised syntax, yielding a notation for APAs based on right-linear lattice expressions, and provide a natural axiomatisation of their equational theory with respect to the standard language model of omega-regular languages. The design of this axiomatisation is guided by the theory of fixed point logics; in fact, the completeness factors cleanly through the completeness of the linear-time mu-calculus.

ABSTRACT. A classic result of Williamson, Goemans, Mihail, and Vazirani [STOC 1993: 708--717] states that the problem of covering an uncrossable set family by a min-cost edge set admits approximation ratio 2, by a primal-dual algorithm with a reverse delete phase. Bansal, Cheriyan, Grout, and Ibrahimpur [ICALP 2023: 15:1–15:19] showed that this algorithm achieves approximation ratio 16 for a larger class of so called $\gamma$-pliable set families, that have much weaker uncrossing properties. The approximation ratio $16$ was improved to 10 by Nutov [WAOA 2024: 151-166]. Recently, Bansal stated approximation ratio 8 for $\gamma$-pliable families and an improved approximation ratio 5 for an important particular case of the family of cuts of size $<k$ of a graph, but his proof has an error. We will improve the approximation ratio to 7 for the former case and give a simple proof of approximation ratio 6 for the latter case. Our analysis is supplemented by examples showing that these approximation ratios are tight for the primal-dual algorithm.

ABSTRACT. We study the performance of mildly greedy players in $k$-coloring games, a relevant subclass of anti-coordination games. A mildly greedy player is a selfish agent who is willing to deviate from a certain strategy profile only if her payoff improves by a factor of more than $\epsilon$, for some given $\epsilon \geq 0$. In presence of mildly greedy players, stability is captured by the concept of $(1+\epsilon)$-approximate Nash equilibrium. In this paper, we first show that, for any $k$-coloring game, the $(1+\epsilon)$-approximate price of anarchy, i.e., the price of anarchy of $(1+\epsilon)$-approximate pure Nash equilibria, is at least $\frac{k-1}{(k-1)\epsilon +k}$, and that this bound is tight for any $\epsilon \geq 0$. Then, we evaluate the approximation ratio of the solutions achieved after a $(1+\epsilon)$-approximate one-round walk starting from any initial strategy profile, where a $(1+\epsilon)$-approximate one-round walk is a sequence of $(1 + \epsilon)$-approximate best-responses, one for each player. We provide a lower bound of $\min \Big \{ \frac{k-2}{k}, \frac{k-1}{(k-1)\epsilon +k} \Big \}$ on this ratio, for any $\epsilon \geq 0$ and $k \geq 5$; for the cases of $k=3$ and $k=4$, we give finer bounds depending on $\epsilon$. Our work generalizes the results known for cut games, the special case of $k$-coloring games restricted to $k=2$.

ABSTRACT. The Capacitated Vehicle Routing Problem (CVRP) is one of the most extensively studied problems in combinatorial optimization. Based on customer demand, we distinguish three variants of CVRP: unit-demand, splittable, and unsplittable. In this paper, we consider $k$-CVRP in general metrics and on general graphs, where $k$ is the vehicle capacity. All three versions are APX-hard for any fixed $k\geq3$. Assume that the approximation ratio of metric TSP is $3/2$. We present a $(5/2-\Theta(\sqrt{1/k}))$-approximation algorithm for the splittable and unit-demand cases, and a $(5/2+\ln2-\Theta(\sqrt{1/k}))$-approximation algorithm for the unsplittable case. Our ratio is better than previous results when $k$ is less than a sufficiently large value, approximately $1.7\times10^7$.

For small values of $k$, we design independent and elegant algorithms with further improvements. For the splittable and unit-demand cases, we improve the ratio from $1.792$ to $1.500$ for $k=3$, and from $1.750$ to $1.500$ for $k=4$. For the unsplittable case, we improve the ratio from $1.792$ to $1.500$ for $k=3$, from $2.051$ to $1.750$ for $k=4$, and from $2.249$ to $2.157$ for $k=5$. The ratio for $k=3$ surprisingly achieves the same value as in the splittable case. Our techniques, such as EX-ITP -- an extension of the classic ITP method, have the potential to improve algorithms for other routing problems as well.

ABSTRACT. Polylogarithmic time delineates a relevant notion of feasibility on several classical computational models such as Boolean circuits or parallel random access machines. As far as the quantum paradigm is concerned, this notion yields the complexity class fbqpolylog of functions approximable in polylogarithmic time with a quantum random access Turing machine. We introduce a quantum programming language with first-order recursive procedures, which provides the first programming language-based characterization of fbqpolylog. Each program computes a function in fbqpolylog (soundness) and, conversely, each function of this complexity class is computed by a program (completeness). We also provide a compilation strategy from programs to uniform families of quantum circuits of polylogarithmic depth and polynomial size, whose set of computed functions is known as QNC, and recover the well-known separation result fbqpolylog ⊊ QNC.

ABSTRACT. We show the existence of a fixed recurrent network capable of approximating any computable function with arbitrary precision, provided that an encoding of the function is given in the initial input. While uniform approximation over a compact domain is a well-known property of neural networks, we go further by proving that our network ensures effective uniform approximation simultaneously ensuring: - Uniform approximation in the sup-norm sense, guaranteeing precision across a compact domain; - Uniformity in the sense of computability theory (also referred to as effectivity or universality), meaning the same network works for all computable functions.

Our result is obtained constructively, using original arguments. Moreover, our construction bridges computation theory with neural network approximation, providing new insights into the fundamental connections between circuit complexity and function representation.

Furthermore, this connection extends beyond computability to complexity theory. The obtained network is efficient: if a function is computable or approximable in polynomial time in the Turing machine model, then the network requires only a polynomial number of recurrences or iterations to achieve the same level of approximation, and conversely. Moreover, the recurrent network can be assumed to be very narrow, strengthening the link our results and existing models of very deep learning, where uniform approximation properties have already been established.

ABSTRACT. Many promising quantum algorithms in economics, medical science, and material science rely on circuits that are parameterized by a large number of angles. To ensure that these algorithms are efficient, these parameterized circuits must be heavily optimized. However, most quantum circuit optimizers are not verified, so this procedure is known to be error-prone. For this reason, there is growing interest in the design of equivalence checking algorithms for parameterized quantum circuits. In this paper, we define a generalized class of parameterized circuits with arbitrary rotations and show that this problem is decidable for cyclotomic gate sets. We propose a cutoff-based procedure which reduces the problem of verifying the equivalence of parameterized quantum circuits to the problem of verifying the equivalence of finitely many parameter-free quantum circuits. Because the number of parameter-free circuits grows exponentially with the number of parameters, we also propose a probabilistic variant of the algorithm for cases when the number of parameters is intractably large. We show that our techniques extend to equivalence modulo global phase, and describe an efficient angle sampling procedure for cyclotomic gate sets.

ABSTRACT. We define generalized de Bruijn words as those words having a Burrows-Wheeler transform that is a concatenation of permutations of the alphabet. We show that generalized de Bruijn words are in 1-to-1 correspondence with Hamiltonian cycles in the generalized de Bruijn graphs introduced in the early '80s in the context of network design. When the size of the alphabet is a prime $p$, we define invertible necklaces as those whose BWT-matrix is non-singular. We show that invertible necklaces of length $n$ correspond to normal bases of the finite field $F_{p^n}$, and that they form an Abelian group isomorphic to the Reutenauer group $RG_p^n$. Using known results in abstract algebra, we can make a bridge between generalized de Bruijn words and invertible necklaces. In particular, we highlight a correspondence between binary de Bruijn words of order $d+1$, binary necklaces of length $2^{d}$ having an odd number of $1$s, invertible BWT matrices of size $2^{d}\times 2^{d}$, and normal bases of the finite field $F_{2^{2^{d}}}$.

ABSTRACT. We study how the application of injective morphisms affects the number r of equal-letter runs in the Burrows–Wheeler Transform (BWT). This parameter has emerged as a key repetitiveness measure in compressed indexing. We focus on the notion of BWT-run sensitivity after application of an injective morphism. For binary alphabets, we characterize the class of morphisms that preserve the number of BWT-runs up to a bounded additive increase, by showing that it coincides with the known class of primitivity-preserving morphisms, which are those that map primitive words to primitive words. We further prove that deciding whether a given binary morphism has bounded BWT-run sensitivity is possible in polynomial time with respect to the total length of the images of the two letters. Additionally, we explore new structural and combinatorial properties of synchronizing and recognizable morphisms. These results establish new connections between BWT-based compressibility, code theory, and symbolic dynamics.

ABSTRACT. We study automatic presentations of the structures $(\mathbb{N}; S)$, $(\mathbb{N}; E_S)$, $(\mathbb{N}; \leq)$, and their expansions by a unary predicate $U$. Here $S$ is the successor function, $E_S$ is the undirected version of $S$, and $\leq$ is the natural order. We call these structures word structures. Our goal is three-fold. First, we study the isomorphism problem for automatic word structures by focusing on the following three problems. The first problem asks to design an algorithm that, given an automatic structure $\mathcal A$, decides if $\mathcal A$ is isomorphic to $(\mathbb{N}; S)$. The second asks to design an algorithm that, given two automatic presentations of $(\mathbb{N}; S, U_1)$ and $(\mathbb{N}; S, U_2)$, where $U_1$ and $U_2$ are unary predicates, decides if these structures are isomorphic. The third problem investigates if there is an algorithm that, given two automatic presentations of $(\mathbb{N}; \leq, U_1)$ and $(\mathbb{N}; \leq, U_2)$, decides whether $U_1\cap U_2\neq \emptyset$. We show that these problems are undecidable. Next, we study intrinsic regularity of the function $S$ in the structure $Path_{\omega}=(\mathbb{N}; E_S)$. We build an automatic presentation of $Path_{\omega}$ in which $S$ is not regular. This implies that $S$ is not intrinsically regular in $Path_{\omega}$. For $U\subseteq \mathbb{N}$, let $d_U$ be the function that computes the distances between the consecutive elements of $U$. We build automatic presentations of $(\mathbb{N}; \leq, U)$ where $d_U$ can realise logarithmic, radical, intermediate, and exponential functions.

ABSTRACT. Vectors addition systems with states (VASS), or equivalently Petri nets, are arguably one of the most studied formalisms for the modeling and analysis of concurrent systems. A central decision problem for VASS is reachability: whether there exists a run from an initial configuration to a final one. This problem has been known to be decidable for over forty years, and its complexity has recently been precisely characterized. Our work concerns the reachability problem for BVASS, a branching generalization of VASS. In dimension one, the exact complexity of this problem is known. In this paper, we prove that the reachability problem for 2-dimensional BVASS is decidable. In fact, we even show that the reachability set admits a computable semilinear presentation. The decidability status of the reachability problem for BVASS remains open in higher dimensions.

ABSTRACT. Enumerating the result set of a first-order query over a relational structure of bounded degree can be done with linear preprocessing and constant delay. In this work, we extend this result towards the compressed perspective where the structure is given in a potentially highly compressed form by a straight-line program (SLP). Our main result is an algorithm that enumerates the result set of a first-order query over a structure of bounded degree that is represented by an SLP satisfying the so-called apex condition. For a fixed formula, the enumeration algorithm has constant delay and needs a preprocessing time that is linear in the size of the SLP.

ABSTRACT. A piecewise affine map is one of the simplest mathematical objects exhibiting complex dynamics. The reachability problem of piecewise affine maps is as follows: Given two vectors s, t ∈ Q^d and a piecewise affine map f: Q^d → Q^d, is there n ∈ N such that f^n(s) = t? Koiran, Cosnard, and Garzon show that the reachability problem of piecewise affine maps is undecidable even in dimension 2.

Most of the recent progress has been focused on decision procedures for one-dimensional piecewise affine maps, where the reachability problem has been shown to be decidable for some subclasses. However, the general undecidability discouraged research into positive results in arbitrary dimension.

In this work, we investigate a rich subclass of piecewise affine maps arising as Bellman operators of Markov decision processes (MDPs). We consider the reachability problem restricted to this subclass and examine its decidability in arbitrary dimensions. We establish that the reachability problem for Bellman operators is decidable in any dimension under either of the following conditions: (i) the target vector t is not the fixed point of the operator f; or (ii) the initial and target vectors s and t are comparable with respect to the componentwise order. Furthermore, we show that the reachability problem for two-dimensional Bellman operators is decidable for arbitrary s, t ∈ Q^d, in contrast to the known undecidability of reachability for general piecewise affine maps.