Search

International audience; Today car drivers struggle to find a free parking space for their cars. It is considered a big challenge specially in large cities and in rush hours. Many studies considered this problem and how it influences our life. This increases emissions and energy consumption and wastes people’s times as they try to find a free space for their cars. People normally become exhausted all over the day to reach their destination which causes stress and make them lose their temper. This would have a bad impact on the quality of life and economy. Based on the above, today people expect technology to address this problem and hence find a suitable solution to end the suffering of motorists. On the other hand, IoT is a promising platform for providing unusual applications for helping people and provide them a better way to manage their day’s lives.This work proposes a solution for a green intelligent parking system based on IoT. This solution is supported by proposing the game theory mathematical model. Game theory is used to model a reservation system of the proposed car parking solution. This work tackles the main problems facing car drivers to find available car parking spaces. These problems include: the parking fees, how far the car park from the car drivers destinations and hence the amount of walking, and the parking duration. Moreover, the proposed solution encourages companies and householders to offer their own parking stalls and/or driveways for renting in the unused times. From one hand, this will help on providing more parking lots specially in the dense traffic areas. On the other hand, the owners will get a revenue of their unused assets. Therefore, this work proposes a solution to parking problems by providing affordable parking lots based on the choice of the car driver that is relatively close to the destination. As a result of that, there will not be wasting of time or energy, frustration and panic will be reduced, fewer traffic jams, and consequently a green environment and a better quality of life.

International audience; We study the social choice setting of perpetual voting where, based on voter preferences, decisions have to be taken over a finite horizon of consecutive points in time (e.g, days). We consider two complementary settings: a Static setting, in which voter preferences remain static over time, and a Dynamic setting, in which voter preferences may change over time. We adapt the well-established Justified Representation and Proportional Justified Representation axioms, commonly used in the social choice literature, to perpetual voting, resulting in two axiomatic variants for the static setting and four variants for the dynamic setting. We show that all of the axioms are always satisfiable, and that simple preference aggregation methods can be used to satisfy the axioms in both cases. We then conduct a large human study (N = 190) aimed at identifying what potential voters (i.e., ordinary people) deem as desirable outcomes in simple perpetual voting settings. Our results show that approximately half of our participants consider different interpretations of fairness that correspond to our axiomatic framework. Taken jointly, our results can be used to help the research community identify appropriate aggregation methods to use in practice. INDEX TERMS Computational social choice, justified representation, perpetual voting.

In this paper, we design a framework to obtain efficient algorithms for several problems with a global constraint (acyclicity or connectivity) such as Connected Dominating Set, Node Weighted Steiner Tree, Maximum Induced Tree, Longest Induced Path, and Feedback Vertex Set. We design a meta-algorithm that solves all these problems and whose running time is upper bounded by $2^{O(k)}\cdot n^{O(1)}$, $2^{O(k \log(k))}\cdot n^{O(1)}$, $2^{O(k^2)}\cdot n^{O(1)}$, and $n^{O(k)}$ where $k$ is respectively the clique-width, $\mathbb{Q}$-rank-width, rank-width, and maximum induced matching width of a given decomposition. Our approach simplifies and unifies the known algorithms for each of the parameters and its running time matches asymptotically also the running times of the best known algorithms for basic \sf NP-hard problems such as Vertex Cover and Dominating Set. Our framework is based on the $d$-neighbor equivalence defined in [B. Bui-Xuan, J. A. Telle, and M. Vatshelle, Theoret. Comput. Sci., (2013), pp. 66--76] and the rank-based approach introduced in [H. L. Bodlaender, M. Cygan, S. Kratsch, and J. Nederlof, Inform. and Comput., 243 (2015), pp. 86--111]. The results we obtain highlight the importance of the $d$-neighbor equivalence relation on the algorithmic applications of width measures. We also prove that our framework could be useful for ${\sf W}[1]$-hard problems parameterized by clique-width such as Max Cut and Maximum Minimal Cut. For these latter problems, we obtain $n^{O(k)}$, $n^{O(k)}$, and $n^{2^{O(k)}}$ time algorithms where $k$ is respectively the clique-width, the $\mathbb{Q}$-rank-width, and the rank-width of the input graph. publishedVersion

International audience; In a vertex-coloured graph, a set of vertices S is said to be a rainbow set if every colour in the graph appears exactly once in S. We investigate the complexities of various problems dealing with domination in vertex-coloured graphs (existence of rainbow dominating sets, of rainbow locating-dominating sets, of rainbow identifying sets), including when we ask for a unique solution: we show equivalence between these complexities and those of the well-studied Boolean satisfiability problems.

International audience; We introduce the notion of pre-expansivity for cellular automata (CA): it is the property of being positively expansive on asymptotic pairs of configurations (i.e. configurations that differ in only finitely many positions). Pre-expansivity therefore lies between positive expansivity and pre-injectivity, two important notions of CA theory.We show that there exist one-dimensional pre-expansive CAs which are not positively expansive and they can be chosen reversible (while positive expansivity is impossible for reversible CAs). We provide both linear and non-linear examples. In the one-dimensional setting, we also show that pre-expansivity implies sensitivity to initial conditions in any direction. We show however that no two-dimensional Abelian CA can be pre-expansive. We also consider the finer notion of k-expansivity (positive expansivity over pairs of configurations with exactly k differences) and show examples of linear CA in dimension 2 and on the free group that are k-expansive depending on the value of k, whereas no (positively) expansive CA exists in this setting.

