ABSTRACT. This talk addresses the synthesis problem of distributed monitors for concurrency properties.

ABSTRACT. Recoverable robust optimization is a popular multi-stage approach, in which it is possible to adjust a first-stage solution after the uncertain cost scenario is revealed. We consider recoverable robust optimization in combination with discrete budgeted uncertainty. In this setting, it seems plausible that many problems become $\Sigma^p_3$-complete and therefore it is impossible to find compact IP formulations of them (unless the unlikely conjecture NP $= \Sigma^p_3$ holds). Even though this seems plausible, few concrete results of this kind are known. In this paper, we fill that gap of knowledge. We consider recoverable robust optimization for the nominal problems of Sat, 3Sat, vertex cover, dominating set, set cover, hitting set, feedback vertex set, feedback arc set, uncapacitated facility location, $p$-center, $p$-median, independent set, clique, subset sum, knapsack, partition, scheduling, Hamiltonian path/cycle (directed/undirected), TSP, $k$-directed disjoint path ($k \geq 2$), and Steiner tree. We show that for each of these problems, and for each of three widely used distance measures, the recoverable robust problem becomes $\Sigma^p_3$-complete. Concretely, we show that all these problems share a certain abstract property and prove that this property implies that their robust recoverable counterpart is $\Sigma^p_3$-complete. This reveals the insight that all the above problems are $\Sigma^p_3$-complete "for the same reason". Our result extends a recent framework by Grüne and Wulf.

ABSTRACT. The low-rank matrix completion problem asks whether a given real matrix with missing values can be completed so that the resulting matrix has low rank or is close to a low-rank matrix. The completed matrix is often required to satisfy additional structural constraints, such as positive semi-definiteness or a bounded infinity norm. The problem arises in various research fields, including machine learning, statistics, and theoretical computer science, and has broad real-world applications.

This paper presents new NP-hardness results for low-rank matrix completion problems. We show that for every sufficiently large integer d and any real number $\eps \in [ 2^{-O(d)},\frac{1}{7}]$, given a partial matrix A with exposed values of magnitude at most 1 that admits a positive semi-definite completion of rank d, it is NP-hard to find a positive semi-definite matrix that agrees with each given value of A up to an additive error of at most $\eps$, even when the rank is allowed to exceed d by a multiplicative factor of $O (\frac{1}{\eps^2 \cdot \log(1/\eps)} )$. This strengthens a result of Hardt, Meka, Raghavendra, and Weitz (COLT, 2014), which applies to multiplicative factors smaller than 2 and to $\eps$ that decays polynomially in d. We establish similar NP-hardness results for the case where the completed matrix is constrained to have a bounded infinity norm (rather than be positive semi-definite), for which all previous hardness results rely on complexity assumptions related to the Unique Games Conjecture. Our proofs involve a novel notion of nearly orthonormal representations of graphs, the concept of line digraphs, and bounds on the rank of perturbed identity matrices.

ABSTRACT. We consider equilibria in multiplayer stochastic graph games with terminal-node rewards. In such games, Nash equilibria are defined assuming that each player seeks to maximise their expected payoff, ignoring their aversion or tolerance to risk. We therefore study risk-sensitive equilibria (RSEs), where the expected payoff is replaced by a risk measure. A classical risk measure in the literature is the entropic risk measure, where each player has a real valued parameter capturing their risk-averseness. We introduce the extreme risk measure, which corresponds to extreme cases of entropic risk measure, where players are either extreme optimists or extreme pessimists. Under extreme risk measure, every player is an extremist: an extreme optimist perceives their reward as the maximum payoff that can be achieved with positive probability, while an extreme pessimist expects the minimum payoff achievable with positive probability. The extreme risk measure, especially in multi-player graph based settings, is particularly relevant as they can model several real life instances such as interactions between secure systems and potential security threats, or distributed controllers in safety critical systems. We prove that RSEs defined with the extreme risk measure are guaranteed to exist when all rewards are non-negative. Furthermore, we prove that the problem of deciding whether a given game contains an RSE that generates risk measures within specified intervals is decidable and NP-complete for our extreme risk measure, and even PTIME-complete when all players are extreme optimists, while that same problem is undecidable using the entropic risk measure or even the classical expected payoff. This establishes, to our knowledge, the first decidable fragment for equilibria in simple stochastic games without restrictions on strategy types or number of players.

