Search

In dial-a-ride systems involving autonomous vehicles circulating along a circuit, a fleet of vehicles must serve clients who request rides between stations of the circuit such that the total number of pickup and drop-off operations is minimized. In this paper, we focus on a unitary variant where each client requests a single place in the vehicles and all the clients must be served within a single tour of the circuit. Such unitary variant induces a combinatorial optimization problem for which we introduce a nontrivial special case that is polynomially solvable when the capacity of each vehicle is at most 2 but it is NP-Hard otherwise. We also study the polytope associated with the solutions to this problem. We introduce new families of valid inequalities and give necessary and sufficient conditions under which they are facet-defining. Based on these inequalities, we devise an efficient branch-and-cut algorithm that outperforms the state-of-the-art commercial solvers.

International audience; This paper proposes the first implementation of a self-stabilizing regular register emulated by n servers that is tolerant to both Mobile Byzantine Agents and transient failures in a round-free synchronous model. Differently from existing Mobile Byzantine Tolerant register implementations, this paper considers a weaker model where: (i) the computation of the servers is decoupled from the movements of the Byzantine agents, i.e., movements may happen before, concurrently, or after the generation or the delivery of a message, and (ii) servers are not aware of their failure state i.e., they do not know if and when they have been corrupted by a Mobile Byzantine agent. The proposed protocol tolerates (i) any finite number of transient failures, and (ii) up to f Mobile Byzantine agents. In addition, our implementation uses bounded timestamps from the domain and it is optimal with respect to the number of servers needed to tolerate f Mobile Byzantine agents in the given model (i.e., when , and when , where Δ represents the period at which the Byzantine agents move and δ is the upper bound on the communication latency).

The hard-sphere model is one of the most extensively studied models in statistical physics. It describes the continuous distribution of spherical particles, governed by hard-core interactions. An important quantity of this model is the normalizing factor of this distribution, called the partition function. We propose a Markov chain Monte Carlo algorithm for approximating the grand-canonical partition function of the hard-sphere model in d dimensions. Up to a fugacity of λ < e/2^d, the runtime of our algorithm is polynomial in the volume of the system. This covers the entire known real-valued regime for the uniqueness of the Gibbs measure. Key to our approach is to define a discretization that closely approximates the partition function of the continuous model. This results in a discrete hard-core instance that is exponential in the size of the initial hard-sphere model. Our approximation bound follows directly from the correlation decay threshold of an infinite regular tree with degree equal to the maximum degree of our discretization. To cope with the exponential blow-up of the discrete instance we use clique dynamics, a Markov chain that was recently introduced in the setting of abstract polymer models. We prove rapid mixing of clique dynamics up to the tree threshold of the univariate hard-core model. This is achieved by relating clique dynamics to block dynamics and adapting the spectral expansion method, which was recently used to bound the mixing time of Glauber dynamics within the same parameter regime., LIPIcs, Vol. 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pages 66:1-66:15

We discuss the notion of a dense cluster with respect to the information distance and prove that all such clusters have an extractable core that represents the mutual information shared by the objects in the cluster., 12 pages; 3 figures. A version of this paper is accepted for publication in the Theoretical Computer Science journal

The standard model of quantum circuits assumes operations are applied in a fixed sequential "causal" order. In recent years, the possibility of relaxing this constraint to obtain causally indefinite computations has received significant attention. The quantum switch, for example, uses a quantum system to coherently control the order of operations. Several ad hoc computational and information-theoretical advantages have been demonstrated, raising questions as to whether advantages can be obtained in a more unified complexity theoretic framework. In this paper, we approach this problem by studying the query complexity of Boolean functions under general higher order quantum computations. To this end, we generalise the framework of query complexity from quantum circuits to quantum supermaps to compare different models on an equal footing. We show that the recently introduced class of quantum circuits with quantum control of causal order cannot lead to any reduction in query complexity, and that any potential advantage arising from causally indefinite supermaps can be bounded by the polynomial method, as is the case with quantum circuits. Nevertheless, we find some functions for which the minimum error with which they can be computed using two queries is strictly lower when exploiting causally indefinite supermaps., Comment: 6+11 pages