International audience; In the localization game, introduced by Seager in 2013, an invisible and immobile target is hidden at some vertex of a graph $G$. At every step, one vertex $v$ of $G$ can be probed which results in the knowledge of the distance between $v$ and the secret location of the target. The objective of the game is to minimize the number of steps needed to locate the target whatever be its location.We address the generalization of this game where $k\geq 1$ vertices can be probed at every step. Our game also generalizes the notion of the {\it metric dimension} of a graph.Precisely, given a graph $G$ and two integers $k,\ell \geq 1$, the {\sc Localization} problem asks whether there exists a strategy to locate a target hidden in $G$ in at most $\ell$ steps and probing at most $k$ vertices per step. We first show that, in general, this problem is \textsf{NP}-complete for every fixed $k \geq 1$ (resp., $\ell \geq 1$).We then focus on the class of trees.On the negative side,we prove that the \Localization problem is \textsf{NP}-complete in trees when $k$ and $\ell$ are part of the input. On the positive side, we design a $(+1)$-approximation algorithm for the problem in $n$-node trees, {\it i.e.}, an algorithm that computes in time $O(n \log n)$ (independent of $k$) a strategy to locate the target in at most one more step than an optimal strategy. This algorithm can be used to solve the \Localization problem in trees in polynomial time if $k$ is fixed.We also consider some of these questions in the context where, upon probing the vertices,the relative distances to the target are retrieved.This variant of the problem generalizes the notion of the {\it centroidal dimension} of a graph.

International audience; A normal form system (NFS) for representing Boolean functions is thought of as a set of stratified terms over a fixed set of connectives. For a fixed NFS A, the complexity of a Boolean function f with respect to A is the minimum of the sizes of terms in A that represent f. This induces a preordering of NFSs: an NFS A is polynomially as efficient as an NFS B if there is a polynomial P with nonnegative integer coefficients such that the complexity of any Boolean function f with respect to A is at most the value of P in the complexity of f with respect to B. In this paper we study monotonic NFSs, i.e., NFSs whose connectives are increasing or decreasing in each argument. We describe the monotonic NFSs that are optimal, i.e., that are minimal with respect to the latter preorder. We show that these minimal monotonic NFSs are all equivalent. Moreover, we address some natural questions, e.g.: does optimality depend on the arity of connectives? Does it depend on the number of connectives used? We show that optimal monotonic NFSs are exactly those that use a single connective or one connective and the negation. Finally, we show that optimality does not depend on the arity of the connectives.

International audience; The class of Basic Feasible Functionals BFF$_2$ is the type-2 counterpart of the class FP of type-1 functions computable in polynomial time. Several characterizations have been suggested in the literature, but none of these present a programming language with a type system guaranteeing this complexity bound. We give a characterization of BFF$_2$ based on an imperative language with oracle calls using a tier-based type system whose inference is decidable. Such a characterization should make it possible to link higher-order complexity with programming theory. The low complexity (cubic in the size of the program) of the type inference algorithm contrasts with the intractability of the aforementioned methods and does not overly constrain the expressive power of the language.

A subset $D \subseteq V$ is an \emph{independent} (or \emph{stable}) \emph{dominating set} of a graph $G = (V,E)$ if $D$ is an independent set (no edges between vertices of $D$) and dominates all the vertices of $G$ (each vertex of $V-D$ has a neighbour in $D$). In this paper we study a generalisation of this classical notion. Namely, an instance of our problem is a graph $G=(V, E)$ and $\Pi=(V_1, \dots, V_k)$ a partition of $V$. Each subset $V_i$ of $\Pi$ is called an \emph{obligation}. An \emph{Independent Dominating set with Obligation} (\IDO) $D$ in an instance $(G, \Pi)$ is an independent dominating set of $G$ with the additional property that if a vertex $u$ of obligation $V_i$ is in $D$, then \emph{all} the others vertices of $V_i$ must also be in $D$; i.e., for all $i=1,\dots,k$, either $V_i\cap D=\emptyset$ or $V_i \subseteq D$ (we say that $D$ \emph{respects} the obligations). Note that when each obligation of $\Pi$ is a singleton, an \IDO is just an independent dominating set of $G$ that can be constructed with a greedy algorithm. Among other things, we show that determining if an instance $(G=(V,E),\Pi)$ has an \IDO is $NP$-complete, even if $G$ is a path (each vertex of $G$ exactly has two neighbours, except two extremities that have one), all the obligations are independent sets of $G$ and they all have the same constant size $\lambda > 1$. We also show that the problem is also $NP$-complete, even if $\Pi$ is composed of $\sqrt{|V|}$ independent obligations each of size $\sqrt{|V|}$ or if the diameter of $G$ is three. Our results clearly show that this problem is very difficult, even in extremely restricted instances. Hence, in a second part of the paper, we relax the condition to dominate all the vertices of $G$. However, we show that determining if $(G=(V, E), \Pi)$ contains an independent set $D$ respecting the obligations and dominating at least $3\sqrt{|V|} -2$ vertices of $G$ is $NP$-complete, even if $G$ is a collection of disjoint paths and obligations are all independent sets of $G$. On the positive side, we propose a greedy algorithm constructing a solution dominating at least $2\sqrt{|V|} - 1$ vertices in any instance $(G=(V, E), \Pi)$ if all obligations of $\Pi$ are independent sets of $G$.

When modeling an application of practical relevance as an instance of a combinatorial problem X, we are often interested not merely in finding one optimal solution for that instance, but in finding a sufficiently diverse collection of good solutions. In this work we initiate a systematic study of diversity from the point of view of fixed-parameter tractability theory. First, we consider an intuitive notion of diversity of a collection of solutions which suits a large variety of combinatorial problems of practical interest. We then present an algorithmic framework which --automatically-- converts a tree-decomposition-based dynamic programming algorithm for a given combinatorial problem X into a dynamic programming algorithm for the diverse version of X. Surprisingly, our algorithm has a polynomial dependence on the diversity parameter., Comment: Accepted to Twenty-Ninth International Joint Conference on Artificial Intelligence, {IJCAI} 2020, 16 pages

International audience; We study the complexity of regular matching and inclusion for compressed tree patterns with context variables subject to regular constraints. Context variables with regular constraints permit to properly generalize on unranked tree patterns with hedge variables. Regular inclusion on unranked tree patterns is relevant to certain query answering on Xml streams with references. We show that regular matching and inclusion with regular constraints can be reduced in polynomial time to the corresponding problem without regular constraints.