ABSTRACT. A subcoloring of a graph is a partition of its vertex set into subsets (called colors), each inducing a disjoint union of cliques. It is a natural generalization of the classical proper coloring, in which each color must instead induce an independent set. Similarly to proper coloring, we define the subchromatic number of a graph as the minimum integer $k$ such that it admits a subcoloring with $k$ colors, and the corresponding problem k-Subcoloring which asks whether a graph has subchromatic number at most k. In this paper, we initiate the study of the subcoloring of (unit) disk graphs. One motivation stems from the fact that disk graphs can be seen as a dense generalization of planar graphs where, intuitively, each vertex can be blown into a large clique--much like subcoloring generalizes proper coloring. Interestingly, it can be observed that every unit disk graph admits a subcoloring with at most 7 colors. We first prove that the subchromatic number can be $3$-approximated in polynomial-time in unit disk graphs. We then present several hardness results for special cases of unit disk graphs which somehow prevents the use of classical approaches for improving this result. We show in particular that 2-Subcoloring remains NP-hard in triangle-free unit disk graphs, as well as in unit disk graphs representable within a strip of bounded height. We also solve an open question of Broersma, Fomin, Nešetřil, and Woeginger (2002) by proving that 3-Subcoloring remains NP-hard in co-comparability graphs (which contain unit disk graphs representable within a strip of height \sqrt{3}/2). Finally, we prove that every n-vertex disk graph admits a subcoloring with at most O(\log^3(n)) colors and present a O(\log^2(n))-approximation algorithm for computing the subchromatic number of such graphs. This is achieved by defining a decomposition and a special type of co-comparability disk graph, called \Delta-disk graphs, which might be of independent interest.

ABSTRACT. We investigate the Dispersive Art Gallery Problem with vertex guards for a class of orthogonal polygons that reflect the properties of real-world floor plans: These office-like polygons consist of rectangular rooms and corridors. In the dispersive variant of the Art Gallery Problem, the objective is not to minimize the number of guards but to maximize the minimum distance between any two guards, called the dispersion distance.

Our main contributions are as follows. We prove that determining whether a guard set can achieve a dispersion distance of 4 in office-like polygons, where vertices are restricted to integer coordinates, is NP-complete. Additionally, we present a simple worst-case optimal algorithm that guarantees a dispersion distance of 3. Our complexity result extends to polyominoes, resolving an open question posed by Rieck and Scheffer (CGTA 2024). When vertex coordinates are unrestricted, we establish analogous results, proving that achieving a dispersion distance of 2 + epsilon is NP-hard for any epsilon > 0, while the classic Art Gallery Problem remains solvable in polynomial time for this class of polygons. Furthermore, our algorithm computes worst-case optimal solutions with a dispersion distance of 2.

On the other hand, for the more restricted class of hole-free independent office-like polygons, we propose a dynamic programming approach that computes optimal solutions. Moreover, we demonstrate that the problem is practically tractable for arbitrary orthogonal polygons. To this end, we compare solvers based on SAT, CP, and MIP formulations. Notably, SAT solvers efficiently compute optimal solutions for randomly generated instances with up to 1600 vertices in under 15 seconds.

ABSTRACT. Geometric hitting set problems, in which we seek a smallest set of points that collectively hit a given set of ranges, are ubiquitous in computational geometry. Most often, the set is discrete and is given explicitly. We propose new variants of these problems, dealing with continuous families of convex polyhedra, and show that they capture decision versions of the two-level finite adaptability problem in robust optimization. We show that these problems can be solved in strongly polynomial time when the size of the hitting/covering set and the dimension of the polyhedra and the parameter space are constant. We also show that the hitting set problem can be solved in strongly quadratic time for one-parameter families of convex polyhedra in constant dimension. This leads to new tractability results for finite adaptability that are the first ones with so-called left-hand-side uncertainty, where the underlying problem is non-linear.

