Search

An Election is a method of selection of individuals to hold the public office in democracy. Ballot is basically a piece of paper that is used to cast vote during election. In ballot paper voting system each voter uses a ballot paper which is not shared and basically it is a paper printed with the name and symbols of the candidates. The Electronic Voting Machine is basically a memory recorder which records the vote casted by the voters. In this paper, main advantages of E-voting systems for country is highlighted. For constructing E-voting systems, every countries need to do great attention to Verification and Validation requirements. In this research, E-voting scheme with face recognition using deep learning technique is proposed. The process of casting vote is accomplished by blockchain technology and blind signature mechanism. The main objective of the proposed scheme is to explore the positive effects of security and safety in online voting system. • The Election is a method of selection of individuals to hold the public office in democracy. • The Electronic Voting Machine is basically a memory recorder which records the vote casted by the voters. • The aim of the research is to E-voting scheme with face recognition using deep learning technique is proposed. • The main objective of the proposed scheme is to explore the positive effects of security and safety in online voting system. [ABSTRACT FROM AUTHOR]

The laws of physics play a crucial role in the security of quantum key distribution (QKD). This fact has often been misunderstood as if the security of QKD would be based only on the laws of physics. As the experts know well, things are more subtle. We review the progresses in practical QKD focusing on (I) the elements of trust that are common to classical and quantum implementations of key distribution; and (II) some threats to security that have been highlighted recently, none of which is unredeemable (i.e., in principle QKD can be made secure). This leads us to guess that the field, similar to non-quantum modern cryptography, is going to split in two directions: those who pursue practical devices may have to moderate their security claims; those who pursue ultimate security may have to suspend their claims of usefulness. [ABSTRACT FROM AUTHOR]

The generalized connectivity of a graph G , denoted as κ k (G) , is a generalization of the traditional connectivity and is a parameter to measure the capability of connecting multiple vertices in G. The divide-and-swap cube D S C n is a variant of the hypercube with a nice hierarchical structure and plentiful properties. This paper investigates the generalized connectivity on D S C n. We obtain the result κ 4 (D S C n) = d , where d = log 2 ⁡ n ≥ 1 , by the construction showing that there are d internally disjoint trees connecting any four arbitrary vertices of D S C n. As a corollary, one can directly obtain κ 3 (D S C n) = d. • The generalized k -connectivity κ k (G) is the maximum number of internally disjoint trees connecting any k vertices of G. • The divide-and-swap cube D S C n is a variant of the hypercube with a nice hierarchical structure and plentiful properties. • This paper obtains the result κ 4 (D S C n) = d , where d = log 2 ⁡ n ≥ 1. • As a corollary, we also obtain κ 3 (D S C n) = d. [ABSTRACT FROM AUTHOR]

Thorup and Zwick [1] introduced the notion of approximate distance oracles, a data structure that produces for an n -vertex, m -edge weighted undirected graph G = (V , E) , distance estimations in constant query time. They presented a distance oracle of size O (k n 1 + 1 / k) that given a pair of vertices u , v ∈ V at distance d (u , v) produces in O (k) time an estimation that is bounded by (2 k − 1) d (u , v) , i.e., a (2 k − 1) -multiplicative approximation (stretch). Thorup and Zwick [1] presented also a lower bound based on the girth conjecture of Erdős. For sparse unweighted graphs (i.e., m = O ˜ (n)) the lower bound does not apply. Pǎtraşcu and Roditty [2] used the sparsity of the graph and obtained a distance oracle that uses O ˜ (n 5 / 3) space, has O (1) query time and a stretch of 2. Pǎtraşcu et al. [3] presented infinitely many distance oracles with fractional stretch factors that for graphs with m = O ˜ (n) converge exactly to the integral stretch factors and the corresponding space bound of Thorup and Zwick. It is not known, however, whether graph sparsity can help to get a stretch which is better than (2 k − 1) using only O ˜ (k n 1 + 1 / k) space. In this paper we answer this open question and prove a separation between sparse and dense graphs by showing that using sparsity it is possible to obtain better stretch/space tradeoffs than those of Thorup and Zwick. We show that for every k ≥ 2 there is a distance oracle of size O ˜ (k m 1 + 1 / k) that produces in O (k) time an estimation d ⁎ (u , v) that satisfies d (u , v) ≤ d ⁎ (u , v) ≤ (2 k − 1) d (u , v) − 4 , for k > 2 , and d (u , v) ≤ d ⁎ (u , v) ≤ 3 d (u , v) − 2 , for k = 2. Another contribution of this paper is a refined stretch analysis of Thorup and Zwick distance oracles that allows us to obtain a better understanding of this important data structure. We present simple conditions for every w ∈ V that characterize the exact scenarios in which every query that involves w produces an estimation of stretch strictly better than 2 k − 1 , even in the case of dense graphs. We complement this contribution with an experiment on real world graphs. The main finding in the experiment is that different real world graphs are likely to satisfy the required conditions and hence the stretch of Thorup and Zwick distance oracles is much better than its worst case bound in these real world graphs. • Graph sparsity can help to get space-stretch tradeoffs for Distance Oracle which are strictly better than Thorup and Zwick space-stretch tradeoffs for general undirected graphs. • A refined stretch analysis of Thorup and Zwick Distance Oracle that characterizes several cases in which the stretch is strictly better than 2 k − 1. • An experiment on real world graphs shows that the cases characterized in the refined stretch analysis are quite frequent, and thus, in many real world graphs, the actual stretch is much better than the worst case stretch bound. [ABSTRACT FROM AUTHOR]

By using the PoW protocol, mining pools compete to successfully mine blocks to pursue rewards. Generally, the reward from a mined block includes the fixed block subsidies and the time-varying transaction fees. The latter are offered by the senders whose transactions are packaged into blocks and are increasing with the block size being larger. However, the larger block size brings the longer latency, resulting in a smaller probability of successfully mining. Therefore, decision on the optimal block size of a block to trade off two factors above mentioned is a complex and crucial problem for the mining pools. In this paper, we model the repeated mining competition dynamics among mining pools as an evolutionary game, in which each mining pool has two strategies: following the upper bound of block size B ¯ , or selecting a block size smaller than B ¯. Because of the bounded rationality, each mining pool pursues its evolutionary stable strategy (ESS) on block size by continuous learning and adjustments during the whole mining process. A framework is built for the general evolutionary game, based on which we then explore the existence and stability of the ESSs for a case of two mining pools. Numerical experiments using the real Bitcoin data are conducted to demonstrate the theoretical results in this paper. • A framework is built for the general evolutionary game. • Based on the analysis framework, we then explore the existence and stability of the ESSs for a case of two mining pools. • Numerical experiments using the real-world Bitcoin data are conducted to demonstrate the theoretical results in this paper. [ABSTRACT FROM AUTHOR]

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 Z 13 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., n > 6 f when Δ = 2 δ , and n > 8 f when Δ = δ , where Δ represents the period at which the Byzantine agents move and δ is the upper bound on the communication latency). [ABSTRACT FROM AUTHOR]