International audience; Massive biological datasets are available in various sources. To answer a biological question (e.g., ''which are the genes involved in a given disease?''), life scientists query and mine such datasets using various techniques. Each technique provides a list of results usually ranked by importance (e.g., a list of ranked genes). Combining the results obtained by various techniques, that is, combining ranked lists of elements into one list of elements is of paramount importance to help life scientists make the most of various results and prioritize further investigations. Rank aggregation techniques are particularly well-fitted with this context as they take in a set of rankings and provide a consensus, that is, a single ranking which is the ''closest'' to the input rankings. However, (i) the problem of rank aggregation is NP-hard in most cases (using an exact algorithm is currently not possible for more than a few dozens of elements) and (ii) several (possibly very different) exact solutions can be obtained. As answer to (i), many heuristics and approximation algorithms have been proposed. However, heuristics cannot guarantee how far from an exact solution the consensus ranking will be, and the approximation ratio of approximation algorithms dedicated to the problem is fairly high (not less than 3/2). No solution has yet been proposed to help true-users dealing with the problem encountered in point (ii). In this paper we present a complete system able to perform rank aggregation of massive biological datasets. Our solution is efficient as it is based on an original partitioning method making it possible to compute a high-quality consensus using an exact algorithm in a large number of cases. Our solution is robust as it clearly identifies for the user groups of elements whose relative order is the same in any optimal solution. These features provide answers to points (i) and (ii) and lie in mathematical bases offering guarantees on the computed result. Also, our solution is effective as it has been implemented into a real tool, ConquR-BioV2 is used for the life science community, and evaluated at large-scale using a very large number of datasets.

International audience; This paper investigates the so-called ODP-problem that has been formulated by Caragiannis and Micha [8]. This problem considers a setting with two election alternatives out of which one is assumed to be correct. In ODP, the goal is to organise the delegations in a social network in order to maximize the probability that the correct alternative is elected. While the problem is known to be computationally hard, we strengthen existing hardness results and show that the approximation hardness of ODP highly depends on the connectivity of the social network and the individual accuracies. Interestingly, under some assumptions, on either the accuracies of voters or the connectivity of the network, we obtain a polynomial-time 1/2-approximation algorithm. Lastly, we run extensive simulations and observe that simple algorithms relying on the abilities of liquid democracy outperform direct democracy on a large class of instances.

This paper considers the problem of scheduling a set of time-and energy-constrained preemptive tasks on a discrete time horizon. At each time period, the total energy required by the tasks that are in process can be provided by two energy sources: a reversible one and a non-reversible one. The non-reversible energy source can provide an unlimited amount of energy for a given period but at the expense of a time-dependent piecewise linear cost. The reversible energy source is a storage resource. The goal is to schedule each task preemptively inside its time window and to dispatch the required energy to the sources at each time period, while satisfying the reversible source capacity constraints and minimizing the total cost. We propose a mixed integer linear program of pseudo-polynomial size to solve this NP-hard problem. Acknowledging the limits of this model for problem instances of modest size, we propose an iterative decomposition matheuristic to compute an upper bound. The method relies on an efficient branch-and-price method or on a local search procedure to solve the scheduling problem without storage. The energy source allocation problem for a fixed schedule can in turn be solved efficiently by dynamic programming as a particular lot-sizing problem. We also propose a lower bound obtained by solving the linear programming relaxation of a new extended formulation by column generation. Experimental results show the quality of the bounds compared to the ones obtained using mixed integer linear program. Keywords Energy-aware scheduling piecewise linear costs storage resources matheuristic column generation lot sizing mixed integer programming MSC 90B05 MSC 90B30 MSC 90C39 MSC 90C59

International audience; ComplexityParser is a static complexity analyzer for Java programs providing the first implementation of a tier-based typing discipline. The input is a file containing Java classes. If the main method can be typed and, provided the program terminates, then the program is guaranteed to do so in polynomial time and hence also to have heap and stack sizes polynomially bounded. The application uses antlr to generate a parse tree on which it performs an efficient type inference: linear in the input size, provided that the method arity is bounded by some constant.

In this paper, we focus on the uniform bipartition problem in the population protocol model. This problem aims to divide a population into two groups of equal size. In particular, we consider the problem in the context of arbitrary communication graphs. As a result, we investigate the solvability of the uniform bipartition problem with arbitrary communication graphs when agents in the population have designated initial states, under various assumptions such as the existence of a base station, symmetry of the protocol, and fairness of the execution. When the problem is solvable, we present protocols for uniform bipartition. When global fairness is assumed, the space complexity of our solutions is tight.

International audience; This paper presents a new consensus algorithm, Proof of Usage (PoU), for the blockchain technology. This consensus is introduced for permis-sioned (or private) blockchains and is designed for a user-centric personal data market. This market is subject to specific regulations with which conventional blockchains fail to comply. Proof of Usage aims to promote a new paradigm dedicated to usage incentivization, valuation, and control of user data in various sectors, such as banking and insurance. Other consensuses such as Proof of Stake or historical Proof of Work do not encourage coin spending and usage (in fact, Proof of Stake promotes the opposite). However, the value of the currency mainly depends on its use. This paper first introduces a contextualization of blockchain technology and decentralized consensus models. The motivation is then discussed for a new model of personal data exchange in a decentralized but supervised environment. The PoU protocol and its process flow are defined in detail. Furthermore, the paper explores two different approaches regarding the reward mechanism and the incentive model. Finally, the paper focuses on security requirements and how PoU meets such requirements in a permissioned-based blockchain system.

International audience