ABSTRACT. A query algorithm based on homomorphism counts is a procedure to decide membership for a class of finite relational structures using only homomorphism count queries. A left query algorithm can ask the number of homomorphisms from any structure to the input structure and a right query algorithm can ask the number of homomorphisms from the input structure to any other structure. We systematically compare the expressive power of different types of left or right query algorithms, including non-adaptive query algorithms, adaptive query algorithms that can ask a bounded number of queries, and adaptive query algorithms that can ask an unbounded number of queries. We also consider query algorithms where the homomorphism counting is done over the Boolean semiring, meaning that only the existence of a homomorphism is recorded, not the precise number of them.

ABSTRACT. We study the dynamic membership problem for regular tree languages under relabeling updates: we fix an alphabet Σ and a regular tree language L over Σ (expressed, e.g., as a tree automaton), we are given a tree T with labels in Σ, and we must maintain the information of whether the tree T belongs to L while handling relabeling updates that change the labels of individual nodes in T. (The shape and size of the tree remain the same throughout.)

Our first contribution is to show that this problem admits an O(log n/ log log n) algorithm for any fixed regular tree language, improving over known algorithms that achieve O(log n). This generalizes the known O(log n/ log log n) upper bound over words, and it matches the lower bound of Ω(log n/ log log n) from dynamic membership to some word languages and from the existential marked ancestor problem.

Our second contribution is to introduce a class of regular languages, dubbed almost-commutative tree languages, and show that dynamic membership to such languages under relabeling updates can be done in constant time per update. Almost-commutative languages generalize both commutative languages and finite languages, and they are the analogue for trees of the ZG languages enjoying constant-time dynamic membership over words. Our main technical contribution is to show that this class is conditionally optimal when we assume that the alphabet features a neutral letter, i.e., a letter e that has no effect on membership to the language. More precisely, we show that any regular tree language with a neutral letter which is not almost-commutative cannot be maintained in constant time under the assumption that prefix-U1 problem from [3] also does not admit a constant-time algorithm.

ABSTRACT. In this paper, we study the query complexity of Boolean functions in the presence of uncertainty, motivated by parallel computation with an unlimited number of processors where inputs are allowed to be unknown. We allow each query to produce three results: zero, one, or unknown. The output could also be: zero, one, or unknown, with the constraint that we should output ``unknown'' only when we cannot determine the answer from the revealed input bits. Such an extension of a Boolean function is called its \emph{hazard-free} extension.

\begin{itemize} \item We prove an analogue of Huang's celebrated sensitivity theorem [Annals of Mathematics, 2019] in our model of query complexity with uncertainty. \item We show that the deterministic query complexity of the hazard-free extension of a Boolean function is at most quadratic in its randomized query complexity and quartic in its quantum query complexity, improving upon the best-known bounds in the Boolean world. \item We exhibit an exponential gap between the smallest depth (size) of decision trees computing a Boolean function, and those computing its hazard-free extension. \item We present general methods to convert decision trees for Boolean functions to those for their hazard-free counterparts, and show optimality of this construction. We also parameterize this result by the maximum number of unknown values in the input. \item We show lower bounds on size complexity of decision trees for hazard-free extensions of Boolean functions in terms of the number of prime implicants and prime implicates of the underlying Boolean function. \end{itemize}

ABSTRACT. We construct a probabilistic finite automaton (PFA) with 7 states and an input alphabet of 5 symbols for which the PFA Emptiness Problem is undecidable. The only input for the decision problem is the starting distribution. For the proof, we use reductions from special instances of the Post Correspondence Problem. We also consider some variations: The input alphabet of the PFA can be restricted to a binary alphabet at the expense of a larger number of states. If we allow a rational output value for each state instead of a yes-no acceptance decision, the number of states can even be reduced to 6.