The traveling salesman problem (TSP) is one of the classic research topics in the field of operations research, graph theory and computer science. In this paper, we propose a generalized model of traveling salesman problem, denoted by generalized traveling salesman path problem. Let G = (V , E , c) be a weighted complete graph, in which c is a nonnegative metric cost function on edge set E , i.e., c : E → R +. The traveling salesman path problem aims to find a Hamiltonian path in G with minimum cost. Compared to the traveling salesman path problem, we are given extra vertex subset V ′ and edge subset E ′ in the problem proposed in this paper; its goal is to construct a path which traverses all the edges in E ′ while only needs to visit each vertex in V ′ exactly once. Based on integer programming, we give a mathematical model of the problem, and design a 1 + 5 2 -approximation algorithm for the problem by combining linear programming rounding strategy and a special graph structure. • In this paper, we consider a generalized model of traveling salesman problem. • Based on integer programming, we give a mathematical model of the problem. • Combining linear programming rounding strategy and a special graph structure, we propose a 1 + 5 2 -approximation algorithm. [ABSTRACT FROM AUTHOR]

This paper enriches a pre-existing decision algorithm, which in turn augmented a fragment of Tarski's elementary algebra with one-argument real functions endowed with a continuous first derivative. In its present (still quantifier-free) version, our decidable language embodies the addition of functions and multiplication of functions by scalars; the issue we address is the one of satisfiability. As regards real numbers, individual variables and constructs designating the basic arithmetic operations are available, along with comparison relators. As regards functions, we have variables of another sort, out of which compound terms are formed by means of constructs designating addition and differentiation. An array of predicates designates various relationships between functions, as well as function properties, that may hold over intervals of the real line; those are: function comparisons, strict and non-strict monotonicity / convexity / concavity, comparisons between the derivative of a function and a real-valued term. Our decision method consists in preprocessing the given formula into an equi-satisfiable quantifier-free formula of the elementary algebra of real numbers, whose satisfiability can then be checked by means of Tarski's decision method. No direct reference to functions will appear in the target formula, each function variable having been superseded by a collection of stub real variables; hence, in order to prove that the proposed translation is satisfiability-preserving, we must figure out a flexible-enough family of interpolating C 1 functions that can accommodate a model for the source formula whenever the target formula turns out to be satisfiable. With respect to the results announced in earlier papers of the same stream, a significant effort went into designing the family of interpolating functions so that it could meet the new constraints stemming from the presence of function addition (along with differentiation) among the constructs of our fragment of mathematical analysis. • A formal language RDF* concerned with differentiable real functions is proposed. • The class of differentiable functions treated is closed under addition. • The expressive power of RDF* is illustrated through a gallery of examples. • A satisfiability-preserving algorithm reducing RDF* formulas into an existential sentence of Tarskian algebra is presented. • The correctness of the reduction algorithm is reported. [ABSTRACT FROM AUTHOR]

The independent set polynomial is important in many areas of combinatorics, computer science, and statistical physics. For every integer Δ ≥ 2 , the Shearer threshold is the value λ ⁎ (Δ) = (Δ − 1) Δ − 1 / Δ Δ. It is known that for λ < − λ ⁎ (Δ) , there are graphs G with maximum degree Δ whose independent set polynomial, evaluated at λ , is at most 0. Also, there are no such graphs for any λ > − λ ⁎ (Δ). This paper is motivated by the computational problem of approximating the independent set polynomial when λ < − λ ⁎ (Δ). The key issue in complexity bounds for this problem is "implementation". Informally, an implementation of a real number λ ′ is a graph whose hard-core partition function, evaluated at λ , simulates a vertex-weight of λ ′ in the sense that λ ′ is the ratio between the contribution to the partition function from independent sets containing a certain vertex and the contribution from independent sets that do not contain that vertex. Implementations are the cornerstone of intractability results for the problem of approximately evaluating the independent set polynomial. Our main result is that, for any λ < − λ ⁎ (Δ) , it is possible to implement a set of values that is dense over the reals. The result is tight in the sense that it is not possible to implement a set of values that is dense over the reals for any λ > λ ⁎ (Δ). Our result has already been used in a paper with Bezáková (STOC 2018) to show that it is #P-hard to approximate the evaluation of the independent set polynomial on graphs of degree at most Δ at any value λ < − λ ⁎ (Δ). In the appendix, we give an additional incomparable inapproximability result (strengthening the inapproximability bound to an exponential factor, but weakening the hardness to NP-hardness). [ABSTRACT FROM AUTHOR]

A mixed dominating set of a graph G = (V , E) is a mixed set D of vertices and edges, such that for every edge or vertex, if it is not in D , then it is adjacent or incident to at least one vertex or edge in D. The mixed domination problem is to find a mixed dominating set with a minimum cardinality. It has applications in system control and some other scenarios and it is NP -hard to compute an optimal solution. This paper studies approximation algorithms and hardness of the weighted mixed dominating set problem. The weighted version is a generalization of the unweighted version, where all vertices are assigned the same nonnegative weight w v and all edges are assigned the same nonnegative weight w e , and the question is to find a mixed dominating set with a minimum total weight. Although the mixed dominating set problem has a simple 2-approximation algorithm, few approximation results for the weighted version are known. The main contributions of this paper include: 1. for w e ≥ w v , a 2-approximation algorithm; 2. for w e ≥ 2 w v , inapproximability within ratio 1.3606 unless P = N P and within ratio 2 under UGC; 3. for 2 w v > w e ≥ w v , inapproximability within ratio 1.1803 unless P = N P and within ratio 1.5 under UGC; 4. for w e < w v , inapproximability within ratio (1 − ϵ) ln ⁡ | V | unless P = N P for any ϵ > 0. [ABSTRACT FROM AUTHOR]

Let s (n) denote the sum of digits in the binary expansion of the integer n. Hare, Laishram and Stoll (2011) studied the number of odd integers such that s (n) = s (n 2) = k , for a given integer k ≥ 1. The remaining cases that could not be treated by these authors were k ∈ { 9 , 10 , 11 , 14 , 15 }. In this paper we show that there is only a finite number of solutions for k ∈ { 9 , 10 , 11 } and comment on the difficulties to settle the two remaining cases k ∈ { 14 , 15 }. A related problem is to study the solutions of s (n 2) = 4 for odd integers. Bennett, Bugeaud and Mignotte (2012) proved that there are only finitely many solutions and conjectured that n = 13 , 15 , 47 , 111 are the only solutions. In this paper, we give an algorithm to find all solutions with fixed sum of digits value, supporting this conjecture, as well as show related results for s (n 2) = 5. [ABSTRACT FROM AUTHOR]

This paper considers combinatorial optimization problems with an objective of type bottleneck, so the objective is to minimize the maximum cost among all elements in a feasible solution. For these problems, the sensitivity of an optimal solution to changes in parameters has received much less attention in existing studies than the computation of an optimal solution. This paper introduces methods for computing upper and lower tolerances which measure the amount of cost change needed in an element inside and outside an optimal solution, respectively, before that solution becomes non-optimal. Our main contribution is the development of efficient computation methods for bottleneck versions of the Linear Assignment Problem and the Minimum Spanning Tree Problem. • We study sensitivity of combinatorial problems with bottleneck objective (CBPs). • We investigate the range of element costs that keep current solutions optimal. • We derive algorithms for two CBPs in particular. • We determine the elements belonging to optimal solutions of CBPs efficiently. [ABSTRACT FROM AUTHOR]