International audience; We investigate the complexity of four decision problems dealing with the uniqueness of a solution in a graph: “Uniqueness of an r-Locating–Dominating Code with bounded size” (U-LDCr), “Uniqueness of an Optimal r-Locating–Dominating Code” (U-OLDCr), “Uniqueness of an r-Identifying Code with bounded size” (U-IdCr), “Uniqueness of an Optimal r-Identifying Code” (U-OIdCr), for any fixed integer r ≥ 1In particular, we describe a polynomial reduction from “Unique Satisfiability of a Boolean formula” (U-SAT) to U-OLDCr, and from U-SAT to U-OIdCr; for U-LDCr and U-IdCr, we can do even better and prove that their complexity is the same as that of U-SAT, up to polynomials. Consequently, all these problems are NP-hard, and U-LDCr and U-IdCr belong to the class DP.

We consider families of symmetric linear programs (LPs) that decide a property of graphs (or other relational structures) in the sense that, for each size of graph, there is an LP defining a polyhedral lift that separates the integer points corresponding to graphs with the property from those corresponding to graphs without the property. We show that this is equivalent, with at most polynomial blow-up in size, to families of symmetric Boolean circuits with threshold gates. In particular, when we consider polynomial-size LPs, the model is equivalent to definability in a non-uniform version of fixed-point logic with counting (FPC). Known upper and lower bounds for FPC apply to the non-uniform version. In particular, this implies that the class of graphs with perfect matchings has polynomial-size symmetric LPs, while we obtain an exponential lower bound for symmetric LPs for the class of Hamiltonian graphs. We compare and contrast this with previous results (Yannakakis 1991), showing that any symmetric LPs for the matching and TSP polytopes have exponential size. As an application, we establish that for random, uniformly distributed graphs, polynomial-size symmetric LPs are as powerful as general Boolean circuits. We illustrate the effect of this on the well-studied planted-clique problem. First author partially funded by European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement ERC-2014-CoG 648276 (AUTAR) and MICCIN grant TIN2016-76573-C2-1P (TASSAT3). The second author was partially supported by a Fellowship of the Alan Turing Institute under the EPSRC grant EP/N510129/1. The third author funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 795936.

Wireless technologies are very often used simultaneously for different applications in the same deployment area. This is more and more the case with the massive use of the Internet of Things. Very few of these technologies are designed to coexist efficiently. We concentrate in this paper on two technologies: IEEE 802.15.4 and IEEE 802.11. We consider the case where these two technologies are available on the same communicating node. We propose backoff algorithms for IEEE 802.15.4 (WPAN) that take into account information collected at a multi-interface node to improve coexistence with IEEE 802.11 (WLAN). The proposed mechanisms benefit from a virtual Clear Channel Assessment given by the WLAN interface to improve both network throughput and overall energy efficiency. Our simulation results show that the proposed mechanisms improve the basic CSMA/CA mechanism of WPAN by up to 26% of more packet delivery rate under a traffic load in WLAN that does not exceed 40%.

International audience; Swarm robotics takes inspiration from natural selforganizing systems such as social insects, fish schools or bird flocks, deriving rules to build robotic systems that are more robust, fault-tolerant and flexible than single robots. Over the last two decades, swarm robotics has made significant progress, providing concrete demonstrations on how robot swarms could address complex problems, and also contributing to a better understanding of how complex behaviors emerge in nature. However, as of today, only few published experiments have been able to demonstrate collective behavior in a number of robots that can effectively be compared to the size of biological swarms, and further research is needed before swarm robotics is mature enough to be employed in real world applications. Here we summarize the main lessons learned during the first two decades of research in the field and the main open problems still to be solved, such as the lack of dedicated hardware and software platforms, the need for reliable methodologies for swarm design, or how to make the best out of biological inspiration. We then present what we expect to be the main avenues of research in the future, and discuss how application demands may drive swarm robotics research, transitioning from abstract studies towards an engineering practice. Specifically, we identify precision agriculture, infrastructure inspection and maintenance, defense, space missions, entertainment and precision medicine as the application fields that will most likely drive the science and technology of robot swarms in the next three decades.

In this paper we study the quantum learnability of constant-depth classical circuits under the uniform distribution and in the distribution-independent framework of PAC learning. In order to attain our results, we establish connections between quantum learning and quantum-secure cryptosystems. We then achieve the following results. 1) Hardness of learning AC$^0$ and TC$^0$ under the uniform distribution. Our first result concerns the concept class TC$^0$ (resp. AC$^0$), the class of constant-depth and polynomial-sized circuits with unbounded fan-in majority gates (resp. AND, OR, NOT gates). We show that if there exists no quantum polynomial-time (resp. strong sub-exponential time) algorithm to solve the Ring Learning with Errors (RLWE) problem, then there exists no polynomial-time quantum learning algorithm for TC$^0$ (resp. AC$^0$) under the uniform distribution (even with access to quantum membership queries). The main technique in this result uses explicit pseudo-random functions that are believed to be quantum-secure to construct concept classes that are hard to learn quantumly under the uniform distribution. 2) Hardness of learning TC$^0_2$ in the PAC setting. Our second result shows that if there exists no quantum polynomial time algorithm for the LWE problem, then there exists no polynomial time quantum PAC learning algorithm for the class TC$^0_2$, i.e., depth-2 TC$^0$ circuits. The main technique in this result is to establish a connection between the quantum security of public-key cryptosystems and the learnability of a concept class that consists of decryption functions of the cryptosystem. This gives a strong (conditional) negative answer to one of the "Ten Semi-Grand Challenges for Quantum Computing Theory" raised by Aaronson [Aar05], who asked if AC$^0$ and TC$^0$ can be PAC-learned in quantum polynomial time., Comment: 43 pages. v2 fixes a mistake in the previous version of the paper and proves stronger results