ABSTRACT. We propose Permutation Deterministic Register Automata (pDRAs), a deterministic register automaton model where we allow permutations of registers in transitions. The model enables minimal canonical representations, and pDRAs can be tested for equivalence in polynomial time. The complexity of minimization is between GI (the complexity of graph isomorphism) and NP. We then introduce a subclass of pDRAs, called register automata with fixed permutation policy, where the register permutation discipline is stipulated globally. This class generalizes the model proposed by Benedikt, Ley, and Puppis in 2010, and we show that it also admits minimal and canonical representations based on a finite-index word equivalence relation. As an application, we show that for any regular data language L, the minimal register automaton with fixed permutation policy recognizing L can be actively learned in polynomial time using oracles for membership, equivalence, and data-memorability queries. We show that all the oracles can be implemented in polynomial time, and so this yields a polynomial time minimization algorithm.

ABSTRACT. As the notion of similarity of languages, we consider the edit distance between languages L, L', i.e., the minimal number of edits necessary to transform any word from L to some word from L' and vice versa.

In this paper we address two problems: minimization up to a predetermined edit distance given in the input, and minimization up to a bounded edit distance, in which there has to be an upper bound on the number of edits, but it is not specified. We show the first problem to be PSPACE-complete and that the second problem is in Sigma_2^p, and both NP-hard and coNP-hard. We also establish maximal subclasses of DFA over which minimization up to a bounded edit distance can be performed in polynomial time.

Additionally, we provide a succinct overview of alternative metrics for assessing language similarity.

ABSTRACT. We study the complexity of computing second solutions for NP search problems, i. e., given a problem instance x and a valid solution y, we have to find another valid solution y'.

Our main result shows that for typical NP decision problems, the complexity of computing second solutions is completely determined by the choice of the type of solution, but independent of the underlying decision problem. More precisely, for every 1-paddable X in NP, different choices of the type of solution lead to different second solution problems, which altogether have the same degree structure as the entire class of NP search problems (FNP). In fact, each degree of difficulty within FNP does occur as a second solution problem for X. This proves that typical NP decision problems have no intrinsic complexity w. r. t. the search for a second solution, but only the specification of the type of solution determines this complexity. This explains the empirical observation that the difficulty of computing second solutions strongly depends on the formulation of the problem.

Moreover, we show that the complexities of a search problem and its second solution variant are independent in the following sense: For all search problems A and B representing two degrees of difficulty, there exists a search problem C such that 1. C is as difficult as A and 2. computing second solutions for C is as difficult as B.

ABSTRACT. For a fixed graph H, the function #IndSub(H,*) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interpretation. Linear combinations of such functions are called graph motif parameters and have recently received significant attention in counting complexity after a seminal paper by Curticapean, Dell and Marx (STOC'17). We show that, among linear combinations of functions #IndSub(H,*) involving only graphs H without isolated vertices, precisely those with positive integer coefficients maintain a combinatorial interpretation. It is important to note that graph motif parameters can be nonnegative for all inputs G, even when some coefficients are negative.

Formally, we show that evaluating any graph motif parameter with a negative coefficient is impossible in an oracle variant of #P, where an implicit graph is accessed by oracle queries. Our proof follows the classification of the relativizing closure properties of #P by Hertrampf, Vollmer, and Wagner (SCT'95) and the framework developed by Ikenmeyer and Pak (STOC'22), but our application of the required Ramsey theorem turns out to be more subtle, as graphs do not have the required Ramsey property.

Our techniques generalize from graphs to relational structures, including colored graphs. Vastly generalizing this, we introduce motif parameters over categories that count occurrences of sub-objects in the category. We then prove a general dichotomy theorem that characterizes which such parameters have a combinatorial interpretation. Using known results in Ramsey theory for categories, we obtain a dichotomy for motif parameters of finite vector spaces as well as parameter sets.

ABSTRACT. There is a large body of work that shows how to leverage lower bound techniques for circuit classes to obtain satisfiability algorithms that run in better than brute-force time[Williams'14, PPZ'97]. For circuits with threshold gates, there are several such algorithms based on either probabilistic representations by low-degree polynomials, which allow for the use of fast polynomial evaluation algorithms, or low rank, which allows for an efficient reduction to rectangular matrix multiplication.

In this paper, we show how to use probabilistic rank, which generalizes both these notions, to obtain satisfiability algorithms for constant-depth circuits with modular counting gates and a single layer of degree-3 polynomial threshold functions.