In this paper, we extend the maximal independent set problem to two-stage stochastic case: given an independence system associated with one deterministic weight function and a random weight function, the goal is to find two nonoverlapping independent subsets from these two stages with the maximum total weight. In this paper, we study the submodularity of three kinds of two-stage independent set problems with max-weight. When the independent set problem is a matroid constraint, we can show its submodularity. However, neither submodular nor supermodular maximization problem can be obtained for the knapsack independent set problem by designing a counterexample. At last, we show that the robust two-stage stochastic maximum-weight uniform matroid problem can be formulated as a γ -submodular problem with cardinality constraint and also give a lower bound for γ. • The submodularity of two-stage stochastic matroid problem with maximum-weight is studied using properties of bases and the circuits in matroids. • An instance of two-stage stochastic knapsack problem which is not a submodular or supermodular maximization problem is proposed. • The robust two-stage stochastic max-weight problem with cardinality constraint can be formulated as a weakly submodular maximization problem. [ABSTRACT FROM AUTHOR]

A vertex coloring of a graph G = (V , E) is called an exact square coloring of G if any two vertices at distance exactly 2 receive different colors. The minimum number of colors required by an exact square coloring is called the exact square chromatic number of G and is denoted by χ [ # 2 ] (G). Given a graph G and a positive integer k , the Exact Square Coloring Problem is to decide whether G admits an exact square coloring using k colors. It is known that Exact Square Coloring Problem is NP-complete for chordal graphs. In this paper, we strengthen this result by proving that this problem remains NP-complete for undirected path graphs, which is a proper subclass of chordal graphs. However, we give linear time algorithms for computing the exact square chromatic number of proper interval graphs and threshold graphs, which are proper subclasses of chordal graphs. Moreover, for a proper interval graph G , we show that χ [ # 2 ] (G) ≤ 3. We also propose a polynomial time algorithm to produce an exact square coloring of a block graph G using at most χ [ # 2 ] (G) + 1 colors. Next, we study a lower bound of χ [ # 2 ] (G). A subset S of vertices of a graph G = (V , E) is called an exact square clique of G if the distance between any two vertices in S is exactly 2. The cardinality of the maximum exact square clique of G is called the exact square clique number of G and is denoted by ω [ # 2 ] (G). Clearly, ω [ # 2 ] (G) ≤ χ [ # 2 ] (G). Given a graph G and a positive integer k , the problem of deciding whether ω [ # 2 ] (G) is at least k , is known to be NP-complete for bipartite graphs and chordal graphs. In this paper, we strengthen these results by proving that this problem remains NP-complete for undirected path graphs, perfect elimination bipartite graphs, star-convex bipartite graphs and comb-convex bipartite graphs. We also compute the exact value of ω [ # 2 ] (G) for proper interval graphs, threshold graphs, block graphs and convex bipartite graphs. [ABSTRACT FROM AUTHOR]

• C -probe graphs are graphs having stable sets N for which edges can be added to obtain a supergraph in C. • A graph G is an (r , ℓ) -graph if V (G) can be partitioned into r independent sets and ℓ cliques. • A graph G is well-covered if every maximal independent set is also maximum. • This paper studies the complexity of recognizing probe graphs for the class of (r , ℓ) -well-covered graphs. Let C be a class of graphs. A graph G = (V , E) is C -probe if V (G) can be partitioned into two sets: non-probes N and probes P , where N is an independent set and new edges may be added between some non-probe vertices such that the resulting graph is in the class C. In this case, we say that (N , P) is a C - probe partition of G. In the Unpartitioned Probe problem for a graph class C we are given a graph G and asked whether G has a C -probe partition, i.e., such a problem consist of recognizing the class of C -probe graphs. A graph G = (V , E) is an (r , ℓ) -graph when V can be partitioned into (S 1 , S 2 , ... , S r , K 1 , K 2 , ... , K ℓ) such that S 1 , S 2 , ... , S r are independent sets, and K 1 , K 2 , ... , K ℓ are cliques. A graph G is well-covered if every maximal independent set is also maximum, and it is (r , ℓ) -well-covered if it is well-covered as well as an (r , ℓ) -graph. In this paper, we study the complexity of the Unpartitioned Probe problem for the class of (r , ℓ) -well-covered graphs. We classify all but the (2 , 0) and (1 , 2) cases. [ABSTRACT FROM AUTHOR]

Consider a Gaussian downlink between an access point with power budget P > 0 , and a set of users specified by their effective noises and rate demands. In order to control the decoding complexity and error propagation, an integer-valued access limit M > 0 is imposed on the number of superimposed users. For each subset S of users, its (total) power demand p (S) is a strictly increasing and nonseparable function of the effective noises and rate demands of users in S. A subset S of users is feasible if | S | ≤ M and p (S) ≤ P. The goal is to select a feasible subset S of users whose total rate demand is maximized. In this paper, we show that this problem is NP-hard, and present a (1 − 1 / e) -approximation algorithm for this problem. In addition, we also give several other approximation algorithms with trade-offs between accuracy and efficiency. • The Gaussian downlink user selection problem studied in this paper is an NP-hard maximization problem. • The first 1 2 (1 − 1 / e) -approximation algorithm takes the relaxation/extraction approach. • A better algorithm utilizes partial enumeration for reducing the extraction loss, and achieves (1 − 1 / e) -approximation factor. • The paper is concluded with a summary of the general algorithmic framework and some open problems for further studies. [ABSTRACT FROM AUTHOR]

For a graph G = (V , E) , a subset D of vertex set V , is a dominating set of G if every vertex not in D is adjacent to at least one vertex of D. A dominating set D of a graph G with no isolated vertices is called a paired dominating set (PD-set) , if the subgraph induced by D in G has a perfect matching. The Min-PD problem requires to compute a PD-set of minimum cardinality. The decision version of the Min-PD problem is NP-complete even when G belongs to restricted graph classes such as bipartite graphs, chordal graphs etc. On the other side, the problem is efficiently solvable for many graph classes including interval graphs, strongly chordal graphs, permutation graphs etc. In this paper, we study the complexity of the problem in AT-free graphs and planar graphs. The class of AT-free graphs contains cocomparability graphs, permutation graphs, trapezoid graphs, and interval graphs as subclasses. We propose a polynomial-time algorithm to compute a minimum PD-set in AT-free graphs. In addition, we also present a linear-time 2-approximation algorithm for the problem in AT-free graphs. Further, we prove that the decision version of the problem is NP-complete for planar graphs, which answers an open question asked by Lin et al. (2015) [19] and (2020) [20]. Alvarado et al. (2015) [1] conjectured that given a graph G = (V , E) , it is NP-hard to decide whether γ (G) = γ p r (G). In this paper we settle this conjecture affirmatively. [ABSTRACT FROM AUTHOR]

The influence maximization problem aims to find some seeds which can cause the maximum influence spread results in a social network. Most researches focus on the non-adaptive strategies, in which all seeds are selected at once. For the non-adaptive strategies, the seeds may influence other seeds in the influence spread process and make the waste of budget. This paper considers the adaptive strategies and studies the adaptive influence maximization and adaptive stochastic influence maximization in the general feedback model. These problems select seeds adaptively, and it completes each selection after the fixed observation time-step. In this paper, we utilize the adaptive greedy to solve these problems and propose a theoretical analysis by introducing a comparative factor. In addition, we present the feasible approximation algorithm using the reverse sampling technique. Finally, we carry out experiments on three networks to show the efficiency of adaptive strategies. • We study the adaptive influence maximization problem under a general model. • We propose a comparative factor and obtain the approximation ratio of an adaptive greedy algorithm. • We not only consider the problem with cardinality constraint but also the knapsack constraint. • We conduct several experiments on three real datasets to show the effectiveness of adaptive methods. [ABSTRACT FROM AUTHOR]

A trigraph is a graph where each pair of vertices is labelled either 0 (a non-arc), 1 (an arc) or ⋆ (both an arc and a non-arc). In a series of papers, Hell and co-authors (see for instance [P. Hell, 2014 [21] ]) proposed to study the complexity of homomorphisms from graphs to trigraphs, called Matrix Partition Problems , where arcs and non-arcs can be both mapped to ⋆-arcs, while a non-arc cannot be mapped to an arc, and vice-versa. Even though Matrix Partition Problems are generalisations of Constraint Satisfaction Problems (CSPs) , they share with them the property of being "intrinsically" combinatorial. So, the question of a possible P-time vs NP-complete dichotomy is a very natural one and was raised in Hell et al.'s papers. We propose a generalisation of Matrix Partition Problems to relational structures and study them with respect to the question of a dichotomy. We first show that trigraph homomorphisms and Matrix Partition Problems are P-time equivalent, and then prove that one can also restrict (with respect to having a dichotomy) to relational structures with a single relation. Failing in proving that Matrix Partition Problems on directed graphs are not P-time equivalent to Matrix Partitions on relational structures, we give some evidence that it might be unlikely by formalising the reductions used in the case of CSPs and by showing that such reductions cannot work for the case of Matrix Partition Problems. We then turn our attention to Matrix Partition problems that can be described by finite sets of (induced-subgraph) obstructions. We show, in particular, that any such problem has finitely many minimal obstructions if and only if it has finite duality. We conclude by showing that on trees (seen as trigraphs) it is NP-complete to decide whether a given tree has a homomorphism to another input trigraph. The latter shows a notable difference on tractability between CSP and Matrix Partition Problems as it is well-known that CSP is tractable on the class of trees. [ABSTRACT FROM AUTHOR]

Cellular automata are a famous model of computation, yet it is still a challenging task to assess the computational capacity of a given automaton; especially when it comes to showing negative results. In this paper, we focus on studying this problem via the notion of CA intrinsic simulation. We say that automaton A is simulated by B if each space-time diagram of A can be, after suitable transformations, reproduced by B. We study affine automata – i.e., automata whose local rules are affine mappings of vector spaces. This broad class contains the well-studied cases of linear automata. The main result of this paper shows that (almost) every automaton affine over a finite field F p can only simulate affine automata over F p. We discuss how this general result implies, and widely surpasses, limitations of linear and additive automata previously proved in the literature. We provide a formalization of the simulation notions into algebraic language and discuss how this opens a new path to showing negative results about the computational power of cellular automata using deeper algebraic theorems. [ABSTRACT FROM AUTHOR]

In the famous paper in which he introduced what is now known as the Turing machine, Alan Turing gave a definition of computable real numbers under which it turns out that multiplication by 3 is uncomputable. This shortcoming vanished in a Correction to his paper that Turing himself published shortly afterwards, but it clearly illustrates the subtlety of defining computability issues correctly. In this paper, we give the name "printable" to real numbers that Turing originally called "computable", we recall what is now the generally accepted definition of computable real numbers (which is not quite Turing's amended definition, but is equivalent to it), and we contrast the two notions. Despite the fact that the multiplication by 3 of printable numbers is uncomputable, as opposed to the same operation on computable numbers, a real number is computable if and only if it is printable. The resolution of this apparent paradox is that no machine can transform the "computable" description of a real number to its "printable" description, as Turing proved in his Correction. Finally, we address the subtle issue of allowing or not the printable description of a real number to end with an infinite sequence of 9s (or of 1s in binary), which was left open by Turing in his Correction. Several of these results were already known, as they appear in scattered places, some in non-refereed publications, but we give a unified treatment with some different proofs and a historical perspective. • Alan Turing's original definition of computable real numbers was inadequate. • Turing's use of the word Entscheidungsproblem led us to invent the Druckproblem. • The correct definition of computable real numbers is very subtle. • All computable real numbers are printable, but this is inherently non-constructive. • Discontinuous functions of the real numbers on closed intervals are uncomputable. [ABSTRACT FROM AUTHOR]

The complexity of the list homomorphism problem for signed graphs appears difficult to classify. Existing results focus on special classes of signed graphs, such as trees [4] and reflexive signed graphs [25]. Irreflexive signed graphs are in a certain sense the heart of the problem, as noted by a recent paper of Kim and Siggers. We focus on a special class of irreflexive signed graphs, namely those in which the unicoloured edges form a spanning path or cycle, which we call separable signed graphs. We classify the complexity of list homomorphisms to these separable signed graphs; we believe that these signed graphs will play an important role for the general resolution of the irreflexive case. We also relate our results to a conjecture of Kim and Siggers concerning the special case of semi-balanced irreflexive signed graphs; we have proved the conjecture in another paper, and the present results add structural information to that topic. [ABSTRACT FROM AUTHOR]

Accordingly to Duchet (1987), the first paper of convexity on general graphs, in english, is the 1981 paper "Convexity in graphs". One of its authors, Frank Harary, introduced in 1984 the first graph convexity games, focused on the geodesic convexity, which were investigated in a sequence of five papers that ended in 2003. In this paper, we continue this research line, extend these games to other graph convexities, and obtain winning strategies and complexity results. Among them, we obtain winning strategies for general convex geometries and winning strategies for trees from the Sprague-Grundy theory on impartial games. We also obtain the first PSPACE-hardness results on convexity games, by proving that the normal play and the misère play of the impartial hull game on the geodesic convexity is PSPACE-complete even in graphs with diameter two. [ABSTRACT FROM AUTHOR]

The fair k -center problem has been paid lots of attention recently. In the fair k -center problem, we are given a set X of points in a metric space and a parameter k ∈ Z + , where the points in X are divided into several groups, and each point is assigned a color to denote which group it is in. The goal is to partition X into k clusters such that the number of cluster centers with each color is equal to a given value, and the k -center problem objective is minimized. In this paper, we consider the fair k -center problem with outliers and capacity constraints, denoted as the fair k -center with outliers (F k CO) problem and the capacitated fair k -center (CF k C) problem, respectively. The outliers constraints allow up to z outliers to be discarded when computing the objective function, while the capacity constraints require that each cluster has size no more than L. In this paper, we design an Fixed-Parameter Tractability (FPT) approximation algorithm and a polynomial approximation algorithm for the above two problems. In particular, our algorithms give (1 + ϵ) -approximations with FPT time for the F k CO and CF k C problems in doubling metric space. Moreover, we also propose a 3-approximation algorithm in polynomial time for the F k CO problem with some reasonable assumptions. [ABSTRACT FROM AUTHOR]

Watson-Crick D0L systems (WD0L systems) are augmented variants of D0L systems defined over a DNA-like alphabet, where each letter has a complementary letter and this relation is symmetric. WD0L systems operate under a control that is inspired by the well-known phenomenon of Watson-Crick complementarity of the double helix of DNA. Depending on a trigger, the standard D0L rewriting step is applied either to the string or to its complementary string. In this paper, we examine extended networks of standard Watson-Crick D0L systems (ENSWD0L systems) with a variant of incomplete communication. An NWD0L system is a finite set of WD0L systems defined over a common DNA-like alphabet and operating in a synchronized manner. After rewriting their own strings in the WD0L manner, they communicate copies of certain generated strings (the so-called good strings) to the other nodes. In some previous papers, it was shown that ENSWD0L systems are computationally complete, and their computational power does not change if the communicated string is a non-empty prefix (non-empty suffix) of the generated string. We strengthen the previous results, namely we show that ENSWD0L systems are computationally complete even if the communicated string is an arbitrary substring of the generated string. • We define a new communication protocol for extended networks of standard Watson-Crick D0L systems (ENSWD0L systems). • We show that ENSWD0L systems communicating substrings are computationally complete. • Communication of incomplete strings does not decrease the generative power of ENSWD0L systems. [ABSTRACT FROM AUTHOR]

This paper presents a new McEliece-type cryptosystem using Gabidulin-Kronecker product codes in the rank metric. The contributions of this paper are as follows. Firstly, we propose a new Gabidulin-Kronecker product code which is a kind of block circulant code, and give an efficient decoding algorithm. Secondly, we design a one-way secure public key encryption scheme based on the Gabidulin-Kronecker product codes. Thirdly, we obtain an IND-CCA2 secure public key encryption scheme by converting our one-way secure public key encryption scheme under the hardness assumption of the RSD Dual Problem. In terms of efficiency, our scheme has a smaller public key size by taking advantage of the block circulant structure. For 128-bit security, the public key size of our proposal is 13% of Lau-Tan's cryptosystem (in the rank metric), and 19% of BIKE (in the Hamming metric). In terms of security, our scheme can resist Overbeck attack, Coggia-Couvreur attack and Sendrier attack. [ABSTRACT FROM AUTHOR]

In the paper of Manuel et al. [10] the minimum wirelength of embedding hypercube into cylinder was given as a conjecture. We show that Gray code embedding is an optimal strategy for the conjecture. In the paper, we prove the lower bound of the wirelength as two parts respectively, one of which is studied by the edge isoperimetric problem (EIP) related to the type sequence. The technique is totally different from the previous work in Refs. [10,11,1,6]. [ABSTRACT FROM AUTHOR]

• Eulerian trails are classical and important objects in theoretical computer science field. • Enumeration of Eulerian trails is known to be #P-complete. • Although the existence of an algorithm with linear time per output is known, the existence of a faster algorithm is open. • This paper shows optimal algorithms for Eulerian trails which run in constant time per solution on average. In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Two Eulerian trails are said to be edge-distinct if the edge sequences are not identical, and they are said to be vertex-distinct if the vertex sequences are not identical. To solve these problems, we propose optimal enumeration algorithms that run in O (N + m) total time, where N is the number of solutions and m is the number of edges in an input connected graph. The proposed algorithms are based on the reverse search technique introduced by [Avis and Fukuda, DAM 1996], and the push-out amortization technique introduced by [Uno, WADS 2015]. [ABSTRACT FROM AUTHOR]

Connectivity of a connected graph G , κ (G) , is an important index in exploring network topology which is the minimal number of vertices that need to be removed to separate G into disconnected or trivial. Let G 0 , G 1 , ... , G m − 1 be m connected graphs of the same order. A matching composition network G is constructed by adding an arbitrary perfect matching between G 0 and G 1. For m ≥ 3 , a cycle composition network H is constructed by adding an arbitrary perfect matching between G i and G i + 1 (mod m) for each 0 ≤ i ≤ m − 1. This construction has been so widely used in literature to build networks in which fault diagnosability can be studied, that it is worth to study their connectivity in detail, this is the main purpose of this paper. In this paper, we determine (1) κ (G) = δ (G) if κ (G 0) + κ (G 1) ≥ δ (G) ; otherwise, κ (G) ≥ κ (G 0) + κ (G 1) , and (2) κ (H) = δ (H) if ∑ i = 0 m − 1 κ (G i) ≥ δ (H) ; otherwise, κ (H) ≥ ∑ i = 0 m − 1 κ (G i). Examples show those bounds are tight. We then generalize these examples to a general composition using matchings on which we propose a conjecture on the connectivity and prove it for an important particular case. [ABSTRACT FROM AUTHOR]

• We present a fully abstract encoding of the lambda-calculus in the pi-calculus. • We apply a recent technique of unique solution of equations to establish completeness of the encoding. • We revisit the original encoding of the call-by-value lambda-calculus due to Milner, show some shortcomings, and study two approaches to overcome these shortcomings. We study Milner's encoding of the call-by-value λ -calculus into the π -calculus. We show that, by tuning the encoding to two subcalculi of the π -calculus (Internal π and Asynchronous Local π), the equivalence on λ -terms induced by the encoding coincides with Lassen's eager normal-form bisimilarity, extended to handle η -equality. As behavioural equivalence in the π -calculus we consider contextual equivalence and barbed congruence. We also extend the results to preorders. A crucial technical ingredient in the proofs is the recently-introduced technique of unique solutions of equations, further developed in this paper. In this respect, the paper also intends to be an extended case study on the applicability and expressiveness of the technique. [ABSTRACT FROM AUTHOR]

• We add CUDA verification support to the VerCors verifier. • We verify data race-freedom and functional correctness of CUDA implementations of two parallel prefix sum algorithms. • We verify data race-freedom and functional correctness of CUDA implementations of stream compaction algorithm. GPUs are an important part of any High Performance Computing (HPC) architecture. To make optimal use of the specifics of a GPU architecture, we need programming models that naturally support the parallel execution model of a GPU. CUDA and OpenCL are two widely used examples of such programming models. Furthermore, we also need to redesign algorithms such that they adhere to this parallel programming model, and we need to be able to prove the correctness of these redesigned algorithms. In this paper we study two examples of such parallelized algorithms, and we discuss how to prove their correctness (data race freedom and (partial) functional correctness) using the VerCors program verifier. First of all, we prove the correctness of two parallel algorithms solving the prefix sum problem. Second, we show how such a prefix sum algorithm is used as a basic block in a stream compaction algorithm, and we prove correctness of this stream compaction algorithm, taking advantage of the earlier correctness proof for the prefix sum algorithm. The proofs as described in this paper are developed over the CUDA implementations of these algorithms. In earlier work, we had already shown correctness of a more high-level version of the algorithm. This paper discusses how we add support to reason about CUDA programs in VerCors, and it then shows how we can redo the verification at the level of the CUDA code. We also discuss some practical challenges that we had to address to prove correctness of the actual CUDA-level verifications. [ABSTRACT FROM AUTHOR]

• We show that the Independant Dominating set with Obligations problem is NPC in various cases including paths. • We approach the IDO problem according to the topology of the graph and the properties of the obligations. • We characterize the PIDO problem where the solution does not have to dominate all the vertices of the graphs. • We show that determining if a solution can dominate a square root factor of the vertices for the PIDO problem is NPC. • We show cases where PIDO problem is polynomial and propose a polynomial algorithm to solve them. A subset D ⊆ V is an independent (or stable) dominating set of a graph G = (V , E) if D is an independent set (i.e., there are 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 a partition Π = (V 1 , ... , V k) of V. Each subset V i of Π is called an obligation. An Independent Dominating set with Obligations (IDO) D in an instance (G , Π) is an independent dominating set of G with the additional property that if a vertex u that belongs to the obligation V i is in D , then all the other vertices of V i must also be in D (we say that D respects the obligations). Note that when each obligation of Π 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 the problem of determining whether an instance (G = (V , E) , Π) has an IDO is NP -complete, even if G is a path, if all the obligations are independent sets of G , and if they all have the same constant size λ > 1. We also show that the problem is NP -complete, even if Π is composed of | V | independent obligations each of size | V | or if the diameter of G is three. Our results clearly show that this problem is very difficult, even for 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 whether (G = (V , E) , Π) contains an independent set D respecting the obligations and dominating at least 3 | 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 | V | − 1 vertices in any instance (G = (V , E) , Π) if all obligations of Π are independent sets of G. [ABSTRACT FROM AUTHOR]

The coordination among drones and ground vehicles for last-mile delivery has gained significant interest in recent years. In this paper, we study multiple drone delivery scheduling problem (MDSP) [1] for last-mile delivery, where we have a set of drones with an identical battery budget and a set of delivery locations; along with profit for delivery, cost, and delivery time intervals. The objective of the MDSP is to find conflict-free schedules for each drone such that the total profit gained is maximum subject to the battery constraint of the drones. This paper proposes an optimal pseudo-polynomial algorithm and a fully polynomial time approximation scheme (FPTAS) for the single drone delivery scheduling problem (SDSP). Also, we propose two approximation algorithms of factor 1 3 for the MDSP with some constraints on the number of drones. We formulate the problem for the heterogeneous case, where the drones have non-identical battery capacities, and propose a 1 6 ρ -approximation algorithm, where ρ is the ratio between the minimum and maximum battery capacity of the drones. • An optimal pseudo-polynomial algorithm and FPTAS for the single drone delivery scheduling problem is proposed. • Two approximation algorithms for the multiple drone delivery scheduling problem are proposed. • An approximation algorithm for the multiple heterogeneous drone delivery scheduling problem is proposed. • We analyzed the approximation factors of all the aforementioned proposed algorithms and time complexities. [ABSTRACT FROM AUTHOR]

Modern distributed systems are becoming pervasive and increasingly provided with adaptation, (self-)reconfiguration and mobility capability. On one side, to face the challenges of the highly dynamic environments where they are deployed. On the other side, to keep production/maintenance costs down. Therein lies the increasing demand for formal models encompassing all of these aspects (besides concurrency). Hardly any of the classical formalisms like Petri Nets, Automata, and Process Algebra, even though powerful, permits designers to easily specify dynamic structural changes to systems and evaluate their impact on system behaviour. That has led to several extensions of classical formal models (e.g., the Pi calculus or the Nets-within-Nets paradigm) rarely accompanied by suitable analysis techniques. A recent formalization of a class of Rewritable Place-Transition Nets (RwPT) in Maude has proved potentially convenient to specify dynamically reconfigurable systems. Concerning analogous proposals, the RwPT formalism provides more abstraction/flexibility in modelling and efficiency in analysis. Nevertheless, its ability to scale the size of distributed systems built of several similar (nested) components is limited. This paper presents a compositional approach to define large RwPT models in a typical algebraic way and to exploit the modular structure of models during the analysis: Symmetries are implicitly captured by composite node-labelling (reflecting the model's hierarchical structure) that is preserved by net rewrites. A distributed, gracefully degrading production system is used as a case study. Experimental evidence points out the dramatic impact of the approach against a non-modular one and the advantages over alternative techniques. Even if the emphasis is on state-space-based verification, the paper shows the convenience of combining it with structural analysis, which is typical of Petri nets as well. For that purpose, rewrite-rule abstractions are given in the form of guidelines. [ABSTRACT FROM AUTHOR]

There are many infinite families of 2-designs and 3-designs supported by linear codes in the literature. Recently, several infinite families of 4-designs from linear codes were discovered. But no infinite family of linear codes supporting an infinite family of nontrivial simple 5-designs is reported in the literature. It is not easy to construct 5-designs from sporadic codes. Only a small number of sporadic 5-designs supported by linear codes are available in the literature. In this paper, we construct eight 5-designs from some lifted codes of some known linear codes. • There are many infinite families of 2-designs and 3-designs supported by linear codes in the literature. • Recently, several infinite families of 4-designs from linear codes were discovered. • But no infinite family of linear codes supporting an infinite family of nontrivial simple 5-designs is reported in the literature. • It is not easy to construct 5-designs from sporadic codes. Only a small number of sporadic 5-designs supported by linear codes are available in the literature. • In this paper, we construct eight new 5-designs from some lifted codes of some known linear codes. [ABSTRACT FROM AUTHOR]

Syntactic models constitute one of the main areas of mathematical studies on picture array generation. A number of 2D grammar models have been proposed with motivation from a variety of applications. Parallel Contextual Array Insertion Deletion Grammar (PCAIDG) and Pure 2D Context-Free Grammar (P2DCFG) are two such 2D grammars. In the case of P2DCFG, two new variants are studied with interesting properties. In this paper we show that PCAIDG has higher generative power than the generative powers of two variants of P2DCFG. Further, P systems associated with the grammars PCAIDG, P2DCFG and their variants are considered in the literature. In this paper, we show that the generative power of Parallel Contextual Array Insertion Deletion P System (PCAIDPS) is greater than the generative power of the P system associated with a variant of P2DCFG. [ABSTRACT FROM AUTHOR]

Sorting is a fundamental component in many different applications including web indexing engines, geographic information systems, data mining and database systems. However, the existing optimal algorithms still cause huge costs when the input data becomes very large. Thus, the approximate sorting for big data is considered in this paper. The goal of approximate sorting for big data is to generate an approximate sorted result, but using less CPU and I/O cost. For big data, we consider the approximate sorting and applications for approximate sorted results in I/O model. The quality of approximate sorting results is usually measured by the distance metrics on permutation space. However, the existing metrics on permutation space are not available for external approximate sorting algorithms. Thus, we propose a new kind of metric named External metric, which ignores the errors and dislocations that happened in each I/O block. The External metric of Spearman's footrule metric is named as External Spearman's footrule metric (short as ESP metric), which is analyzed in this paper. Furthermore, to facilitate a better evaluation of the approximate sorted result, we propose a new metric, named as errors , which directly states the number of dislocation of the elements. The External errors are also considered in this paper. Then, according to the rate-distortion relationship under these two metrics, the lower bound of these two metrics on external approximate sorting problem with t I/O operations is proved. We propose a k-passes external approximate sorting algorithm, named as EASORT, and prove that EASORT is asymptotically optimal under ESP metric. Finally, we consider the applications on approximate sorting results. An index for the approximate sorted result is proposed. The single and range query on approximate sorted result using this index are also analyzed. Further, the sort-merge join on two relations, where one of the relations is approximate sorted or both relations are approximate sorted, are all discussed in this paper. • This paper first discusses the approximate sorting in I/O model. • This paper proposes a new external metric to evaluate the approximate sorted result. • This paper analyzes the lower bound of two metrics of approximate sorted result. • This paper proposes a new external approximate sorting algorithm. • This paper analyzes the applications on approximate sorted result. [ABSTRACT FROM AUTHOR]

• In identity-based encryption (IBE), a key generation center (KGC), which generates secret keys for a given identity, has the power to decrypt all ciphertexts. • This key escrow problem is one of the main barriers to the widespread real-world use of IBE. • In this paper we formally define an IBE scheme that resolves the key escrow problem. • We present two instantiations in our new security model: a lattice-based construction and a pairing-based construction. The key escrow problem is one of the main barriers to the widespread real-world use of identity-based encryption (IBE). Specifically, a key generation center (KGC), which generates secret keys for a given identity, has the power to decrypt all ciphertexts. At PKC 2009, Chow defined a notion of security against the KGC, that relies on assuming that it cannot discover the underlying identities behind ciphertexts. However, this is not a realistic assumption since, in practice, the KGC manages an identity list, and hence it can easily guess the identities corresponding to given ciphertexts. Chow later amended this issue by introducing a new entity called an identity-certifying authority (ICA) and proposed an anonymous key-issuing protocol. Essentially, this allows the users, KGC, and ICA to interactively generate secret keys without users ever having to reveal their identities to the KGC. Unfortunately, since Chow separately defined the security of IBE and that of the anonymous key-issuing protocol, his IBE definition did not provide any formal treatment when the ICA is used to authenticate the users. Effectively, all of the subsequent works following Chow lack the formal proofs needed to determine whether or not it delivers a secure solution to the key escrow problem. In this paper, based on Chow's work, we formally define an IBE scheme that resolves the key escrow problem and provide formal definitions of security against corrupted users, KGC, and ICA. Along the way, we observe that if we are allowed to assume a fully trusted ICA, as in Chow's work, then we can construct a trivial (and meaningless) IBE scheme that is secure against the KGC. Finally, we present two instantiations in our new security model: a lattice-based construction based on the Gentry–Peikert–Vaikuntanathan IBE scheme (STOC 2008) and Rückert's lattice-based blind signature scheme (ASIACRYPT 2010), and a pairing-based construction based on the Boneh–Franklin IBE scheme (CRYPTO 2001) and Boldyreva's blind signature scheme (PKC 2003). [ABSTRACT FROM AUTHOR]

In the degree-constrained graph orientation problem , the input is an unweighted, undirected graph G = (V , E) and nonnegative integers a v and b v (with a v ≤ b v) for each v ∈ V , and the objective is to assign a direction to every edge in E in such a way that for each v ∈ V , the number of outgoing edges in the resulting directed graph lies in the interval [ a v , b v ]. When such an orientation does not exist, it is desirable to find an orientation that best fits the condition instead. In this paper, we consider the problem of finding an orientation that minimizes the total penalty ∑ v ∈ V c v , where c v is a penalty incurred whenever a vertex v violates its degree constraints. As penalty functions, convex, concave, and step functions are considered in this paper. We show that the problem with any convex penalty function can be solved in O (| E | 1.5 min ⁡ { log ⁡ (| E | ⋅ C) , | E | 0.5 log ⁡ Δ log ⁡ | E | }) time, where Δ and C are the maximum degree and the largest magnitude of a penalty, respectively. In contrast, we show APX-hardness of the problem with step or concave functions. For trees and graphs with treewidth τ , the problem with any penalty function can be solved exactly in O (| V | log ⁡ Δ) time and O (τ 2 Δ 2 τ + 2 | V |) time, respectively. Finally, we consider the generalization of the problem to edge-weighted graphs and establish strong bounds on its inapproximability that hold even in the special case of stars. On the positive side, we can extend our algorithms for unweighted version of the problem to obtain pseudo-polynomial-time algorithms for the edge-weighted problem variant when restricted to trees and graphs with bounded treewidth. Also, we design a PTAS and a linear-time algorithm for stars with further restrictions on the degree constraints and edge weights. [ABSTRACT FROM AUTHOR]

This paper is a 'spiritual child' of the 2005 lecture notes Kindergarten Quantum Mechanics Coecke (2005) [24] , which showed how a simple, pictorial extension of Dirac notation allowed several quantum features to be easily expressed and derived, using language even a kindergartner can understand. Central to that approach was the use of pictures and pictorial transformation rules to understand and derive features of quantum theory and computation. However, this approach left many wondering 'where's the beef?' In other words, was this new approach capable of producing new results, or was it simply an aesthetically pleasing way to restate stuff we already know? The aim of this sequel paper is to say 'here's the beef!', and highlight some of the major results of the approach advocated in Kindergarten Quantum Mechanics, and how they are being applied to tackle practical problems on real quantum computers. Toward that end, we will focus mainly on what has become the Swiss army knife of the pictorial formalism: the ZX-calculus , a graphical tool for representing and manipulating complex linear maps on 2 N dimensional space. First we look at some of the ideas behind the ZX-calculus, comparing and contrasting it with the usual quantum circuit formalism. We then survey results from the past few years falling into three categories: (1) completeness of the rules of the ZX-calculus, (2) state-of-the-art quantum circuit optimisation results in commercial and open-source quantum compilers relying on ZX, and (3) the use of ZX in translating real-world stuff like natural language into quantum circuits that can be run on today's (very limited) quantum hardware. We also take the title literally, and outline an ongoing experiment aiming to show that ZX-calculus enables children to do cutting-edge quantum computing stuff. If anything, this would truly confirm that 'kindergarten quantum mechanics' wasn't just a joke. [ABSTRACT FROM AUTHOR]

Suppose an oracle knows a string S that is unknown to us and that we want to determine. The oracle can answer queries of the form "Is s a substring of S ?". In 1995, Skiena and Sundaram showed that, in the worst case, any algorithm needs to ask the oracle σ n / 4 − O (n) queries in order to be able to reconstruct the hidden string, where σ is the size of the alphabet of S and n its length, and gave an algorithm that spends (σ − 1) n + O (σ n) queries to reconstruct S. The main contribution of our paper is to improve the above upper-bound in the context where the string is compressible. We first present a universal algorithm that, given a (computable) compressor that compresses the string to τ bits, performs q = O (τ) substring queries; this algorithm, however, runs in exponential time. For this reason, the second part of the paper focuses on more time-efficient algorithms whose number of queries is bounded by specific compressibility measures. We first show that any string of length n over an integer alphabet of size σ with rle runs can be reconstructed with q = O (rle (σ + log ⁡ n rle)) substring queries in linear time and space. We then present an algorithm that spends q ∈ O (σ g log ⁡ n) substring queries and runs in O (n (log ⁡ n + log ⁡ σ) + q) time using linear space, where g is the size of a smallest straight-line program generating the string. [ABSTRACT FROM AUTHOR]

In this paper we present a series of results which show separations between the standard seeded model of self-assembly, Winfree's abstract Tile Assembly Model (aTAM), and the "seedless" 2-Handed Assembly Model (2HAM), which incorporates the dynamics of hierarchical self-assembly. In particular, we focus on the problem of self-assembling various shapes while minimizing the sizes of tile sets, or "programs", in each of these models in order to compare and contrast the models. A high-level overview of a subset of these results was presented in a paper by the authors in STACS 2013, but in this version we expand and improve the set of results related to showing separations between the two models according to their abilities to self-assemble various shapes. We exhibit classes of finite shapes that can be self-assembled more efficiently in each model. We also demonstrate infinite shapes that can self-assemble in one model but not in the other, as well as a shape which cannot self-assemble in either model. [ABSTRACT FROM AUTHOR]

Solid codes provide outstanding fault-tolerance when used for information transmission through a noisy channel involving not only symbol substitutions, but also synchronisation errors and black-outs. In this paper we provide an automaton theoretic characterisation of solid codes which takes this fault-tolerance into account. The fault-tolerance afforded by a solid code L can be summarised as follows: Consider messages, encoded using L , being sent through a noisy channel. Any code words in L , which are present in the received message, will be decoded correctly, unless they themselves happen to be the results of errors. Thus, errors in the received message will not lead to incorrect decodings of those parts which are error-free. In this paper we consider acceptors which are fault-tolerant in this sense when analysing such received messages. These acceptors characterise the class of solid codes. For finite solid codes an automaton characterisation was published in the sixties by Levenshtein and Romanov. The characterisation uses state-invariant finite-state transducers which act as decoders in such a way that an output is generated exactly when a code word has been read completely. State-invariance means that acceptance does not depend on the initial state — every state can be used as the initial state. The results of Levenshtein and Romanov depend strongly on the fact that the code is finite. In this paper we provide a general automaton theoretic characterisation of arbitrary solid codes without any such restriction. Moreover, the solid code is regular as a language if and only if the automaton used in the characterisation can be reduced to an equivalent finite automaton with equivalent properties. The main results of this paper are as follows: Every acceptor defines a solid code. For every solid code there is a fault-tolerant acceptor defining the code. Such acceptors expose the decomposition of potentially faulty received messages according to the code. For solid codes which are regular as languages these acceptors can be chosen to be finite while preserving all important combinatorial properties. Part of this work was presented at the 14th Journées Montoises of Theoretical Computer Science [32]. [ABSTRACT FROM AUTHOR]

Evolutionary algorithms (EAs) are general-purpose optimization algorithms, inspired by natural evolution. Recent theoretical studies have shown that EAs can achieve good approximation guarantees for solving the problem classes of submodular optimization, which have a wide range of applications, such as maximum coverage, sparse regression, influence maximization, document summarization and sensor placement, just to name a few. Though they have provided some theoretical explanation for the general-purpose nature of EAs, the considered submodular objective functions are defined only over sets or multisets. To complement this line of research, this paper studies the problem class of maximizing monotone submodular functions over sequences, where the objective function depends on the order of items. We prove that for each kind of previously studied monotone submodular objective functions over sequences, i.e., prefix monotone submodular functions, weakly monotone and strongly submodular functions, and DAG monotone submodular functions, a simple multi-objective EA, i.e., GSEMO, can always reach or improve the best known approximation guarantee after running polynomial time in expectation. Note that these best-known approximation guarantees can be obtained only by different greedy-style algorithms before. Empirical studies on various applications, e.g., accomplishing tasks, maximizing information gain, search-and-tracking and recommender systems, show the excellent performance of the GSEMO. [ABSTRACT FROM AUTHOR]

A subset M ⊆ E of edges of a graph G = (V , E) is called a m a t c h i n g if no two edges of M share a common vertex. Given a matching M in G , a vertex v ∈ V is called M -saturated if there exists an edge e ∈ M incident with v. A matching M of a graph G is called an acyclic matching if, G [ V (M) ] , the subgraph of G induced by the M -saturated vertices of G is an acyclic graph. Given a graph G , the Acyclic Matching problem asks to find an acyclic matching of maximum cardinality in G. The Decide-Acyclic Matching problem takes a graph G and an integer k and asks whether G has an acyclic matching of cardinality at least k. The Decide-Acyclic Matching problem is known to be NP -complete for general graphs as well as for bipartite graphs. In this paper, we strengthen this result by showing that the Decide-Acyclic Matching problem remains NP -complete for comb-convex bipartite graphs, star-convex bipartite graphs, and dually chordal graphs. On the positive side, we show that the Acyclic Matching problem is linear time solvable for split graphs, block graphs, and proper interval graphs. We show that the Acyclic Matching problem is hard to approximate within a factor of n 1 − ϵ for any ϵ > 0 unless P = NP. Also, we show that the Acyclic Matching problem is APX -complete for (2 k + 1) -regular graphs for every fixed integer k ≥ 3. [ABSTRACT FROM AUTHOR]

Widespread use of string solvers in the formal analysis of string-heavy programs has led to a growing demand for more efficient and reliable techniques which can be applied in this context. Designing practical algorithms for the (generally undecidable) satisfiability problem for systems of string constraints requires a deep understanding of the structure of constraints present in the targeted cases. In this paper, we first investigate relevant benchmarks containing regular expression membership predicates, extract a series of first order logic theories, and prove the decidability, respectively undecidability, of their satisfiability problem. Further, building on the theoretical results, we present a novel length-aware solving algorithm for the quantifier-free first-order theory over regular expression membership predicates and linear arithmetic over string length. We implement and evaluate this algorithm and related heuristics in the Z3 theorem prover. Besides the theoretical aspects leading to this algorithm, a crucial insight that underpins it is that real-world regex and string formulas contain a wealth of information about upper and lower bounds on lengths of strings, and such information can be used very effectively to simplify operations on automata representing regular expressions. Additionally, we present several novel general heuristics, such as the prefix/suffix method, that can be used to make a variety of regex solving algorithms more efficient in practice. We showcase the power of our algorithm and heuristics via an extensive empirical evaluation over a large and diverse benchmark of 57256 regex-heavy instances, almost 75% of which are derived from industrial applications or contributed by other solver developers. Our solver outperforms five other state-of-the-art string solvers over this benchmark. [ABSTRACT FROM AUTHOR]

Stackelberg pricing games are pricing problems over a set of items. One player, the leader , sets prices for the items and the second player, the follower , buys a subset of items at minimal total cost subject to feasibility constraints. The constraints are determined by an optimization problem. For example, the Stackelberg shortest path game is used to optimize the income from road tolls (cf. [21]). The items are edges in a network graph and the follower buys a subset of edges forming a path. The Stackelberg pricing games studied in the literature are formulated on top of covering problems. In this paper, we introduce pricing games based on packing problems. We are interested in the complexity of computing leader-optimal prices depending on different types of follower-constraints. We show that optimal prices can be computed in polynomial time if the follower-constraints are determined by the well-known interval scheduling problem. This problem is equivalent to the independent set problem on interval graphs. In case the follower-constraints are based on the independent set problem on perfect graphs or on the bipartite matching problem, we prove APX-hardness for the pricing problem. On a more general note, we prove Σ 2 p -completeness if the follower-constraints are given by a packing problem that is NP-complete, i.e., the leader's pricing problem is hard even if she has an NP-oracle at hand. [ABSTRACT FROM AUTHOR]

In this paper, we investigate the computational complexity of subgraph reconfiguration problems in directed graphs. More specifically, we focus on the problem of reconfiguring arborescences in a digraph, where an arborescence is a directed graph such that its underlying undirected graph forms a tree and all vertices have in-degree at most 1. Given two arborescences in a digraph, the goal of the problem is to determine whether there is a (reconfiguration) sequence of arborescences between the given arborescences such that each arborescence in the sequence can be obtained from the previous one by removing an arc and then adding another arc. We show that this problem can be solved in polynomial time, whereas the problem is PSPACE-complete when we restrict arborescences in a reconfiguration sequence to directed paths or relax to directed acyclic graphs. We also show that there is a polynomial-time algorithm for finding a shortest reconfiguration sequence between two spanning arborescences. [ABSTRACT FROM AUTHOR]