Supplementary material (code, extra figures) available at https://github.com/soduco/paper-dgmm2021/; International audience; The digitization of historical maps enables the study of ancient, fragile, unique, and hardly accessible information sources. Main map features can be retrieved and tracked through the time for subsequent thematic analysis. The goal of this work is the vectorization step, i.e., the extraction of vector shapes of the objects of interest from raster images of maps. We are particularly interested in closed shape detection such as buildings, building blocks, gardens, rivers, etc. in order to monitor their temporal evolution. Historical map images present significant pattern recognition challenges. The extraction of closed shapes by using traditional Mathematical Morphology (MM) is highly challenging due to the overlapping of multiple map features and texts. Moreover, state-of-the-art Convolutional Neural Networks (CNN) are perfectly designed for content image filtering but provide no guarantee about closed shape detection. Also, the lack of textural and color information of historical maps makes it hard for CNN to detect shapes that are represented by only their boundaries. Our contribution is a pipeline that combines the strengths of CNN (efficient edge detection and filtering) and MM (guaranteed extraction of closed shapes) in order to achieve such a task. The evaluation of our approach on a public dataset shows its effectiveness for extracting the closed boundaries of objects in historical maps.

We consider the complexity of the Independent Set Reconfiguration problem under the Token Sliding rule. In this problem we are given two independent sets of a graph and are asked if we can transform one to the other by repeatedly exchanging a vertex that is currently in the set with one of its neighbors, while maintaining the set independent. Our main result is to show that this problem is PSPACE-complete on split graphs (and hence also on chordal graphs), thus resolving an open problem in this area. We then go on to consider the $c$-Colorable Reconfiguration problem under the same rule, where the constraint is now to maintain the set $c$-colorable at all times. As one may expect, a simple modification of our reduction shows that this more general problem is PSPACE-complete for all fixed $c\ge 1$ on chordal graphs. Somewhat surprisingly, we show that the same cannot be said for split graphs: we give a polynomial time ($n^{O(c)}$) algorithm for all fixed values of $c$, except $c=1$, for which the problem is PSPACE-complete. We complement our algorithm with a lower bound showing that $c$-Colorable Reconfiguration is W[2]-hard on split graphs parameterized by $c$ and the length of the solution, as well as a tight ETH-based lower bound for both parameters., 17 pages, 1 figure. STACS 2019

We consider the multi organization scheduling problem (MOSP) [19] : given N organizations owning, each of them, one set of tasks and machines, the aim is to compute a schedule which gathers all the tasks on all the machines, and such that the makespan is minimized. A rationality constraint must be fulfilled: no organization should increase its makespan (the completion time of its last task) compared to the case where it schedules its own tasks (and only its own tasks) on its own machines. We show that cooperation (sharing machines and tasks) can benefit to all the organizations simultaneously, since they may decrease their makespans by a factor of N. We present an algorithm which is ( 1 + ϵ ) -approximate, while the makespan of each organization is increased by a factor at most ( 1 + ϵ ) . We also study to which extent the rationality constraint (or a relaxed constraint) increases the makespan, compared to problem ( P | | C max ) where there is no such a constraint. Finally, we introduce a new problem, which focus on equity: the aim is to return a schedule which fulfills the rationality constraint and which maximizes the factor by which each organization has decreased its makespan. We give an optimal algorithm for this problem in a particular case, and show that it is NP-hard and hard to approximate in the general case. We complete this paper by an efficient heuristic for this problem.

Tseitin-formulas are systems of parity constraints whose structure is described by a graph. These formulas have been studied extensively in proof complexity as hard instances in many proof systems. In this paper, we prove that a class of unsatisfiable Tseitin-formulas of bounded degree has regular resolution refutations of polynomial length if and only if the treewidth of all underlying graphs $G$ for that class is in $O(\log|V(G)|)$. To do so, we show that any regular resolution refutation of an unsatisfiable Tseitin-formula with graph $G$ of bounded degree has length $2^{\Omega(tw(G))}/|V(G)|$, thus essentially matching the known $2^{O(tw(G))}poly(|V(G)|)$ upper bound up. Our proof first connects the length of regular resolution refutations of unsatisfiable Tseitin-formulas to the size of representations of \textit{satisfiable} Tseitin-formulas in decomposable negation normal form (DNNF). Then we prove that for every graph $G$ of bounded degree, every DNNF-representation of every satisfiable Tseitin-formula with graph $G$ must have size $2^{\Omega(tw(G))}$ which yields our lower bound for regular resolution., Comment: 20 pages including references

Reconfigurable computing system is emerging as an important computing system for satisfying the present and future computing demands in performance and flexibility. Extensible processor is a representative implementation of reconfigurable computing. In this context, custom instruction enumeration problem is one of the most computationally difficult problems involved in custom instruction synthesis for extensible processors. Custom instruction enumeration problem is essentially enumerating connected convex subgraphs from a given application graph. In this brief, we propose a provable optimal algorithm for enumerating connected convex subgraphs in acyclic digraphs in the sense of time complexity. The running time of the proposed algorithm is theoretically proved to be $O\left({\sum _{C\in CC(G)}(|V(C)|+|E(C)|)}\right)$ , where $CC(G)$ denotes the set of connected convex subgraphs in directed acyclic graph $G$ , $|V(C)|$ and $|E(C)|$ denote the number of vertices and the number of edges in subgraph $C$ respectively. Experimental results show that the proposed algorithm is more efficient than the state-of-the-art algorithms in terms of runtime.

International audience; We consider the rendezvous problem of two autonomous robots with very weak capacities. This problem is notoriously impossible to solve in the semi-synchronous execution model when robots are deterministic, oblivious, and their ego-centered coordinate system is fully symmetric.We show that if the robots disagree on the unit distance of their coordinate system, it becomes possible to solve rendezvous and agree on a final common location, without additional assumptions. We also generalize our scheme to solve gathering (that is, rendezvous of n ≥ 2robots) in the same setting, possibly starting from a bivalent configuration.

International audience; Generalized Spatial Modulation (GSM) is a promising technique for high data-rates systems where the complexity of the optimal joint detector based on the Maximum Likelihood (ML) criterion increases dramatically in terms of the modulation order and the number of activated transmit antennas. In this paper, a novel detection scheme for GSM systems denoted by O 2 SIC-ML is proposed to achieve the optimal performance with a controllable complexity-performance trade-off. The proposed detector is accompanied with ordering techniques for the transmit antenna combination and symbols to further reduce the complexity and improve the performance, respectively. The result reveals that O 2 SIC-ML allows reaching the non-linear ML detector performance with a 99% complexity reduction.