Even for the special case of a single degree-3 polynomial threshold function, it is not clear how to use either of the above two strategies to get a non-trivial satisfiability algorithm. The best known algorithm in this case previously was based on memoization and yields worse guarantees than our algorithm.

ABSTRACT. In this work, we investigate the computational aspects of asynchronous cellular automata (ACAs), a modification of cellular automata in which cells update independently, following an asynchronous schedule. We introduce flip automata networks (FANs), a simple modification of automata networks that remain robust under any asynchronous update schedule. By using FANs as a middleman, we show that asynchronous automata can efficiently simulate their synchronous counterparts with a linear memory overhead, which improves upon the previously established quadratic bound. Additionally, we address the universality gap for (a)synchronous cellular automata---the boundary separating universal and non-universal automata, which is still not fully understood. We tighten this boundary by proving that all one-way asynchronous automata lack universal computational power. Conversely, we establish the existence of a universal asynchronous 6-state first-neighbor automaton in one dimension and a 3-state von Neumann automaton in two dimensions, which represent the smallest known universal constructions to date.

ABSTRACT. Regular transductions over finite words have linear input-to-output growth. This class of transductions enjoys many characterizations, such as transductions computable by two-way transducers as well as transductions definable in MSO (in the sense of Courcelle). Recently, regular transductions have been extended by Bojańczyk to polyregular transductions, which have polynomial growth, and are characterized by pebble transducers and MSO interpretations. Another class of interest is that of transductions defined by streaming string transducers or marble transducers, which have exponential growth and are incomparable with polyregular transductions.

In this paper, we consider MSO set interpretations (MSOSI) over finite words, that were introduced by Colcombet and Loeding. MSOSI are a natural candidate for the class of “regular transductions with exponential growth”, and are rather well-behaved. However MSOSI lack, for now, two desirable properties that regular and polyregular transductions have. The first property is to have a automata description. This property is closely related to a second property, that of being regularity preserving, meaning preserving regular languages under inverse image.

We first show that if MSOSI are (effectively) regularity preserving then any automatic ω-word has a decidable MSO theory, an almost 20 years old conjecture of Bárány.

Our main contribution is the introduction of a class of transductions of exponential growth, which we call lexicographic transductions. We provide three different presentations for this class: first, as the closure of simple transductions (recognizable transductions) under a single operator called maplex; second, as a syntactic fragment of MSOSI (but the regular languages are given by automata instead of formulas); and third, we give an automaton based model called nested marble transducers, which generalize both marble transducers and pebble transducers. We show that this class enjoys many nice properties including being regularity preserving.

ABSTRACT. Sampling a non degenerate (that is, invertible) square matrix over a finite field is easy, draw a random square matrix and discard if the determinant is zero. We address the problem in higher dimensions, and sample non degenerate boundary format tensors, which generalise square matrices. Testing degeneracy is conjectured to be hard in more than two dimensions, precluding the ``draw a random tensor and discard if degenerate'' recipe. The difficulty is in computing hyperdeterminants, higher dimensional analogues of determinants. Instead, we start with a structured random non-degenerate tensor and scramble it by infusing more randomness while still preserving non degeneracy. We propose two kinds of scrambling. The first is multiplication in each dimension by random invertible matrices, which preserves dimension and format. Assuming pseudo randomness of this action, which also underlies tensor isomorphism based cryptography, our samples are computationally indistinguishable from uniform non degenerate tensors. The second scrambling employs tensor convolution (that generalises multiplication by matrices) and can increase dimension. Inspired by hyperdeterminant multiplicativity, we devise a recursive sampler that uses tensor convolution to reduce the problem from arbitrary to three dimensions.

Our sampling is a candidate solution for drawing public keys in tensor isomorphism based cryptography, since non-degenerate tensors elude recent weak key attacks targeting public key tensors either containing geometric structures such as ``triangles" or being deficient in tensor rank. To accommodate our sampling, tensor isomorphism based schemes need to be instantiated in boundary formats such as (2k+1) x(k+1)x(k+1), away from the more familiar k x k x k cubic formats. Our sampling (along with the recent tensor trapdoor one-way functions) makes an enticing case to transition tensor isomorphism cryptography to boundary formats tensors, which are true analogues of square matrices.