Holonomic equations are recursive equations which allow computingefficiently numbers of combinatoric objects. R{\'e}my showed that theholonomic equation associated with binary trees yields an efficientlinear random generator of binary trees. I extend this paradigm toMotzkin trees and Schr{\"o}der trees and show that despite slightdifferences my algorithm that generates random Schr{\"o}der trees has linearexpected complexity and my algorithm that generates Motzkin trees is inO(n) expected complexity, only if we can implement a specific oraclewith a O(1) complexity. For Motzkin trees, I propose a solution whichworks well for realistic values (up to size ten millions) and yields anefficient algorithm.

Whittle index is a generalization of Gittins index that provides very efficient allocation rules for restless multi-armed bandits. In this work, we develop an algorithm to test the indexability and compute the Whittle indices of any finite-state restless bandit arm. This algorithm works in the discounted and non-discounted cases, and can compute Gittins index. Our algorithm builds on three tools: (1) a careful characterization of Whittle index that allows one to compute recursively the kth smallest index from the $(k - 1)$th smallest, and to test indexability, (2) the use of the Sherman-Morrison formula to make this recursive computation efficient, and (3) a sporadic use of the fastest matrix inversion and multiplication methods to obtain a subcubic complexity. We show that an efficient use of the Sherman-Morrison formula leads to an algorithm that computes Whittle index in $(2/3)n^3 + o(n^3)$ arithmetic operations, where $n$ is the number of states of the arm. The careful use of fast matrix multiplication leads to the first subcubic algorithm to compute Whittle or Gittins index: By using the current fastest matrix multiplication, the theoretical complexity of our algorithm is O(n^2.5286 ). We also develop an efficient implementation of our algorithm that can compute indices of Markov chains with several thousands of states in less than a few seconds., Mathematical Methods of Operations Research, 2023

We study qualitative properties of two-dimensional freezing cellular automata with a binary state set initialized on a random configuration. If the automaton is also monotone, the setting is equivalent to bootstrap percolation. We explore the extent to which monotonicity constrains the possible asymptotic dynamics by proving two results that do not hold in the subclass of monotone automata. First, it is undecidable whether the automaton almost surely fills the space when initialized on a Bernoulli random configuration with density $p$, for some/all $0 < p < 1$. Second, there exists an automaton whose space-filling property depends on $p$ in a non-monotone way., 18 pages, 3 figures

Sparse direct solvers using Block Low-Rank compression have been proven efficient to solve problems arising in many real-life applications. Improving those solvers is crucial for being able to 1) solve larger problems and 2) speed up computations. A main characteristic of a sparse direct solver using low-rank compression is when compression is performed. There are two distinct approaches: (1) all blocks are compressed before starting the factorization, which reduces the memory as much as possible, or (2) each block is compressed as late as possible, which usually leads to better speedup. The objective of this paper is to design a composite approach, to speedup computations while staying under a given memory limit. This should allow to solve large problems that cannot be solved with Approach 2 while reducing the execution time compared to Approach 1.We propose a memory-aware strategy where each block can be compressed either at the beginning or as late as possible. We first consider the problem of choosing when to compress each block, under the assumption that all information on blocks is perfectly known, i.e., memory requirement and execution time of a block when compressed or not. We show that this problem is a variant of the NP-complete Knapsack problem, and adapt an existing 2-approximation algorithm for our problem. Unfortunately, the required information on blocks depends on numerical properties and in practice cannot be known in advance. We thus introduce models to estimate those values. Experiments on the PaStiX solver demonstrate that our new approach can achieve an excellent trade-off between memory consumption and computational cost. For instance on matrix Geo1438, Approach 2 uses three times as much memory as Approach 1 while being three times faster. Our new approach leads to an execution time only 30% larger than Approach 2 when given a memory 30% larger than the one needed by Approach 1., Les solveurs directs creux utilisant de la compression low-rank ont montré leur efficacité pour résoudre de grands systèmes. Les améliorer permetde 1) résoudre de plus grands problèmes et 2) accélérer la résolution. Une caractéristique principale de ces solveurs est quand la compression est réalisée. Il existe deux approches: (1) tous les blocs sont compressés avant le début de la factorisation, ce qui minimise la consommation mémoire, ou (2) chaque bloc est compressé au plus tard, ce qui permet d’avoir de meilleures performances. L’objectif de cet article est de proposer une approche intermédiaire, qui accélère les calculs au maximum tout en restant en dessous d’une limite mémoire donnée. Cela devrait permettre de résoudre de grands problèmes que l’approche 2 ne peut pas résoudre ou de réduire le temps d’exécution de l’approche 1. Nous proposonsune stratégie memory-aware où chaque bloc peut ˆêtre compressé au début ou au plus tard. Nous commençons par considérer le problème où toutes les informations (consommation mémoire et temps d’exécution en version compressée ou non) sont parfaitement connues. Nous montrons que ce problème est une variante du problème NP-complet Knapsack et adaptons une 2-approximation pour notre problème. Malheureusement, toutes ces informations dépendent de propriétés numériques et ne sont pas connues `a l’avance. Des modèles sont donc introduits afin d’estimer ces valeurs. Des expérimentations avec le solveur PaStiX montrent que notre approche permet d’avoir un excellent compromis entre consommation mémoire et temps d’exécution. Par exemple, pour la matrice Geo1438, l’approche 2 utilise trois fois plus de mémoire que l’approche 1, qui est trois fois plus lente. Notre nouvelle méthode permet d’obtenir à la fois un temps d’exécution seulement 30% supérieur à celui de l’approche 2 tout en ayant une consommation mémoire seulement supérieure de 30% à celle de l’approche 1.

We show that simple modifications to van der Hoeven's forward and inverse truncated Fourier transforms allow the algorithms to be performed in-place, and with only a linear overhead in complexity.

International audience; Aged macular degeneration (AMD) leads to a progressive decline in visual acuity until reaching blindness. It is considered as an irreversible pathology where an early diagnosis remains crucial. However, the lack of ophthalmologists, the permanent increase in elderly people, and their limited mobility involves a delay in AMD diagnosis. In this paper, we propose an automated method for AMD screening. The proposed processing pipeline consists in applying the well-known Radon transform to the macula region in order to model the AMD lesions even with a moderate quality of smartphone-captured fundus images. Thereby, the relevant features are carefully selected, related to the main proprieties of drusens, and then provided to an SVM classifer. The implementation of the method into a smartphone associated to a fundus image capturing device leads to a mobile CAD system that performs higher performance AMD screening. Within this framework and to achieve a real-time implementation, an optimization approach is suggested in order to reduce the processing workload. The evaluation of our method is carried out through the three public STARE, REFUGE, and RFMiD databases. A 4-fold cross-validation approach is used to evaluate the method performance where accuracies of 100%, 95.2%, and 94.3% are respectively obtained with STARE, REFUGE, and RFMiD databases. Comparisons with the state-of-the-art methods in the literature are done. Thereafter, the robustness of the proposed method was evaluated and proved. We note that 100% accuracy was preserved despite the use of degraded quality fundus images as noisy and blurred. Moreover, the propounded method was implemented in S7-Edge and S9 Smartphone devices, where the execution times of 19 and 15 milliseconds were respectively achieved, which proves the AMD real-time detection. Taking advantage of its mobility, cost-efective, detection performance, andreduced execution time, our proposed method seems a good solution for real-time AMD screening on mobile devices.

Discrete Differential Equations (DDEs) are functional equations that relate polynomially a power series $F(t,u)$ in $t$ with polynomial coefficients in a "catalytic" variable $u$ and the specializations, say at $u=1$, of $F(t,u)$ and of some of its partial derivatives in $u$. DDEs occur frequently in combinatorics, especially in map enumeration. If a DDE is of fixed-point type then its solution $F(t,u)$ is unique, and a general result by Popescu (1986) implies that $F(t,u)$ is an algebraic power series. Constructive proofs of algebraicity for solutions of fixed-point type DDEs were proposed by Bousquet-M\'elou and Jehanne (2006). Bostan et. al (2022) initiated a systematic algorithmic study of such DDEs of order 1. We generalize this study to DDEs of arbitrary order. First, we propose nontrivial extensions of algorithms based on polynomial elimination and on the guess-and-prove paradigm. Second, we design two brand-new algorithms that exploit the special structure of the underlying polynomial systems. Last, but not least, we report on implementations that are able to solve highly challenging DDEs with a combinatorial origin., Comment: 11 pages, revised version

This paper presents a new abstract method for proving lower bounds in computational complexity. Based on the notion of topological and measurable entropy for dynamical systems, it is shown to generalise three previous lower bounds results from the literature in algebraic complexity. We use it to prove that maxflow, a Ptime complete problem, is not computable in polylogarithmic time on parallel random access machines (prams) working with real numbers. This improves, albeit slightly, on a result of Mulmuley since the class of machines considered extends the class “prams without bit operations”, making more precise the relationship between Mulmuley’s result and similar lower bounds on real prams.More importantly, we show our method captures previous lower bounds results from the literature, thus providing a unifying framework for "topological" proofs of lower bounds: Steele and Yao’s lower bounds for algebraic decision trees, Ben-Or’s lower bounds for algebraic computation trees, Cucker’s proof that NC is not equal to Ptime in the real case, and Mulmuley’s lower bounds for “prams without bit operations”.

Our main result is a succinct counterpoint to Courcelle's meta-theorem as follows: every arborescent monadic second-order (MSO) property is either NP-hard or coNP-hard over graphs given by succinct representations. Succint representations are Boolean circuits computing the adjacency relation. Arborescent properties are those which have infinitely many models and countermodels with bounded treewidth. We actually prove this result in the terminology of automata network, which is a generalization of finite cellular automata over arbitrary graphs. This model arose from the biological modelization of neural networks and gene regulation networks. Our result states that every arborescent MSO property on the transition graph of automata networks is either NP-hard or coNP-hard. Moreover, we explore what happens when the arborescence condition is dropped and show that, under a reasonable complexity assumption, the previous dichotomy fails, even for questions expressible in first-order logic.

12th International Symposium on Parameterized and Exact Computation (IPEC 2017); International audience; Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Γk. A graph class G has the SQGC property if every graph G ∈ G has treewidth O(bcg(G)c) for some 1 ≤ c < 2. The SQGC property is important for algo- rithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a general family of graph classes that satisfy the SQGC property and includes bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for several intersection graph classes of 2-dimensional geometrical objects.

Finding communities in the form of cohesive subgraphs is a fundamental problem in network analysis. In domains that model networks as undirected graphs, communities are generally associated with dense subgraphs, and many community models have been proposed. Maximal cliques are arguably the most widely studied among such models, with early works dating back to the ’60s, and a continuous stream of research up to the present. In domains that model networks as directed graphs, several approaches for community detection have been proposed, but there seems to be no clear model of cohesive subgraph, i.e., of what a community should look like. We extend the fundamental model of clique to directed graphs, adding the natural constraint of strong connectivity within the clique. We consider in this paper the problem of listing all maximal strongly connected cliques in a directed graph. We first investigate the combinatorial properties of strongly connected cliques and use them to prove that every n -vertex directed graph has at most 3 n / 3 maximal strongly connected cliques. We then exploit these properties to produce the first algorithms with polynomial delay for enumerating maximal strongly connected cliques: a first algorithm with polynomial delay and exponential space usage, and a second one, based on reverse-search, with higher (still polynomial) delay but which uses linear space. 1

Genome Rearrangements are events that affect large stretches of genomes during evolution. Many mathematical models have been used to estimate the evolutionary distance between two genomes based on genome rearrangements. However, most of them focused on the (order of the) genes of a genome, disregarding other important elements in it. Recently, researchers have shown that considering regions between each pair of genes, called intergenic regions, can enhance distance estimation in realistic data. Two of the most studied genome rearrangements are the reversal, which inverts a sequence of genes, and the transposition, which occurs when two adjacent gene sequences swap their positions inside the genome. In this work, we study the transposition distance between two genomes, but we also consider intergenic regions, a problem we name Sorting by Intergenic Transpositions. We show that this problem is NP-hard and propose two approximation algorithms, with factors 3.5 and 2.5, considering two distinct definitions for the problem. We also investigate the signed reversal and transposition distance between two genomes considering their intergenic regions. This second problem is called Sorting by Signed Intergenic Reversals and Intergenic Transpositions. We show that this problem is NP-hard and develop two approximation algorithms, with factors 3 and 2.5. We check how these algorithms behave when assigning weights for genome rearrangements. Finally, we implemented all these algorithms and tested them on real and simulated data.

Computing persistent homology using Gaussian kernels is useful in the domains of topological data analysis and machine learning as shown by Phillips, Wang and Zheng [SoCG 2015]. However, contrary to the case of computing persistent homology using the Euclidean distance or even the $k$-distance, it is not known how to compute the persistent homology of high dimensional data using Gaussian kernels. In this paper, we consider a power distance version of the Gaussian kernel distance (GKPD) given by Phillips, Wang and Zheng, and show that the persistent homology of the \v{C}ech filtration of $P$ computed using the GKPD is approximately preserved. For datasets in $d$-dimensional Euclidean space, under a relative error bound of $\varepsilon \in [0,1]$, we obtain a dimensionality of $(i)$ $O(\varepsilon^{-2}\log^2 n)$ for $n$-point datasets and $(ii)$ $O(D\varepsilon^{-2}\log (Dr/\varepsilon))$ for datasets having diameter $r$ (up to a scaling factor). We use two main ingredients. The first one is a new decomposition of the squared radii of \v{C}ech simplices using the kernel power distance, in terms of the pairwise GKPDs between the vertices, which we state and prove. The second one is the Random Fourier Features (RFF) map of Rahimi and Recht [NeurIPS 2007], as used by Chen and Phillips [ALT 2017].

Based on work on realisability models for linear logic, the author recently proposed a new approach of implicit computational complexity. He showed how to characterise in this way a hierarchy of sub-linear space non-deterministic complexity classes by means of group actions. These classes, defined by means of two-way non-deterministic automata, range from regular languages to NLogspace (non-deterministic logarithmic space).In the present paper, we extend those results in two directions. First, we show how the same techniques can be used to characterise the sub-linear space complexity classes defined by both deterministic and probabilistic two-way multi-head automata. We thus obtain characterisations of deterministic complexity classes between regular languages and Logspace, as well as a hierarchy of probabilistic classes between stochastic languages and PLogspace (unbounded error probabilistic logarithmic space). Second, we exhibit a monoid action capturing polynomial time computation based on pushdown machines, characterising both Ptime and PPtime (unbounded error probabilistic polynomial time).

We investigate the parameterized complexity of several problems formalizing cluster identification in graphs. In other words we ask whether a graph contains a large enough and sufficiently connected subgraph. We study here three relaxations of Clique: s-Club and s-Clique, in which the relaxation is focused on the distances in respectively the cluster and the original graph, and γ-Complete Subgraph in which the relaxation is made on the minimal degree in the cluster. As these three problems are known to be NP-hard, we study here their parameterized complexities. We prove that s-Club and s-Clique are NP-hard even restricted to graphs of degeneracy ≤ 3 whenever s ≥ 3, and to graphs of degeneracy ≤ 2 whenever s ≥ 5, which is a strictly stronger result than its W[1]-hardness parameterized by the degeneracy. We also obtain that these problems are solvable in polynomial time on graphs of degeneracy 1. Concerning γ-Complete Subgraph, we prove that it is W[1]-hard parameterized by both the degeneracy, which implies the W[1]-hardness parameterized by the number of vertices in the γ-complete-subgraph, and the number of elements outside the γ-complete subgraph.

A subset of NP is said to have a dichotomy if it contains problem that are either solvable in P-time or NP-complete. The class of finite Constraint Satisfaction Problems (CSP) is a well-known subset of NP that follows such a dichotomy. The complexity class NP does not have a dichotomy unless P = NP. For both of these classes there exist logics that are associated with them. -- NP is captured by Existential Second-Order (ESO) logic by Fagin's theorem, i.e., a problem is in NP if and only if it is expressible by an ESO sentence.-- CSP is a subset of Feder and Vardi's logic, Monotone Monadic Strict NP without inequalities (MMSNP), and for every MMSNP sentence there exists a P-time equivalent CSP problem. This implies that ESO does not have a dichotomy as well as NP, and that MMSNP has a dichotomy as well as CSP. The main objective of this thesis is to study subsets of NP that strictly contain CSP or MMSNP with respect to the dichotomy existence.Feder and Vardi proved that if we omit one of the three properties that define MMSNP, namely being monotone, monadic or omitting inequalities, then the resulting logic does not have a dichotomy. As their proofs remain sketchy at times, we revisit these results and provide detailed proofs. Guarded Monotone Strict NP (GMSNP) is a known extension of MMSNP that is obtained by relaxing the "monadic" restriction of MMSNP. We define similarly a new logic that is called MMSNP with Guarded inequalities, relaxing the restriction of being "without inequalities". We prove that it is strictly more expressive than MMSNP and that it also has a dichotomy.There is a logic MMSNP₂ that extends MMSNP in the same way as MSO₂ extends Monadic Second-Order (MSO) logic. It is known that MMSNP₂ is a fragment of GMSNP and that these two classes either both have a dichotomy or both have not. We revisit this result and strengthen it by proving that, with respect to having a dichotomy, without loss of generality, one can consider only MMSNP₂ problems over one-element signatures, instead of GMSNP problems over arbitrary finite signatures.We seek to prove the existence of a dichotomy for MMSNP₂ by finding, for every MMSNP₂ problem, a P-time equivalent MMSNP problem. We face some obstacles to build such an equivalence. However, if we allow MMSNP sentences to consist of countably many negated conjuncts, then we prove that such an equivalence exists. Moreover, the corresponding infinite MMSNP sentence has a property of being "regular". This regular property means that, in some sense, this sentence is still finite. It is known that regular MMSNP problems can be expressed by CSP on omega-categorical templates. Also, there is an algebraic dichotomy characterisation for omega-categorical CSPs that describe MMSNP problems. If one manages to extend this algebraic characterisation onto regular MMSNP, then our result would provide an algebraic dichotomy for MMSNP₂.Another potential way to prove the existence of a dichotomy for MMSNP₂ is to mimic the proof of Feder and Vardi for MMSNP. That is, by finding a P-time equivalent CSP problem. The most difficult part there is to reduce a given input structure to a structure of sufficiently large girth. For MMSNP and CSP, it is done using expanders, i.e., structures, where the distribution of tuples is close to a uniform distribution. We study this approach with respect to MMSNP₂ and point out the main obstacles.We also consider an extension of CSP: the Matrix Partition (MP) problems class. We study it from several perspectives. It is well-known that CSP over an arbitrary finite signature has a dichotomy if and only if CSP on directed graphs has a dichotomy. Motivated by this result, we consider MP problems over arbitrary finite signatures and show that they have a dichotomy if and only if MP problems over one-element signatures have a dichotomy, similarly to our result for MMSNP₂. Another perspective is to characterise MP problems with respect to being definable in First-Order (FO) logic. For CSP, a problem is FO-definable if and only if it has a finitary duality, i.e., a finite family of digraphs such that an input digraph is accepted by the CSP if and only if no digraph from the family is homomorphically mapped to the input one. There have already been some attempts to classify Matrix Partition problems in terms of having finitely many minimal obstructions, i.e., an input graph is accepted by the MP problem if and only if it does not contain an induced subgraph from a given finite family. We manage to show that, for MP problems, these two notions are the same. The third perspective is to find a logic that would be related to MP in a similar way as MMSNP is related to CSP. We introduce, as a potential candidate, a logic obtained from MMSNP by relaxing the "monotone" restriction, and show that it contains MP. However, it is not known how to show the equivalence. At last, we study the notion of "polymorphism" for MP problems. We do it in order to consider the algebraic dichotomy characterisation for finite CSP and see if there is some potential to consider polymorphisms for MP problems. In the case of CSP, a structure has a non-trivial polymorphism if and only if the corresponding CSP is P-time solvable. We manage to provide an MP problem that has only trivial polymorphisms and that is P-time solvable. This means that, for MP problems, the existence of an algebraic characterisation is unlikely.In an independent chapter, we investigate the Maximum Cut (maxcut) problem. Although being NP-complete in general, its complexity becomes unknown if we consider only unit interval graphs in the input. Knowing that maxcut is NP-complete on interval graphs, we approach as close as possible to unit interval graphs by proving that it remains NP-complete even if we are allowed to operate with intervals of only two different lengths.; On dit d'un sous-ensemble de NP qu'il présente une dichotomie s'il contient des problèmes qui sont soit résolubles en temps polynomial (dans Ptime), soit difficiles (NP-complets). La classe des problèmes de satisfaction de contraintes (CSP) finis est un sous-ensemble bien connu de NP qui présente une telle dichotomie. La classe de complexité NP n'a pas de dichotomie à moins que P = NP. Pour ces deux classes, il existe des logiques qui leur sont associées. -- NP est capturé par la logique Existentielle du second ordre (ESO) par le théorème de Fagin, c'est-à-dire qu'un problème est dans NP si et seulement s'il est exprimable par une formule ESO.-- CSP est un sous-ensemble de la logique de Feder et Vardi, le fragment monotone, monadique et sans inégalités de SNP, lui-même un fragment syntaxique de ESO (MMSNP); et, pour chaque formule de MMSNP, il existe un problème CSP équivalent via des réductions polynomiales.Ceci implique que la logique ESO, tout comme NP, n'a pas de dichotomie, à contraster avec le fait que MMSNP a une dichotomie tout comme CSP. L'objectif principal de cette thèse est d'étudier les propriétés de dichotomie de sous-ensembles de NP qui contiennent strictement CSP ou MMSNP.Feder et Vardi ont prouvé que si nous omettons une des trois propriétés qui définissent MMSNP, à savoir être monotone, monadique ou omettre les inégalités, alors la logique résultante n'a pas de dichotomie. Comme leurs preuves restent parfois sommaires, nous revisitons ces résultats et fournissons des preuves détaillées. Le fragment guardé et monotone de SNP (GMSNP) est une extension connue de MMSNP qui est obtenue en relâchant la restriction "monadique" de MMSNP. Nous définissons de manière similaire une nouvelle logique appelée MMSNP avec des inégalités gardées, en relâchant la restriction d'être "sans inégalités". Nous prouvons qu'elle est strictement plus expressive que MMSNP et qu'elle possède également une dichotomie.Il existe une logique MMSNP₂ qui étend MMSNP de la même manière que MSO₂ étend la logique monadique du second ordre (MSO). On sait que MMSNP₂ est un fragment de GMSNP et que ces deux classes ont toutes deux une dichotomie ou n'en ont pas. Nous revisitons ce résultat et le renforçons en prouvant que, en ce qui concerne le fait d'avoir une dichotomie, sans perte de généralité, on peut considérer seulement les problèmes MMSNP₂ sur des signatures à un élément, au lieu des problèmes GMSNP sur des signatures finies arbitraires.Nous cherchons à prouver l'existence d'une dichotomie pour les MMSNP₂ en construisant en temps polynomial, pour tout problème MMSNP₂, un problème MMSNP équivalent. Nous rencontrons quelques obstacles pour construire une telle équivalence. Cependant, si nous permettons aux formules MMSNP d'être composées d'un nombre dénombrable de conjonctions négatives, nous prouvons qu'une telle équivalence existe. De plus, la formule MMSNP infinie correspondante a la propriété d'être "régulière". Cette propriété de régularité signifie que, dans un certain sens, cette formule est essentiellement finie. Il est connu que les problèmes MMSNP réguliers peuvent être exprimés par CSP sur des modèles oméga-catégoriques. De plus, il existe une caractérisation de la dichotomie algébrique pour les CSP oméga-catégoriques qui décrivent des problèmes MMSNP. Si l'on parvient à étendre cette caractérisation algébrique sur les problèmes réguliers MMSNP, alors notre résultat fournirait une dichotomie algébrique pour MMSNP₂.Une autre façon potentielle de prouver l'existence d'une dichotomie pour MMSNP₂ est d'imiter la preuve de Feder et Vardi pour MMSNP. C'est-à-dire, en trouvant un problème CSP équivalent à réduction polynomial près. La partie la plus difficile est de réduire une structure d'entrée donnée à une structure de maille suffisamment grande. Pour MMSNP et CSP, cela est fait en utilisant des expanseurs, c'est-à-dire des structures où la distribution des tuples est proche d'une distribution uniforme. Nous étudions cette approche dans le cas de MMSNP₂ et soulignons les principaux obstacles.Nous considérons également une extension de CSP : la classe des problèmes de partition matricielle (MP). Nous l'étudions sous plusieurs angles. Il est bien connu que CSP sur une signature finie arbitraire a une dichotomie si et seulement si CSP sur des graphes dirigés a une dichotomie. Motivés par ce résultat, nous considérons les problèmes MP sur des signatures finies arbitraires et montrons qu'ils ont une dichotomie si et seulement si les problèmes MP sur des signatures à un élément ont une dichotomie, de manière similaire à notre résultat pour MMSNP₂. Une autre perspective est de caractériser les problèmes MP par rapport à leur définissabilité en logique du premier ordre (FO). Pour le CSP, un problème est définissable en logique du premier ordre si, et seulement si, il a une dualité finitaire, c'est-à-dire une famille finie de digraphes telle qu'un digraphe d'entrée est accepté par le CSP si, et seulement si, aucun digraphe de la famille n'est homomorphe à celui d'entrée. Il y a déjà eu quelques tentatives pour classer les problèmes de partition matricielle en fonction de l'existence d'un nombre fini d'obstructions minimales, c'est-à-dire qu'un graphe d'entrée est accepté par le problème MP si et seulement s'il ne contient pas de sous-graphe induit d'une famille finie donnée. Nous parvenons à montrer que, pour les problèmes MP, ces deux notions sont les mêmes. La troisième perspective est de trouver une logique qui serait liée à MP d'une manière similaire à celle de MMSNP par rapport à CSP. Nous introduisons, comme candidat potentiel, une logique obtenue à partir de MMSNP en relâchant la restriction "monotone", et montrons qu'elle contient MP. Cependant, nous ne savons pas comment montrer l'équivalence. Enfin, nous étudions la notion de "polymorphisme" pour les problèmes MP. Nous le faisons afin de considérer la caractérisation de la dichotomie algébrique pour les CSP finis et de voir s'il existe un potentiel pour considérer les polymorphismes pour les problèmes MP. Dans le cas des CSP, une structure a un polymorphisme non-trivial si, et seulement si, le CSP correspondant peut être résolu en temps polynomial. Nous parvenons à fournir un problème MP qui n'a que des polymorphismes triviaux et qui peut être résolu en temps polynomial. Cela signifie que, pour les problèmes MP, l'existence d'une caractérisation algébrique est peu probable.Dans un chapitre indépendant, nous étudions le problème du Maximum Cut (maxcut). Bien qu'il soit NP-complet en général, sa complexité devient inconnue si nous ne considérons que les graphes d'intervalles unitaires en entrée. Sachant que maxcut est NP-complet sur les graphes d'intervalles, nous nous approchons le plus possible des graphes d'intervalles unitaires en prouvant qu'il reste NP-complet même si nous sommes autorisés à opérer avec des intervalles de seulement deux longueurs différentes.

The most standard model checking approaches are limited to verifying concrete specifications, such as “can we reach a configuration with more than 10 time units elapsing ?”. Nethertheless, for certaincomputer programs, like embedded systems, the constraints depend on the environment. Thus arisesthe need for parametric specifications, such as “can we reach a configuration with more than p timeunits elapsing ?” where p is a parameter which takes values in the non-negative integers.In this thesis, we study parametric pushdown, counter and timed automata and extensions the-reof. In addition to expressing concrete constraints (on the stack, on the counter or on clocks), thesecan employ parametric constraints. The reachability problem for a parametric automaton asks for the existence of an assignment of the parameters such that there exists an accepting run in the underlying concrete automaton. In addition to the reachability problem, we consider parametric parity games, two player games where players alternate chosing assignments for each parameters, then alternate moving a token along the configurations of the concrete automaton resulting from their choice of parameter assignment. We consider the problem of deciding which player has a winning strategy.Parametric timed automata (PTA for short) were introduced in the 90s by Alur, Henzinger andVardi, who showed that the reachability problem for PTA was undecidable, already when only threeclocks can be compared against parameters, and decidable in the case only one clock can. We callsuch clocks that can be compared to parameters parametric clocks. A few years ago, Bundala andOuaknine proved that, for parametric timed automata with two parametric clocks and one parame-ter ((2, 1)-PTA for short), the reachability problem is decidable and also provided a PSPACENEXP lower bound. One of the main results of this thesis states that reachability for (2, 1)-PTA is in factEXPSPACE-complete. For the EXPSPACE lower bound, inspired by previous work by Göller, Haase, Ouaknine, and Worrell, we rely on a serializability characterization of EXPSPACE (in turn originally based on Barrington's Theorem). We provide a programming language and we show it can simulate serializability computations. Relying on a logspace translation of numbers in Chinese Remainder Representation to binary representation due to Chiu, Davida, and Litow, we then show that small (2, 1)-PTA can simulate our programming language. For the EXPSPACE upper bound on (2, 1)-PTA, we first give a careful exponential time reduction towards a variant of parametric one-counter automata over one parameter based on a minor adjustment of a construction due to Bundala and Ouaknine. We solve the reachability problem for this parametric one-counter automata with one parameter variant, by providing a series of techniques to partition a fictitious run into several carefully chosen subruns. This allows us to prove that it is sufficient to consider a parameter value of exponential magnitude only, which in turn leads to a doubly-exponential upper bound on the value of the only parameter of the (2, 1)-PTA. We hope that extensions of our techniques lead to finally establishing decidability of the long-standing open problem of reachability in PTA with two parametric clocks and arbitrarily many parameters.Concerning parametric pushdown automata, our main result states that deciding the winner ofa parametric parity game is in (n + 1)-EXP in the case the number of parameters n is fixed, but nonelementary otherwise. We provide the nonelementary lower bound via a reduction of the FO satisfiability problem on words. For the upper bound, we reduce parametric pushdown parity games to higher-order pushdown automata parity games, which are known to be n-EXP complete in the case of stacks of level n.; Les approches standard de la vérification de modèle se limitent à des spécifications concrètes, par exemple «est-il possible d'atteindre une configuration après que plus de 10 unités de temps se soient écoulées?». Néanmoins, pour certains types de programmes informatiques, comme les technologies embarquées, les contraintes dépendent de l'environnement. De là émerge la nécessité des spécifications paramétriques, par exemple «est-il possible d'atteindre une configuration après que plus de p unités de temps se soient écoulées?» où p désigne un paramètre dont la valeur reste à spécifier.Dans cette thèse nous étudions des variantes paramétriques de trois modèles classique, les automates à pile, à compteur, et temporisés. En plus d'exprimer des contraintes concrètes (sur la pile, le compteur ou les horloges), ces modèles peuvent exprimer des contraintes paramétriques via des comparaisons avec des paramètres. Le problème de l'accessibilité consiste à demander s'il existe une assignation des paramètres telle que il existe une exécution acceptante dans l'automate concret qui en résulte. En plus de ce problème nous étudions des jeux de parités paramétriques, où deux joueurs choisissent une évaluation pour chaque paramètre chacun leur tour, puis déplacent un jeton dans le graphe de l'automate concret résultant. Nous nous intéressons au problème de décider quel joueur dispose d'une stratégie gagnante.Les automates temporisés paramétriques ont été introduit dans les années 90 par Alur, Henzinger et Vardi, qui ont démontré que le problème de l'accessibilité était indécidable, même avec seulement trois horloges pouvant être comparées à des paramètres, ou horloges paramétriques — mais décidable dans le cas d'une seule horloge paramétrique. Des résultats récents de Bundala et Ouaknine démontrent que dans le cas de deux horloges paramétriques et un paramètre, le problème est décidable ainsi que PSPACE^NEXP-dur. Un des principaux résultats de cette thèse consiste à démontrer le caractère EXPSPACE-complet du problème.La borne inférieure EXPSPACE repose sur des résultats récents du domaine de la complexité avancée. Inspirés par Göller, Haase, Ouaknine, et Worrell, nous visualisons la classe EXPSPACE comme un langage de feuille (vision qui repose sur le théorème de Barrington). Nous introduisons un langage de programmation qui peut reconnaître ce genre de langage de feuille. Nous utilisons ensuite une représentation des entiers sous forme de restes chinois dont Chiu, Davida et Litow ont montré qu'elle permettait de calculer en LOGSPACE la représentation binaire, et démontrons grâce à elle que les automates temporisés paramétriques à deux horloges paramétriques et un paramètre peuvent simuler notre langage de programmation.Pour la borne supérieure, à la façon de Bundala et Ouaknine, nous réduisons le problème au problème de l'accessibilité dans un type particulier d'automates à compteur paramétrique. Par une série de techniques de découpage d'une exécution fictive, nous démontrons que ce problème est dans PSPACE. Étant donné que notre réduction se fait en temps exponentiel, cela conduit à une borne supérieure EXPSPACE pour le problème de l'accessibilité dans les automates temporisés paramétriques à deux horloges et un paramètre.En ce qui concerne les jeux de parités paramétriques pour les automates à piles paramétriques, nous démontrons que le problème de déterminer quel joueur a une stratégie gagnante est dans (n+1)-EXP si le nombre de paramètres est fixé à n, mais nonélémentaire sinon. Le caractère nonélémentaire du problème est démontré par réduction du problème de la satisfaisabilité des formules de la logique du premier ordre. La borne supérieure est obtenue via une réduction aux automates à pile de piles, pour lesquels le problème des jeux de parités est n-EXP-complet dans le cas de n niveaux de piles.

The work presented in this thesis can be divided in two, the first part focusing on self-stabilization in distributed systems, and the second one on classical graph algorithms.The self-stabilization part deals with Byzantine faults for problems that had no prior algorithm handling those. One of them is then used to propose a way to produce self-stabilizing algorithms for mendable problems in anonymous networks. The classical graph algorithm part introduces a new problem that extends some previous work on colored matchings and gives a hardness results as well as an FPT algorithm for a specific parameter.Chapter 3 introduces an algorithm that handles Byzantine faults and solves the MIS problem in anonymous systems in O(n²) rounds with high probability under the fair distributed daemon. It then gives a slightly modified version of this algorithm, that solves the same problem under the adversarial distributed daemon (without handling Byzantine faults) in O(n²) moves.Chapter 5 introduces an algorithm that handles Byzantine faults and solves the Minimal Clique Decomposition problem in O(Δn) rounds under the fair distributed daemon in systems with unique identifiers.Chapter 4 introduces an algorithm that solves the (k,k-1)-ruling set problem in anonymous networks under the Gouda daemon. The parallel construction of multiple such ruling sets allows to find a distance-K coloring in an anonymous network, whose colors are used as identifiers to solve any mending problems on anonymous networks.Finally, Chapter 6 introduces a new problem, the Minimum Colored Maximum Matching problem, that extends what had already been done on colored matchings. The problem is shown to be NP-hard and hard to approximate within a logarithmic ratio of the size of the graph. It is also proven W[2]-hard with the parameter "size of the solution", but fixed-parameter tractable with the parameter "size of a maximum matching".; Le travail présenté par cette thèse peut être divisé en deux parties, la première se concentrant sur l'autostabilisation dans des systèmes distribués, la seconde sur de l'algorithmique de graphe classique. La partie portant sur l'autostabilisation s'intéresse aux pannes Byzantines pour des problèmes qui n'avaient pas d'algorithme connu supportant celles-ci. L'un d'eux est ensuite utilisé pour proposer un mécanisme produisant des algorithme autostabilisants pour tout problème raccommodable dans des réseaux anonymes. La partie d'algorithmique de graphes introduit a nouveau problème étendant des travaux antérieurs sur les couplages colorés et donne un résultat de difficulté algorithmique ainsi qu'un algorithme FPT pour un certain paramètre.Le chapitre 3 introduit un algorithme qui supporte les pannes Byzantines et résout le problème de l'indépendant maximal dans les systèmes anonymes en O(n²) rounds avec forte probabilité sous le démon distribué juste. Il donne ensuite une version légèrement modifiée de cet algorithme qui résout le même problème sous le démon distribué antagoniste (sans supporter de pannes Byzantines) en O(n²) opérations.Le chapitre 5 introduit un algorithme qui supporte les pannes Byzantines et résout le problème de partition minimales en cliques en O(Δn) rounds sous le démon distribué juste dans des systèmes à identifiants uniques.Le chapitre 4 introduit un algorithme qui résout le problème du (k,k-1)-ensemble dirigeant dans les réseaux anonymes sous le démon Gouda. La construction en parallèle de tels ensembles dirigeants permet de trouver une coloration à distance K, dont on utilise les couleurs comme identifiants pour résoudre n'importe quel problème raccommodable sur des réseaux anonymes.Enfin, le chapitre 6 introduit un nouveau problème, le problème du couplage maximum minimalement coloré, qui étend des travaux antérieurs sur les couplages colorés. Ce problème est ici démontré NP-dur, et difficile à approximer sous un ratio logarithmique de la taille du graphe. Il y est également démontré qu'il W[2]-difficile en considérant le paramètre "taille de la solution", mais FPT en considérant le paramètre "taille d'un couplage maximum".

In numerical linear algebra, a well-established practice is to choose a norm that exploits the structure of the problem at hand in order to optimize accuracy or computational complexity. In numerical polynomial algebra, a single norm (attributed to Weyl) dominates the literature. This article initiates the use of $L_p$ norms for numerical algebraic geometry, with an emphasis on $L_{\infty}$. This classical idea yields strong improvements in the analysis of the number of steps performed by numerous iterative algorithms. In particular, we exhibit three algorithms where, despite the complexity of computing $L_{\infty}$-norm, the use of $L_p$-norms substantially reduces computational complexity: a subdivision-based algorithm in real algebraic geometry for computing the homology of semialgebraic sets, a well-known meshing algorithm in computational geometry, and the computation of zeros of systems of complex quadratic polynomials (a particular case of Smale's 17th problem)., 54 pages

Figurative drawing is a skill that takes time to learn, and it evolves during different childhood phases that begin with scribbling and end with representational drawing. Between these phases, it is difficult to assess when and how children demonstrate intentions and representativeness in their drawings. The marks produced are increasingly goal-oriented and efficient as the child's skills progress from scribbles to figurative drawings. Pre-figurative activities provide an opportunity to focus on drawing processes. We applied fourteen metrics to two different datasets (N = 65 and N = 344) to better understand the intentional and representational processes behind drawing, and combined these metrics using principal component analysis (PCA) in different biologically significant dimensions. Three dimensions were identified: efficiency based on spatial metrics, diversity with color metrics, and temporal sequentiality. The metrics at play in each dimension are similar for both datasets, and PCA explains 77% of the variance in both datasets. Gender had no effect, but age influenced all three dimensions differently. These analyses for instance differentiate scribbles by children from those drawn by adults. The three dimensions highlighted by this study provide a better understanding of the emergence of intentions and representativeness in drawings. We discussed the perspectives of such findings in comparative psychology and evolutionary anthropology.

In this paper we consider the problem of, given a set of graphs with the same set of vertices, choosing a minimum cycle basis for each of these graphs such that the intersection of these bases has maximal size. We first prove this problem to be NP-complete, then prove its polynomiality for the special case of two graphs and study both the hardness of approximation and the parameterized complexity.

International audience; A path-decomposition of a graph G = (V, E) is a sequence of subsets of V , called bags, that satisfy some connectivity properties. The length of a path-decomposition of a graph G is the greatest distance between two vertices that belong to a same bag and the pathlength, denoted by p (G), of G is the smallest length of its path-decompositions. This parameter has been studied for its algorithmic applications for several classical metric problems like the minimum eccentricity shortest path problem, the line-distortion problem, etc. However, deciding if the pathlength of a graph G is at most 2 is NP-complete, and the best known approximation algorithm has a ratio 2 (there is no c-approximation with c < 3 2 unless P = N P). In this work, we focus on the study of the pathlength of simple sub-classes of planar graphs. We start by designing a linear-time algorithm that computes the pathlength of trees. Then, we show that the pathlength of cycles with n vertices is equal to n 2. Finally, our main result is a (+1)-approximation algorithm for the pathlength of outerplanar graphs. This algorithm is based on a characterization of almost optimal (of length at most p (G)+1) path-decompositions of outerplanar graphs. * This work is partially funded by the project UCA JEDI (ANR-15-IDEX-01) and EUR DS4H Investments in the Future (ANR-17-EURE-004).

This paper presents a new abstract method for proving lower bounds in computational complexity. Based on the notion of topological and measurable entropy for dynamical systems, it is shown to generalise three previous lower bounds results from the literature in algebraic complexity. We use it to prove that maxflow, a Ptime complete problem, is not computable in polylogarithmic time on parallel random access machines (prams) working with real numbers. This improves on a result of Mulmuley since the class of machines considered extends the class “prams without bit operations”. We further improve on this result by showing that euclidean division cannot be computable in polylogarithmic time using division on the reals, pinpointing that euclidean division provides a significant boost in expressive power.On top of showing this new separation result, we show our method captures previous lower bounds results from the literature: Steele and Yao’s lower bounds for algebraic decision trees, Ben-Or’s lower bounds for algebraic computation trees, Cucker’s proof that NC is not equal to Ptime in the real case, and Mulmuley’s lower bounds for “prams without bit operations”.

Hom shifts form a class of multidimensional shifts of finite type (SFT) and consist of colorings of the grid Z2 where adjacent colours must be neighbors in a fixed finite undirected simple graph G. This class includes several important statistical physics models such as the hard square model. The gluing gap measures how far any two square patterns of size n can be glued, which can be seen as a measure of the range of order, and affects the possibility to compute the entropy (or free energy per site) of a shift. This motivates a study of the possible behaviors of the gluing gap. The class of Hom shifts has the interest that mixing type properties can be formulated in terms of algebraic graph theory, which has received a lot of attention recently. Improving some former work of N. Chandgotia and B. Marcus, we prove that the gluing gap either depends linearly on n or is dominated by log(n). We also find a Hom shift with gap {\Theta}(log(n)), infirming a conjecture formulated by R. Pavlov and M. Schraudner. The physical interest of these results is to better understand the transition from short-range to long-range order (respectively sublogarithmic and linear gluing gap), which is reflected in whether some parameter, the square cover, is finite or infinite.

Positional games have been introduced by Hales and Jewett in 1963 and have been extensively investigated in the literature since then. These games are played on a hypergraph where two players alternately select an unclaimed vertex of it. In the Maker-Breaker convention, if Maker manages to fully take a hyperedge, she wins, otherwise, Breaker is the winner. In the Maker-Maker convention, the first player to take a hyperedge wins. In both cases, the game stops as soon as Maker has taken a hyperedge. By definition, this family of games does not handle scores and cannot represent games in which players want to maximize a quantity. In this work, we introduce scoring positional games, that consist in playing on a hypergraph until all the vertices are claimed, and by defining the score as the number of hyperedges a player has fully taken. We focus here on Incidence, a scoring positional game played on a 2-uniform hypergraph, i.e. an undirected graph. In this game, two players alternately claim the vertices of a graph and score the number of edges for which they own both end vertices. In the Maker-Breaker version, Maker aims at maximizing the number of edges she owns, while Breaker aims at minimizing it. In the Maker-Maker version, both players try to take more edges than their opponent. We first give some general results on scoring positional games such that their membership in Milnor's universe and some general bounds on the score. We prove that, surprisingly, computing the score in the Maker-Breaker version of Incidence is PSPACE-complete whereas in the Maker-Maker convention, the relative score can be obtained in polynomial time. In addition, for the Maker-Breaker convention, we give a formula for the score on paths by using some equivalences due to Milnor's universe. This result implies that the score on cycles can also be computed in polynomial time.

International audience; Under the Strong Exponential-Time Hypothesis, the diameter of general unweighted graphs cannot be computed in truly subquadratic time (in the size n + m of the input), as shown by Roditty and Williams. Nevertheless there are several graph classes for which this can be done such as bounded-treewidth graphs, interval graphs and planar graphs, to name a few. We propose to study unweighted graphs of constant distance VC-dimension as a broad generalization of many such classes-where the distance VC-dimension of a graph G is defined as the VCdimension of its ball hypergraph: whose hyperedges are the balls of all possible radii and centers in G. In particular for any fixed H, the class of H-minor free graphs has distance VC-dimension at most |V (H)| − 1.

We propose an algorithm for quickly evaluating polynomials. It pre-conditions a complex polynomial $P$ of degree $d$ in time $O(d\log d)$, with a low multiplicative constant independent of the precision. Subsequent evaluations of $P$ computed with a fixed precision of $p$ bits are performed in average arithmetic complexity $O\big(\sqrt{d(p+\log d)}\big)$ and memory $O(dp)$. The average complexity is computed with respect to points $z \in \mathbb{C}$, weighted by the spherical area of $\overline{\mathbb{C}}$. The worst case does not exceed the complexity of H{\"o}rner's scheme. In particular, our algorithm performs asymptotically as $O(\sqrt{d\log d})$ per evaluation. For many classes of polynomials, in particular those with random coefficients in a bounded region of $\mathbb{C}$, or for sparse polynomials, our algorithm performs much better than this upper bound, without any modification or parameterization.The article contains a detailed analysis of the complexity and a full error analysis, which guarantees that the algorithm performs as well as H\''orner's scheme, only faster. Our algorithm is implemented in a companion library, written in standard C and released as an open-source project [MV22].Our claims regarding complexity and accuracy are confirmed in practice by a set of comprehensive benchmarks.

International audience; There has been little exploration of the explicit simulation of the set of options of actors in agent-based models and its evolution over time. This study proposes to use affordances as intermediate entities between agents’ environment and agent actions. We illustrated the approach on a typical gravity-fed network in the South-East of France to explore how the abandonment of traditional sharing of water changes the irrigators’ options to irrigate. We simulated a typical dry year irrigation season under two institutional arrangements (i.e. traditional coordination through daily slots and its abandonment). Simulation results are consistent with field surveys, and reveal an increase in the number of internal conflicts among irrigators as the counterpart of the abandonment of traditional sharing of water. They also highlight the consequences of the heterogeneity of the irrigators' interests within the collective institution. The sensitivity analysis of the model allowed identification of optimal modalities of coordination, and a potential compromise between past and current institutional arrangements. The key benefits of using affordances in ABM lie in the study of their population dynamics for characterizing the interaction situations between actors and their environment and for better understanding the model dynamics.

This thesis is divided into two main parts, although a common denominator can be found in the notion of non-determinism in automata, and its resolution. The first part focuses on a notion of limited non-determinism, which is explorable automata. These are automata for which the non-determinism can be resolved by building a finite number of simultaneous runs. This generalizes the notion of Good-For-Games (GFG) automata, which correspond to the case where a single run is enough. We give another link between these two notions, namely the fact that GFGness is decidable in PTIME for explorable automata. We prove that deciding whether an automaton is explorable is an EXPTIME-complete problem for finite and Büchi automata. We also consider the problem of omega-explorability, in which we allow for a countable number of simultaneous runs. This problem is non-trivial for automata of infinite words, and we prove the EXPTIME-completeness of deciding the omega-explorability of a co-Büchi automaton. In the second part, we describe a cyclic proof system designed to provide certificates of inclusions between languages of infinite words. These languages are represented by omega-regular expressions, or in the final version by a generalization of these expressions, allowing for arbitrary nesting of the omega operator. We prove the soundness and completeness of that system, along with some algorithmic results: the decidability of the validity of a cyclic proof, and a PSPACE proof search algorithm to decide the inclusion of languages.; Cette thèse est divisée en deux parties, qui ont en commun le problème du non-déterminisme chez différents modèles d'automates, et la résolution de celui-ci. La première partie s'intéresse à une forme de limitation du non-déterminisme, que l'on nomme l'explorabilité. Un automate est explorable s'il est possible de résoudre le non-déterminisme en créant un nombre finis d'exécutions en parallèle. Il s'agit d'une généralisation de la notion d'automate Good-For-Games, i.e. Bon-Pour-les-Jeux (GFG), qui correspond au cas où une seule exécution suffit. Nous commençons par fournir un lien supplémentaire entre ces deux notions : le fait que l'on peut décider en temps polynomial si un automate est GFG, à condition de savoir qu'il est explorable. Nous montrons ensuite que la reconnaissance des automates GFG est un problème PSPACE-complet dans le cas des automates de mots finis ou de Büchi. Nous nous intéressons aussi au problème de l'omega-explorabilité, qui correspond au cas où l'on s'autorise un nombre dénombrable d'exécutions. Celui-ci est non trivial dans le cas des mots infinis, et nous montrons que décider l'omega-explorabilité d'un automate de co-Büchi est EXPTIME-complet. Dans la seconde partie, nous présentons un système de preuves cycliques permettant de fournir des certificats d'inclusions entre langages de mots infinis. Ces langages sont représentés par des expressions omega-régulières dans un premier temps, puis par une généralisation de ces expressions, qui permet notamment des imbrications de l'opérateur omega. Nous montrons la correction et la complétude de ce système, et fournissons deux résultats algorithmiques : la décidabilité de la validité d'une preuve cyclique, ainsi qu'un algorithme PSPACE pour décider l'inclusion de deux langages par la recherche de preuve.

We revisit parallel-innermost term rewriting as a model of parallel computation on inductive data structures and provide a corresponding notion of runtime complexity parametric in the size of the start term. We propose automatic techniques to derive both upper and lower bounds on parallel complexity of rewriting that enable a direct reuse of existing techniques for sequential complexity. The applicability and the precision of the method are demonstrated by the relatively light effort in extending the program analysis tool AProVE and by experiments on numerous benchmarks from the literature., Comment: Extended authors' accepted manuscript for a paper accepted for publication in the Proceedings of the 32nd International Symposium on Logic-based Program Synthesis and Transformation (LOPSTR 2022). 27 pages

An automata network (AN) is a finite graph where each node holds a state from a finite alphabet and is equipped with a local map defining the evolution of the state of the node depending on its neighbors. They are studied both from the dynamical and the computational complexity point of view. Inspired from well-established notions in the context of cellular automata, we develop a theory of intrinsic simulations and universality for families of automata networks. We establish many consequences of intrinsic universality in terms of complexity of orbits (periods of attractors, transients, etc) as well as hardness of the standard well-studied decision problems for automata networks (short/long term prediction, reachability, etc). In the way, we prove orthogonality results for these problems: the hardness of a single one does not imply hardness of the others, while intrinsic universality implies hardness of all of them. As a complement, we develop a proof technique to establish intrinsic simulation and universality results which is suitable to deal with families of symmetric networks were connections are non-oriented. It is based on an operation of glueing of networks, which allows to produce complex orbits in large networks from compatible pseudo-orbits in small networks. As an illustration, we give a short proof that the family of networks were each node obeys the rule of the 'game of life' cellular automaton is strongly universal. This formalism and proof technique is also applied in a companion paper devoted to studying the effect of update schedules on intrinsic universality for concrete symmetric families of automata networks., Comment: arXiv admin note: substantial text overlap with arXiv:2105.08356

International audience; This paper explores the notion of resilience of a fault in a DES, as the ability to spontaneously return to a normal behavior, without leaking information about this fault occurrence to an external observer. Resilience expresses some form of insensitivity or robustness, related but different from classical notions like diagnosability or opacity. Different definitions of resilience are examined, expressed in terms of recovery points or of language relations. It is shown that verifying resilience is PSPACE-complete. However, the complexity reduces to PTIME for the recently introduced history deterministic automata, a sub-class of NFA. We examine in detail the instructive pathway to this complexity reduction, which could be instrumental for the complexity reduction of other DES problems.

International audience; Type systems as a technique to analyse or control programs have been extensively studied for functional programming languages. In particular some systems allow to extract from a typing derivation a complexity bound on the program. We explore how to extend such results to parallel complexity in the setting of the pi-calculus, considered as a communication-based model for parallel computation. We study two notions of time complexity: the total computation time without parallelism (the work) and the computation time under maximal parallelism (the span). We define operational semantics to capture those two notions, and present two type systems from which one can extract a complexity bound on a process. The type systems are inspired both by size types and by input/output types, with additional temporal information about communications.

Coherent control of quantum computations can be used to improve some quantum protocols and algorithms. For instance, the complexity of implementing the permutation of some given unitary transformations can be strictly decreased by allowing coherent control, rather than using the standard quantum circuit model. In this paper, we address the problem of optimising the resources of coherently controlled quantum computations. We refine the PBS-calculus, a graphical language for coherent control which is inspired by quantum optics. In order to obtain a more resource-sensitive language, it manipulates abstract gates - that can be interpreted as queries to an oracle - and more importantly, it avoids the representation of useless wires by allowing unsaturated polarising beam splitters. Technically the language forms a coloured PROP. The language is equipped with an equational theory that we show to be sound, complete, and minimal. Regarding resource optimisation, we introduce an efficient procedure to minimise the number of oracle queries of a given diagram. We also consider the problem of minimising both the number of oracle queries and the number of polarising beam splitters. We show that this optimisation problem is NP-hard in general, but introduce an efficient heuristic that produces optimal diagrams when at most one query to each oracle is required., LIPIcs, Vol. 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), pages 36:1-36:15