We define a continuation-passing style (CPS) translation for a typed λ-calculus with probabilistic choice, unbounded recursion, and a tick operator — for modeling cost. The target language is a (non-probabilistic) λ-calculus, enriched with a type of extended positive reals and a fixpoint operator. We then show that applying the CPS transform of an expression M to the continuation λ v . 0 yields the expected cost of M . We also introduce a formal system for higher-order logic, called EHOL, prove it sound, and show it can derive tight upper bounds on the expected cost of classic examples, including Coupon Collector and Random Walk. Moreover, we relate our translation to Kaminski et al.’s ert-calculus, showing that the latter can be recovered by applying our CPS translation to (a generalization of) the classic embedding of imperative programs into λ-calculus. Finally, we prove that the CPS transform of an expression can also be used to compute pre-expectations and to reason about almost sure termination.

International audience; This paper introduces the largest connected subgraph game played on an undirected graph G. In each round, Alice first colours an uncoloured vertex of G red, and then, Bob colours an uncoloured vertex of G blue, with all vertices initially uncoloured. Once all the vertices are coloured, Alice (Bob, resp.) wins if there is a red (blue, resp.) connected subgraph whose order is greater than the order of any blue (red, resp.) connected subgraph. We first prove that, if Alice plays optimally, then Bob can never win, and define a large class of graphs (called reflection graphs) in which the game is a draw. We then show that determining the outcome of the game is PSPACE-complete, even in bipartite graphs of small diameter, and that recognising reflection graphs is GI-hard. We also prove that the game is a draw in paths if and only if the path is of even order or has at least 11 vertices, and that Alice wins in cycles if and only if the cycle is of odd length. Lastly, we give an algorithm to determine the outcome of the game in cographs in linear time.

International audience; Observations show that some HPC applications periodically alternate between (i) operations (computations, local data-accesses) executed on the compute nodes, and (ii) I/O transfers of data and this behavior can be predicted beforehand. While the compute nodes are allocated separately to each application, the storage is shared and thus I/O access can be a bottleneck leading to contention. To tackle this issue, we design new static I/O scheduling algorithms that prescribe when each application can access the storage. To design a static algorithm, we emphasize on the periodic behavior of most applications. Scheduling the I/O volume of the different applications is repeated over time. This is critical since often the number of application runs is very high. In the following report, we develop a formal background for I/O scheduling. First, we define a model, bi-colored chain scheduling, then we go through related results existing in the literature and explore the complexity of this problem variants. Finally, to match the HPC context, we perform experiments based on use-cases matching highly parallel applications or distributed learning framework

accepted 2020-08-04; International audience; Recurrence quantification analysis (RQA) is an acknowledged method for the characterization of experimental time series. We propose a parametric version of RQA, pRQA, allowing a fast processing of spatial arrays of time series, once each is modeled by an autoregressive stochastic process. This method relies on the analytical derivation of asymptotic expressions for five current RQA measures as a function of the model parameters. By avoiding the construction of the recurrence plot of the time series, pRQA is computationally efficient. As a proof of principle, we apply pRQA to pattern recognition in multichannel electroencephalographic (EEG) data from a patient with a brain tumor.

International audience; One key problem in network analysis is the so-called influence maximization problem, which consists in finding a set $S$ of at most $k$ seed users, in a social network, maximizing the spread of information from $S$. This paper studies a related but slightly different problem: We want to find a set $S$ of at most $k$ seed users that maximizes the spread of information, when $S$ is added to an already pre-existing - but unknown - set of seed users $T$. We consider such scenario to be very realistic. Assume a central entity wants to spread a piece of news, while having a budget to influence $k$ users. This central authority may know that some users are already aware of the information and are going to spread it anyhow. The identity of these users being however completely unknown. We model this optimization problem using the Group Shapley value, a well-founded concept from cooperative game theory. While the standard influence maximization problem is easy to approximate within a factor $1-1/e-\epsilon$ for any $\epsilon>0$, assuming common computational complexity conjectures, we obtain strong hardness of approximation results for the problem at hand in this paper. Maybe most prominently, we show that it cannot be approximated within $1/n^{o(1)}$ under the Gap Exponential Time Hypothesis. Hence, it is unlikely to achieve anything better than a polynomial factor approximation. Nevertheless, we show that a greedy algorithm can achieve a factor of $\frac{1-1/e}{k}-\epsilon$ for any $\epsilon>0$, showing that not all is lost in settings where $k$ is bounded.

Access technologies are one of the fundamental assets of networking. Indeed, they are usually designed to optimize network performance in a given context and are therefore only well suited for targeted applications. Meanwhile, the paradigm of recent generation networks such as 5G is expected to revolutionize communication techniques by supporting a wide range of new applications that compel low latency and high data rates for both indoor and outdoor use cases. In this context, answering how should a user select an access technology at a given time while guaranteeing application needs, and leading to efficient utilization of network resources is an open research area. We survey in this paper decision-making algorithms for network selection in heterogeneous communication architectures. We also propose a taxonomy of these algorithms and carry out a discussion about common design challenges related to their applicability.

International audience; IEEE 802.11p standard enables the wireless technology that defines vehicular communications. However, IEEE 802.11p frame structure employing low pilot density is not enough to track the channel variations in high mobility scenarios, leading to significant performance degradation. Therefore, ensuring communication reliability in vehicular environments is considered as a major challenge. In this work, this challenge is tackled by employing deep learning into conventional channel estimation through utilizing deep neural networks (DNN) as an additional non-linear processing unit to correct the interpolation error of the time domain reliable test frequency domain interpolation (TRFI) channel estimates, besides learning higher order statistics of the estimated channel, resulting in a better channel tracking over time. Simulation results demonstrate the performance superiority of the proposed TRFI-DNN scheme over conventional schemes and the recently proposed DNN estimators with a significant computational complexity decrease, especially in high mobility vehicular scenarios.

Reliable communication is a fundamental primitive in distributed systems prone to Byzantine (i.e. arbitrary, and possibly malicious) failures to guarantee integrity, delivery and authorship of messages exchanged between processes. Its practical adoption strongly depends on the system assumptions. One of the most general (and hence versatile) such hypothesis assumes a set of processes interconnected through an unknown communication network of reliable and authenticated links, and an upper bound on the number of Byzantine faulty processes that may be present in the system, known to all participants. To this date, implementing a reliable communication service in such an environment may be expensive, both in terms of message complexity and computational complexity, unless the topology of the network is known. The target of this work is to combine the Byzantine fault-tolerant topol-ogy reconstruction with a reliable communication primitive, aiming to boost the efficiency of the reliable communication service component after an initial (expensive) phase where the topology is partially reconstructed. We characterize the sets of assumptions that make our objective achievable, and we propose a solution that, after an initialization phase, guarantees reliable communication with optimal message complexity and optimal delivery complexity.

International audience; Data rate management algorithms aim to perform a proper selection of the signal modulation and the coding rate to avoid the corruption of data bits. This paper describes a preliminary investigation on the bit corruption pattern related to the IEEE 802.11p standard. Measurements have been acquired with an experimental test-bed made up with a couple of software radios to perform white-box tests. Software radios are stationary and operate on the same channel without disturbances coming from concurrent communication. The aim of this experimental test-bed is to represent a static scenario where vehicles are stationary such as a crossroad situation. The data analysis shows that a data length reduction as an impact as much as a decrease of the data rate. A deeper analysis of the data bit corruption distribution highlights that some bits are more corrupted than others, rejecting the independent and identically distributed assumption for some situations. This opens a perspective to design algorithms dealing with multiple constraints, even if they are NP-complete.

We present a novel methodology for the automated resource analysis of non-deterministic, probabilistic imperative programs, which gives rise to a modular approach . Program fragments are analysed in full independence. Moreover, the established results allow us to incorporate sampling from dynamic distributions , making our analysis applicable to a wider class of examples, for example the Coupon Collector’s problem . We have implemented our contributions in the tool , exploiting a constraint-solver over iterative refineable cost functions facilitated by off-the-shelf SMT solvers. We provide ample experimental evidence of the prototype’s algorithmic power. Our experiments show that our tool runs typically at least one order of magnitude faster than comparable tools. On more involved examples, it may even be the case that execution times of seconds become milliseconds. At the same time we retain the precision of existing tools. The extensions in applicability and the greater efficiency of our prototype, yield scalability of sorts. This effects into a wider class of examples, whose expected cost analysis can be thus be performed fully automatically.

International audience; The paper details the first successful attempt at using model checking techniques to verify the correctness of distributed algorithms for robots evolving in a continuous environment. The study focuses on the problem of rendezvous of two robots with lights.There exist many different rendezvous algorithms that aim at finding the minimal number of colors needed to solve rendezvous in various synchrony models (e.g., FSYNC, SSYNC, ASYNC). While these rendezvous algorithms are typically very simple, their analysis and proof of correctness tend to be extremely complex, tedious, and error-prone as impossibility results are based on subtle interactions between the activation schedules of the robots.The paper presents a generic verification model that can be concretely expressed in available software model-checkers. In particular, we explain the subtle design decisions that allow to keep the search space finite and tractable, as well as prove several important theorems that support them. As a sanity check, we use the model to verify several known rendezvous algorithms in six different models of synchrony. In each case, we find that the results obtained from the model checker are consistent with the results known in the literature. The model checker outputs a counter-example execution in every case that is known to fail.In the course of developing and proving the validity of the model, we identified several fundamental theorems, including the ability for a well chosen algorithm and ASYNC scheduler to produce an emerging property of memory in a system of oblivious mobile robots, and why it is not a problem when robots executing the gathering algorithms are equipped with lights.

We study in this paper single-peakedness on arbitrary graphs. Given a collection of preferences (rankings of alternatives), we aim at determining a connected graph G on which the preferences are single-peaked, in the sense that all the preferences are traversals of G. Note that a collection of preferences is always single-peaked on the complete graph. We propose an Integer Linear Programming formulation (ILP) of the problem of minimizing the number of edges in G or the maximum degree of a vertex in G. We prove that both problems are NP-hard in the general case. However, we show that if the optimal number of edges is \(m-1\) (where m is the number of candidates) then any optimal solution of the continuous relaxation of the ILP is integer and thus the integrality constraints can be relaxed. This provides an alternative proof of the polynomial time complexity of recognizing single-peaked preferences on a tree. We prove the same result for the case of a path (an axis), providing here also an alternative proof of polynomiality of the recognition problem. Furthermore, we provide a polynomial time procedure to recognize single-peaked preferences on a pseudotree (a connected graph that contains at most one cycle). We also give some experimental results, both on real and synthetic datasets.

Let $\mathcal{C}$ be a plane curve given by an equation $f(x,y)=0$ with $f\in K[x][y]$ a monic squarefree polynomial. We study the problem of computing an integral basis of the algebraic function field $K(\mathcal{C})$ and give new complexity bounds for three known algorithms dealing with this problem. For each algorithm, we study its subroutines and, when it is possible, we modify or replace them so as to take advantage of faster primitives. Then, we combine complexity results to derive an overall complexity estimate for each algorithm. In particular, we modify an algorithm due to B\"ohm et al. and achieve a quasi-optimal runtime., Comment: Preliminary version

International audience; Possibilistic games with incomplete information (Π-games) constitute a suitable framework for the representation of ordinal games under incomplete knowledge. However, representing a Π-game in standard normal form requires an extensive expression of the utility functions and the possibility distribution, namely, on the product spaces of actions and types. In the present work, we propose a less costly view of Π-games, namely min-based polymatrix Π-games, which allows to concisely specify Π-games with local interactions. This framework allows, for instance, the compact representation of coordination games under uncertainty where the satisfaction of an agent is high if and only if her strategy is coherent with all of her neighbors, the game being possibly only incompletely known to the agents. Then, an important result of this paper is to show that a min-based polymatrix Π-game can be transformed, in polynomial time, into a (complete information) min-based polymatrix game with identical pure Nash equilibria. Finally, we show that the latter family of games can be solved through a MILP formulation. Experiments on variants of the GAMUT problems confirm the feasibility of this approach.

International audience; We consider the (parameterized) complexity of a cop and robber game on periodic, temporal graphs and a problem on periodic sequences to which these games relate intimately. In particular, we show that it is NP-hard to decide (a) whether there is some common index at which all given periodic, binary sequences are 0, and (b) whether a single cop can catch a single robber on an edge-periodic temporal graph. We further present results for various parameterizations of both problems and show that hardness not only applies in general, but also for highly limited instances. As one main result we show that even if the graph has a size-2 vertex cover and is acyclic in each time step, the cop and robber game on periodic, temporal graphs is NP-hard and W[1]-hard when parameterized by the size of the underlying input graph.

An automata network is a finite graph where each node holds a state from some finite alphabet and is equipped with an update function that changes its state according to the configuration of neighboring states. More concisely, it is given by a finite map \(f:Q^n\rightarrow Q^n\). In this paper we study how some (sets of) automata networks can be simulated by some other (set of) automata networks with prescribed update mode or interaction graph. Our contributions are the following. For non-Boolean alphabets and for any network size, there are intrinsically non-sequential transformations (i.e. that can not be obtained as composition of sequential updates of some network). Moreover there is no universal automaton network that can produce all non-bijective functions via compositions of asynchronous updates. On the other hand, we show that there are universal automata networks for sequential updates if one is allowed to use a larger alphabet and then use either projection onto or restriction to the original alphabet. We also characterize the set of functions that are generated by non-bijective sequential updates. Following Tchuente, we characterize the interaction graphs D whose semigroup of transformations is the full semigroup of transformations on \(Q^n\), and we show that they are the same if we force either sequential updates only, or all asynchronous updates.

We prove a Pumping Lemma for the noncooperative abstract Tile Assembly Model, a model central to the theory of algorithmic self-assembly since the beginning of the field. This theory suggests, and our result proves, that small differences in the nature of adhesive bindings between abstract square molecules gives rise to vastly different expressive capabilities. In the cooperative abstract Tile Assembly Model, square tiles attach to each other using multi-sided cooperation of one, two or more sides. This precise control of tile binding is directly exploited for algorithmic tasks including growth of specified shapes using very few tile types, as well as simulation of Turing machines and even self-simulation of self-assembly systems. But are cooperative bindings required for these computational tasks? The definitionally simpler noncooperative (or Temperature 1) model has poor control over local binding events: tiles stick if they bind on at least one side. This has led to the conjecture that it is impossible for it to exhibit precisely controlled growth of computationally-defined shapes. Here, we prove such an impossibility result. We show that any planar noncooperative system that attempts to grow large algorithmically-controlled tile-efficient assemblies must also grow infinite non-algorithmic (pumped) structures with a simple closed-form description, or else suffer blocking of intended algorithmic structures. Our result holds for both directed and nondirected systems, and gives an explicit upper bound of $(8|T|)^{4|T|+1}(5|\sigma| + 6)$, where $|T|$ is the size of the tileset and $|\sigma|$ is the size of the seed assembly, beyond which any path of tiles is pumpable or blockable., Comment: Accepted to STOC2020 - the 52nd Annual ACM Symposium on Theory of Computing

Discrete Mathematics & Theoretical Computer Science ; vol. 22 no. 1 ; Discrete Algorithms ; 1365-8050, Finding a solution to a Constraint Satisfaction Problem (CSP) is known to be an NP-hard task. This has motivatedthe multitude of works that have been devoted to developing techniques that simplify CSP instances before or duringtheir resolution.The present work proposes rigidly enforced schemes for simplifying binary CSPs that allow the narrowing of valuedomains, either via value merging or via value suppression. The proposed schemes can be viewed as parametrizedgeneralizations of two widely studied CSP simplification techniques, namely, value merging and neighbourhoodsubstitutability. Besides, we show that both schemes may be strengthened in order to allow variable elimination,which may result in more significant simplifications. This work contributes also to the theory of tractable CSPs byidentifying a new tractable class of binary CSP.

This papera describes a maintenance scheduling application, which was developed together with an industrial partner. This is a highly combinatorial decision process, to plan and schedule the work of a group of travelling repair technicians, which perform preventive and corrective maintenance tasks at customer locations. Customers are located both in urban areas, where many customers are in close proximity, and in sparsely populated rural areas, where the travel time between customer sites is significant. To balance the workload for the agents, we must consider both the productive working time, as well as the travel between locations. As the monolithic problem formulation is unmanageable, we introduce a problem decomposition into multiple sequential steps, that is compatible with current management practice. We present and compare different models for the solution steps, and discuss results on datasets provided by the industrial partner.

International audience; The modular exponentiation is crucial to the RSA cryptographic protocol, and variants inspired by the Montgomery ladder have been studied to provide more secure algorithms. In this paper, we abstract away the iterative conditional branching used in the Montgomery ladder, and formalize systems of equations necessary to obtain what we call the semi-interleaved and fully-interleaved ladder properties. In particular, we design fault-injection attacks able to obtain bits of the secret against semi-interleaved ladders, including the Montgomery ladder, but not against fully-interleaved ladders that are more secure. We also apply these equations to extend the Montgomery ladder for both the semi-and fully-interleaved cases, thus proposing novel and more secure algorithms to compute the modular exponentiation.