Search

The suffix array, perhaps the most important data structure in modern string processing, is often augmented with the longest common prefix (LCP) array which stores the lengths of the LCPs for lexicographically adjacent suffixes of a string. Together the two arrays are roughly equivalent to the suffix tree with the LCP array representing the tree shape. In order to better understand the combinatorics of LCP arrays, we consider the problem of inferring a string from an LCP array, i.e., determining whether a given array of integers is a valid LCP array, and if it is, reconstructing some string or all strings with that LCP array. There are recent studies of inferring a string from a suffix tree shape but using significantly more information (in the form of suffix links) than is available in the LCP array. We provide two main results. (1) We describe two algorithms for inferring strings from an LCP array when we allow a generalized form of LCP array defined for a multiset of cyclic strings: a linear time algorithm for binary alphabet and a general algorithm with polynomial time complexity for a constant alphabet size. (2) We prove that determining whether a given integer array is a valid LCP array is NP-complete when we require more restricted forms of LCP array defined for a single cyclic or non-cyclic string or a multiset of non-cyclic strings. The result holds whether or not the alphabet is restricted to be binary. In combination, the two results show that the generalized form of LCP array for a multiset of cyclic strings is fundamentally different from the other more restricted forms.

We introduce and study a class of optimization problems we call replenishment problems with fixed turnover times: a very natural model that has received little attention in the literature. Clients with capacity for storing a certain commodity are located at various places; at each client the commodity depletes within a certain time, the turnover time, which is constant but can vary between locations. Clients should never run empty. The natural feature that makes this problem interesting is that we may schedule a replenishment (well) before a client becomes empty, but then the next replenishment will be due earlier also. This added workload needs to be balanced against the cost of routing vehicles to do the replenishments. In this paper, we focus on the aspect of minimizing routing costs. However, the framework of recurring tasks, in which the next job of a task must be done within a fixed amount of time after the previous one is much more general and gives an adequate model for many practical situations. Note that our problem has an infinite time horizon. However, it can be fully characterized by a compact input, containing only the location of each client and a turnover time. This makes determining its computational complexity highly challenging and indeed it remains essentially unresolved. We study the problem for two objectives: min–avg minimizes the average tour cost and min–max minimizes the maximum tour cost over all days. For min–max we derive a logarithmic factor approximation for the problem on general metrics and a 6-approximation for the problem on trees, for which we have a proof of NP-hardness. For min–avg we present a logarithmic factor approximation on general metrics, a 2-approximation for trees, and a pseudopolynomial time algorithm for the line. Many intriguing problems remain open.

We present a spectral approach to design approximation algorithms for network design problems. We observe that the underlying mathematical questions are the spectral rounding problems, which were studied in spectral sparsification and in discrepancy theory. We extend these results to incorporate additional non-negative linear constraints, and show that they can be used to significantly extend the scope of network design problems that can be solved. Our algorithm for spectral rounding is an iterative randomized rounding algorithm based on the regret minimization framework. In some settings, this provides an alternative spectral algorithm to achieve constant factor approximation for the classical survivable network design problem, and partially answers a question of Bansal about survivable network design with concentration property. We also show many other applications of the spectral rounding results, including weighted experimental design and additive spectral sparsification., Comment: Improved bound on one-sided spectral rounding by a randomized swapping algorithm. Added the proof of the deterministic algorithm for additive sparsifers

We study the relation between latency and alphabet size in the context of Multicast Network Coding. Given a graph $G =$ (${V}$, E) representing a communication network, a subset $S \subseteq V$ of sources, each of which initially holds a set of information messages, and a set $ T\subseteq V$ of terminals; we consider the problem in which one wishes to design a communication scheme that eventually allows all terminals to obtain all the messages held by the sources. In this study we assume that communication is performed in rounds, where in each round each network node may transmit a single (possibly encoded) information packet on any of its outgoing edges. The objective is to minimize the communication latency, i.e., number of communication rounds needed until all terminals have all the messages of the source nodes.For sufficiently large alphabet sizes (i.e., large block length, packet sizes), it is known that traditional linear multicast network coding techniques (such as random linear network coding)) minimize latency. In this work we seek to study the task of minimizing latency in the setting of limited alphabet sizes $(\mathrm {i}.\mathrm {e}.,$ finite block length), and alternatively, the task of minimizing the alphabet size in the setting of bounded latency. Through reductive arguments, we prove that it is NP-hard to (i) approximate (and in particular to determine) the minimum alphabet size given a latency constraint; (ii) to approximate (and in particular to determine) the minimum latency of communication schemes in the setting of limited alphabet sizes.

A graph database is a digraph whose arcs are labeled with symbols from a fixed alphabet. A regular graph pattern (RGP) is a digraph whose edges are labeled with regular expressions over the alphabet. RGPs model navigational queries for graph databases called conjunctive regular path queries (CRPQs). A match of a CRPQ in the database is witnessed by a special navigational homomorphism of the corresponding RGP to the database. We study the complexity of deciding the existence of a homomorphism between two RGPs. Such homomorphisms model a strong type of containment between the two corresponding CRPQs. We show that this problem can be solved by an EXPTIME algorithm (while general query containmement in this context is EXPSPACE-complete). We also study the problem for restricted RGPs over a unary alphabet, that arise from some applications like XPath or SPARQL. For this case, homomorphism-based CRPQ containment is in NP. We prove that certain interesting cases are in fact polynomial-time solvable., 15 pages. Short version appeared in the proceedings of the 15th Conference on Computability in Europe (CIE 2019)

In the $\varepsilon$-Consensus-Halving problem, a fundamental problem in fair division, there are $n$ agents with valuations over the interval $[0,1]$, and the goal is to divide the interval into pieces and assign a label "$+$" or "$-$" to each piece, such that every agent values the total amount of "$+$" and the total amount of "$-$" almost equally. The problem was recently proven by Filos-Ratsikas and Goldberg [2019] to be the first "natural" complete problem for the computational class PPA, answering a decade-old open question. In this paper, we examine the extent to which the problem becomes easy to solve, if one restricts the class of valuation functions. To this end, we provide the following contributions. First, we obtain a strengthening of the PPA-hardness result of [Filos-Ratsikas and Goldberg, 2019], to the case when agents have piecewise uniform valuations with only two blocks. We obtain this result via a new reduction, which is in fact conceptually much simpler than the corresponding one in [Filos-Ratsikas and Goldberg, 2019]. Then, we consider the case of single-block (uniform) valuations and provide a parameterized polynomial time algorithm for solving $\varepsilon$-Consensus-Halving for any $\varepsilon$, as well as a polynomial-time algorithm for $\varepsilon=1/2$. Finally, an important application of our new techniques is the first hardness result for a generalization of Consensus-Halving, the Consensus-$1/k$-Division problem [Simmons and Su, 2003]. In particular, we prove that $\varepsilon$-Consensus-$1/3$-Division is PPAD-hard., Journal version. Preliminary version appeared at EC '20

The secretary problem became one of the most prominent online selection problems due to its numerous applications in online mechanism design. The task is to select a maximum weight subset of elements subject to given constraints, where elements arrive one-by-one in random order, revealing a weight upon arrival. The decision whether to select an element has to be taken immediately after its arrival. The different applications that map to the secretary problem ask for different constraint families to be handled. The most prominent ones are matroid constraints, which both capture many relevant settings and admit strongly competitive secretary algorithms. However, dealing with more involved constraints proved to be much more difficult, and strong algorithms are known only for a few specific settings. In this paper, we present a general framework for dealing with the secretary problem over the intersection of several matroids. This framework allows us to combine and exploit the large set of matroid secretary algorithms known in the literature. As one consequence, we get constant-competitive secretary algorithms over the intersection of any constant number of matroids whose corresponding (single-)matroid secretary problems are currently known to have a constant-competitive algorithm. Moreover, we show that our results extend to submodular objectives., 45 pages

Metaheuristics are found to be efficient in different applications where the use of exact algorithms becomes short-handed. In the last decade, many of these algorithms have been introduced and used in a wide range of applications. Nevertheless, most of those approaches share similar components leading to a concern related to their novelty or contribution. Thus, in this paper, a pool template is proposed and used to categorize algorithm components permitting to analyze them in a structured way. We exemplify its use by means of continuous optimization metaheuristics, and provide some measures and methodology to identify their similarities and novelties. Finally, a discussion at a component level is provided in order to point out possible design differences and commonalities.

Machine Learning (ML) solutions are nowadays distributed, according to the so-called server/worker architecture. One server holds the model parameters while several workers train the model. Clearly, such architecture is prone to various types of component failures, which can be all encompassed within the spectrum of a Byzantine behavior. Several approaches have been proposed recently to tolerate Byzantine workers. Yet all require trusting a central parameter server. We initiate in this paper the study of the ``general'' Byzantine-resilient distributed machine learning problem where no individual component is trusted. We show that this problem can be solved in an asynchronous system, despite the presence of $\frac{1}{3}$ Byzantine parameter servers and $\frac{1}{3}$ Byzantine workers (which is optimal). We present a new algorithm, ByzSGD, which solves the general Byzantine-resilient distributed machine learning problem by relying on three major schemes. The first, Scatter/Gather, is a communication scheme whose goal is to bound the maximum drift among models on correct servers. The second, Distributed Median Contraction (DMC), leverages the geometric properties of the median in high dimensional spaces to bring parameters within the correct servers back close to each other, ensuring learning convergence. The third, Minimum-Diameter Averaging (MDA), is a statistically-robust gradient aggregation rule whose goal is to tolerate Byzantine workers. MDA requires loose bound on the variance of non-Byzantine gradient estimates, compared to existing alternatives (e.g., Krum). Interestingly, ByzSGD ensures Byzantine resilience without adding communication rounds (on a normal path), compared to vanilla non-Byzantine alternatives. ByzSGD requires, however, a larger number of messages which, we show, can be reduced if we assume synchrony., This is a merge of arXiv:1905.03853 and arXiv:1911.07537; arXiv:1911.07537 will be retracted

Order-preserving encryption (OPE) is a cryptographic primitive that preserves the order of plaintexts. In the past few years, many OPE schemes have been studied to solve the problem of executing range queries in encrypted databases. However, OPE allows certain information to be leaked (for example, the order of ciphertext), so it is vulnerable to many attacks. Subsequently, order-revealing encryption (ORE), as a generalization of order-preserving encryption, breaks through the limitation of the numeric order of OPE plaintext. It implements ciphertext comparison for any specific form of plaintext through a publicly computable comparison function. In this work, we aim to design the new ORE scheme which reduces the leakage and preserves the practicality in terms of ciphertext length and encryption time. We first propose the hybrid model named HybridORE. Then, we propose an improved scheme named EncodeORE which achieves acceptable security and appropriate ciphertext length. They both explore the encode strategy of encoding plaintext into different parts and apply suitable ORE algorithms to each part according to its security characteristics to reduce leakage. Compared with the typical schemes in large domain, they have less leakage. The experiment shows that the proposed EncodeORE is very practical.

Consider a region that requires to be protected from unauthorized penetrations. The border of the region, modeled as a unit line segment, consists of high priority segments that require the highest level of protection separated by low priority segments that require to be visited infinitely often. We study the problem of patrolling the border with a set of k robots. The goal is to obtain a strategy that minimizes the maximum idle time (the time that a point is left unattended) of the high priority points while visiting the low priority points infinitely often. We use the concept of single lid cover (segments of fixed length) where each high priority point is covered with at least one lid, and then we extend it to strong double-lid cover where each high priority point is covered with at least two lids, and the unit line segment is fully covered. Let λk-1 be the minimum lid length that accepts a single λk-1-lid cover with k - 1 lids and Λ2k be the minimum lid length that accepts a strong double Λ2k-lid cover with 2k lids. We show that 2min(Λ2k, λk-1) is the lower bound of the idle time when the max speed of the robots is one. To compute Λ2k and λk-1, we present an algorithm with time complexity O(max(k, n) logn) where n is the number of high priority sections. Our algorithm improves by a factor of min(n, k) the previous O(knlogn) running time algorithm. For the upper bound, first we present a strategy with idle time λk-1 where one robot covers the unit line, and the remaining robots cover the lids of a single λk-1-lid cover with k - 1 lids. Then, we present a simple strategy with idle time 3Λ2k that splits the unit line into not-disjoint k segments of equal length that robots synchronously cover, i.e., reaching the leftmost and rightmost point simultaneously. Then, we present a complex strategy that split the unit line into k non-disjoint segments that robots asynchronously cover. We show that combining strategies one and two attain an approximation of 1.5 the optimal idle time and combining strategy one and third attain optimal idle time.

This paper deals with the simultaneous estimation of the attitude, position and linear velocity for vision-aided inertial navigation systems. We propose a nonlinear observer on $SO(3)\times \mathbb{R}^{15}$ relying on body-frame acceleration, angular velocity and (stereo or monocular) bearing measurements of some landmarks that are constant and known in the inertial frame. Unlike the existing local Kalman-type observers, our proposed nonlinear observer guarantees almost global asymptotic stability and local exponential stability. A detailed uniform observability analysis has been conducted and sufficient conditions are derived. Moreover, a hybrid version of the proposed observer is provided to handle the intermittent nature of the measurements in practical applications. Simulation and experimental results are provided to illustrate the effectiveness of the proposed state observer., Accepted for publication in IEEE Transaction on Automatic Control. 16 pages, 6 figures

Cloud computing enables users to remove the necessity of the need of local hardware architecture, which removes the burden of the users from high computation costs. Therefore, it has attracted much attention and research has been conducted heavily on it. To protect users' privacy, data is usually encrypted prior to being sent to the cloud server. New cryptographic primitive such as public-key encryption with equality test (PKEET) has been introduced to make it more practical. In PKEET, users can test whether the underlying messages of two ciphertexts encrypted under different public keys are equal or not without the need to decrypt those ciphertexts. This is a very useful tool, especially for the cloud database, since PKEET mainly focuses on the equality test between two ciphertexts. However, in practice, the cloud server may need to verify the equivalence among more than two ciphertexts. This leads to disclosing unnecessary information of users and redundant computation cost will also occur when using traditional PKEET schemes. How to make this more efficient and practical remains an interesting research problem. In this paper, to solve the aforementioned problems by providing a novel concept of public-key encryption with multi-ciphertext equality test (PKE-MET).

International audience; In this paper we enhance the EasyCrypt proof assistant to reason about computational complexity of adversaries. The key technical tool is a Hoare logic for reasoning about computational complexity (execution time and oracle calls) of adversarial computations. Our Hoare logic is built on top of the module system used by EasyCrypt for modeling adversaries. We prove that our logic is sound w.r.t. the semantics of EasyCrypt programs-we also provide full semantics for the EasyCrypt module system, which was previously lacking. We showcase (for the first time in EasyCrypt and in other computer-aided cryptographic tools) how our approach can express precise relationships between the probability of adversarial success and their execution time. In particular, we can quantify existentially over adversaries in a complexity class, and express general composition statements in simulation-based frameworks. Moreover, such statements can be composed to derive standard concrete security bounds for cryptographic constructions whose security is proved in a modular way. As a main benefit of our approach, we revisit security proofs of some well-known cryptographic constructions and we present a new formalization of Universal Composability (UC).

We examine the classic game of Cops and Robbers played on models of dynamic graphs, that is, graphs evolving over discrete time steps. At each time step, a graph instance is generated as a subgraph of the underlying graph of the model. The cops and the robber take their turns on the current graph instance. The cops win if they can capture the robber at some point in time. Otherwise, the robber wins. In the offline case, the players are fully aware of the evolution sequence, up to some finite time horizon T. We provide a O(n 2k+1 T) algorithm to decide whether a given evolution sequence for an underlying graph with n vertices is k-cop-win via a reduction to a reachability game. In the online case, there is no knowledge of the evolution sequence, and the game might go on forever. Also, each generated instance is required to be connected. We provide a nearly tight characterization for sparse underlying graphs, i.e., with at most linear number of edges. We prove λ + 1 cops suffice to capture the robber in any underlying graph with n − 1 + λ edges. Further, we define a family of underlying graphs with n−1+λ edges where λ−1 cops are necessary (and sufficient) for capture.

We consider a swarm of mobile robots evolving in a bidimensional Euclidean space. We study a variant of the crash-tolerant gathering problem: if no robot crashes, robots have to meet at the same arbitrary location, not known beforehand, in finite time; if one or several robots crash at the same location, the remaining correct robots gather at the crash location to rescue them. Motivated by impossibility results in the semi-synchronous setting, we present the first solution to the problem for the fully synchronous setting that operates in the vanilla Look-Compute-Move model with no additional hypotheses: robots are oblivious, disoriented, have no multiplicity detection capacity, and may start from arbitrary positions (including those with multiplicity points). We furthermore show that robots gather in a time that is proportional to the initial maximum distance between robots., Comment: arXiv admin note: substantial text overlap with arXiv:2010.04400

The origins of proof-theoretic semantics lie in the question of what constitutes the meaning of the logical connectives and its response: the rules of inference that govern the use of the connective. However, what if we go a step further and ask about the meaning of a proof as a whole? In this paper we address this question and lay out a framework to distinguish sense and denotation of proofs. Two questions are central here. First of all, if we have two (syntactically) different derivations, does this always lead to a difference, firstly, in sense, and secondly, in denotation? The other question is about the relation between different kinds of proof systems (here: natural deduction vs. sequent calculi) with respect to this distinction. Do the different forms of representing a proof necessarily correspond to a difference in how the inferential steps are given? In our framework it will be possible to identify denotation as well as sense of proofs not only within one proof system but also between different kinds of proof systems. Thus, we give an account to distinguish a mere syntactic divergence from a divergence in meaning and a divergence in meaning from a divergence of proof objects analogous to Frege's distinction for singular terms and sentences., Comment: Post-peer-review, pre-copyedit version of article, published version available open access under DOI: 10.1007/s10992-020-09577-2

Concurrent data structures provide fundamental building blocks for concurrent programming. Standard concurrent data structures may be extended by allowing a sequence of operations to be submitted as a batch for later execution. A sequence of such operations can then be executed more efficiently than the standard execution of one operation at a time. In this article, we develop a novel algorithmic extension to the prevalent FIFO queue data structure that exploits such batching scenarios. An implementation in C++ on a multicore demonstrates significant performance improvement of more than an order of magnitude (depending on the batch lengths and the number of threads) compared to previous queue implementations.

We study the problem of computing data-driven personalized reserve prices in eager second price auctions without having any assumption on valuation distributions. Here, the input is a data set that contains the submitted bids of n buyers in a set of auctions, and the problem is to return personalized reserve prices r that maximize the revenue earned on these auctions by running eager second price auctions with reserve r. For this problem, which is known to be NP complete, we present a novel linear program (LP) formulation and a rounding procedure, which achieves a 0.684 approximation. This improves over the [Formula: see text]-approximation algorithm from Roughgarden and Wang. We show that our analysis is tight for this rounding procedure. We also bound the integrality gap of the LP, which shows that it is impossible to design an algorithm that yields an approximation factor larger than 0.828 with respect to this LP. This paper was accepted by Chung Piaw Teo, Management Science Special Section on Data-Driven Prescriptive Analytics.

Recent theoretical research has shown that self-adjusting and self-adaptive mechanisms can provably outperform static settings in evolutionary algorithms for binary search spaces. However, the vast majority of these studies focuses on unimodal functions which do not require the algorithm to flip several bits simultaneously to make progress. In fact, existing self-adjusting algorithms are not designed to detect local optima and do not have any obvious benefit to cross large Hamming gaps. We suggest a mechanism called stagnation detection that can be added as a module to existing evolutionary algorithms (both with and without prior self-adjusting algorithms). Added to a simple (1+1) EA, we prove an expected runtime on the well-known Jump benchmark that corresponds to an asymptotically optimal parameter setting and outperforms other mechanisms for multimodal optimization like heavy-tailed mutation. We also investigate the module in the context of a self-adjusting (1+$\lambda$) EA and show that it combines the previous benefits of this algorithm on unimodal problems with more efficient multimodal optimization. To explore the limitations of the approach, we additionally present an example where both self-adjusting mechanisms, including stagnation detection, do not help to find a beneficial setting of the mutation rate. Finally, we investigate our module for stagnation detection experimentally., Comment: 26 pages. Full version of a paper appearing at GECCO 2020

Network pricing games provide a framework for modeling real-world settings with two types of strategic agents: operators of a network and users of the network. Operators of the network post a price so as to attract users and maximize profit; users of the network select routes based on these prices and congestion from other users. Motivated by the fact that equilibrium in these games may not exist, may not be unique, and may induce an inefficient network performance, our main result is to observe that a simple regulation on the network owners’ market solves these three issues. Specifically, if an authority could set appropriate caps (upper bounds) on the tolls (prices) operators can charge, then the game among the link operators has a unique and strong Nash equilibrium and the users’ game results in a Wardrop equilibrium that achieves the optimal total delay. We call any price vector with these properties a great set of tolls and investigate the efficiency of great tolls with respect to the users’ surplus. We derive a bicriteria bound that compares the users’ surplus under great tolls with the users’ surplus under optimal tolls. Finally, we consider two different extensions of the model. First, we assume that operators face operating costs that depend on the amount of flow on the link, for which we prove existence of great tolls. Second, we allow operators to own more than one link. In this case, we prove that, when operators own complementary links (i.e., links for which an increase in toll value may only increase the flow on the other owned links), any toll vector that induces the optimal flow and that is upper bounded by the marginal tolls is a great set of tolls, and furthermore, we show that, when all links in the network are complementary, then the aforementioned toll vector is also a strong cap equilibrium.

The question if a given partial solution to a problem can be extended reasonably occurs in many algorithmic approaches for optimization problems. For instance, when enumerating minimal dominating sets of a graph $G=(V,E)$, one usually arrives at the problem to decide for a vertex set $U \subseteq V$, if there exists a \textit{minimal} dominating set $S$ with $U\subseteq S$. We propose a general, partial-order based formulation of such extension problems and study a number of specific problems which can be expressed in this framework. Possibly contradicting intuition, these problems tend to be NP-hard, even for problems where the underlying optimisation problem can be solved in polynomial time. This raises the question of how fixing a partial solution causes this increase in difficulty. In this regard, we study the parameterised complexity of extension problems with respect to parameters related to the partial solution, as well as the optimality of simple exact algorithms under the Exponential-Time Hypothesis. All complexity considerations are also carried out in very restricted scenarios, be it degree restrictions or topological restrictions (planarity) for graph problems or the size of the given partition for the considered extension variant of Bin Packing.

Large-scale software verification relies critically on the use of compositional languages, semantic models, specifications, and verification techniques. Recent work on certified abstraction layers synthesizes game semantics, the refinement calculus, and algebraic effects to enable the composition of heterogeneous components into larger certified systems. However, in existing models of certified abstraction layers, compositionality is restricted by the lack of encapsulation of state. In this paper, we present a novel game model for certified abstraction layers where the semantics of layer interfaces and implementations are defined solely based on their observable behaviors. Our key idea is to leverage Reddy's pioneer work on modeling the semantics of imperative languages not as functions on global states but as objects with their observable behaviors. We show that a layer interface can be modeled as an object type (i.e., a layer signature) plus an object strategy. A layer implementation is then essentially a regular map, in the sense of Reddy, from an object with the underlay signature to that with the overlay signature. A layer implementation is certified when its composition with the underlay object strategy implements the overlay object strategy. We also describe an extension that allows for non-determinism in layer interfaces. After formulating layer implementations as regular maps between object spaces, we move to concurrency and design a notion of concurrent object space, where sequential traces may be identified modulo permutation of independent operations. We show how to express protected shared object concurrency, and a ticket lock implementation, in a simple model based on regular maps between concurrent object spaces.

We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of $n$ disjoint growing squares. Our data structure uses $O(n (\log n \log\log n)^2)$ space, supports queries in worst case $O(\log^3 n)$ time, and updates in $O(\log^7 n)$ amortized time. This leads to an $O(n\alpha(n)\log^7 n)$ time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best $O(n^2)$ time algorithms., Comment: 14 pages, 7 figures

Approximate Matrix Multiplication (AMM) has emerged as a useful and computationally inexpensive substitute for actual multiplication of large matrices. Randomized as well as deterministic solutions to AMM were provided in the past. The latest work provides a deterministic algorithm that solves AMM more accurately than the other works. It is a streaming algorithm that is both fast and accurate. But, it is less robust to noise and is also liable to have less than optimal performance in the presence of concept drift in the input matrices. We propose an algorithm that is more accurate, robust to noise, invariant to concept drift in the data, while having almost the same running time as the state-of-the-art algorithm. We also prove that theoretical guarantees exist for the proposed algorithm. An empirical performance improvement of up to 90 % is obtained over the previous algorithm. We also propose a general framework for parallelizing the proposed algorithm. The two parallelized versions of the algorithm achieve up to 1.9 x and 3.6 x speedups over the original version of the proposed algorithm.

We propose a novel constraint-handling technique for the covariance matrix adaptation evolution strategy (CMA-ES). The proposed technique is aimed at solving explicitly constrained black-box continuous optimization problems, in which the explicit constraint is a constraint whereby the computational time for the constraint violation and its (numerical) gradient are negligible compared to that for the objective function. This method is designed to realize two invariance properties: invariance to the affine transformation of the search space, and invariance to the increasing transformation of the objective and constraint functions. The CMA-ES is designed to possess these properties for handling difficulties that appear in black-box optimization problems, such as non-separability, ill-conditioning, ruggedness, and the different orders of magnitude in the objective. The proposed constraint-handling technique (CHT), known as ARCH, modifies the underlying CMA-ES only in terms of the ranking of the candidate solutions. It employs a repair operator and an adaptive ranking aggregation strategy to compute the ranking. We developed test problems to evaluate the effects of the invariance properties, and performed experiments to empirically verify the invariance of the algorithm. We compared the proposed method with other CHTs on the CEC 2006 constrained optimization benchmark suite to demonstrate its efficacy. Empirical studies reveal that ARCH is able to exploit the explicitness of the constraint functions effectively, sometimes even more efficiently than an existing box-constraint handling technique on box-constrained problems, while exhibiting the invariance properties. Moreover, ARCH overwhelmingly outperforms CHTs by not exploiting the explicit constraints in terms of the number of objective function calls., Accepted to Evolutionary Computation (MIT Press)

In cryptography and algorithmic number theory, modular inversion is viewed as one of the most common and time-consuming operations. It is hard to be directly accomplished on resource-constrained clients (e.g. mobile devices and IC cards) since modular inversion involves a great amount of operations on large numbers in practice. To address the above problem, this paper proposes a novel unimodular matrix transformation technique to realize secure outsourcing of modular inversion. This technique makes our algorithm achieve several amazing properties. First, to the best of our knowledge, it is the first secure outsourcing computation algorithm that supports arbitrary and variable modulus, which eliminates the restriction in previous work that the protected modulus has to be a fixed composite number. Second, our algorithm is based on the single untrusted program model, which avoids the non-collusion assumption between multiple servers. Third, it only needs one round interaction between the client and the cloud server, and can detect the malicious behavior of the cloud server with the (optimal) probability $1$ . Furthermore, we propose an extended secure outsoucing algorithm that can solve modular inversion in multi-variable case. Theoretical analysis and experimental results show that our proposed algorithms achieve remarkable local-client's computational savings. At last, as two important and helpful applications of our algorithms, the outsourced implementations of the key generation of RSA algorithm and the Chinese Reminder Theorem are given.

The resilience of cyberphysical systems to denial-of-service (DoS) and integrity attacks is studied in this paper. The cyberphysical system is modeled as a linear structured system, and its resilience to an attack is interpreted in a graph theoretical framework. The structural resilience of the system is characterized in terms of unmatched vertices in maximum matchings of the bipartite graph and connected components of directed graph representations of the system under attack. We first present conditions for the system to be resilient to DoS attacks when an adversary may block access or turn off certain inputs to the system. We extend this analysis to characterize resilience of the system when an adversary might additionally have the ability to affect the implementation of state-feedback control strategies. This is termed an integrity attack. We establish conditions under which a system that is structurally resilient to a DoS attack will also be resilient to a certain class of integrity attacks. Finally, we formulate an extension to the case of switched linear systems, and derive conditions for such systems to be structurally resilient to a DoS attack., Comment: Accepted to the European Journal of Control

Model management is a central activity in Software Engineering. The most challenging aspect of model management is to keep inter-related models consistent with each other while they evolve. As a consequence, there is a lot of scientific activity in this area, which has produced an extensive body of knowledge, methods, results and tools. The majority of these approaches, however, are limited to binary inter-model relations; i.e. the synchronisation of exactly two models. Yet, not every multi-ary relation can be factored into a family of binary relations. In this paper, we propose and investigate a novel comprehensive system construction, which is able to represent multi-ary relations among multiple models in an integrated manner and thus serves as a formal foundation for artefacts used in consistency management activities involving multiple models. The construction is based on the definition of partial commonalities among a set of models using the same language, which is used to denote the (local) models. The main theoretical results of this paper are proofs of the facts that comprehensive systems are an admissible environment for (i) applying formal means of consistency verification (diagrammatic predicate framework), (ii) performing algebraic graph transformation (weak adhesive HLR category), and (iii) that they generalise the underlying setting of graph diagrams and triple graph grammars.

We propose ε ↓ ( D → ) -logic as a formal foundation for the specification and development of event-based systems with data states. The framework is presented as an institution in the sense of Goguen and Burstall and the logic itself is parametrised by an underlying institution D → whose structures are used to model data states. ε ↓ ( D → ) -logic is intended to cover a broad range of abstraction levels from abstract requirements specifications up to constructive specifications. It uses modal diamond and box operators over complex actions adopted from dynamic logic. Atomic actions are pairs [inline-graphic not available: see fulltext] where e is an event and ψ a state transition predicate capturing the allowed reactions to the event. To write concrete specifications of recursive process structures we integrate (control) state variables and binders of hybrid logic. The semantic interpretation relies on event/data transition systems. For the presentation of constructive specifications we propose operational event/data specifications allowing for familiar, diagrammatic representations by state transition graphs. We show that ε ↓ ( D → ) -logic is powerful enough to characterise the semantics of an operational specification by a single ε ↓ ( D → ) -sentence. Thus the whole (formal) development process for event/data-based systems relies on ε ↓ ( D → ) -logic and its semantics as a common basis. It is supported by a variety of implementation constructors which can express, among others, event refinement and parallel composition. Due to the genericity of the approach, it is also possible to change a data state institution during system development when needed. All steps of our formal treatment are illustrated by a running example.

We consider, for the first time, the exploration of dynamic graphs of arbitrary unknown topology. We study the number of agents necessary and sufficient to explore such graphs under the fully synchronous ( Fsync ) and the semi-synchronous ( Ssync ) activation schedulers. We prove that, under the minimal assumption on the dynamics, temporal connectivity, the number of agents sufficient to perform exploration depends on a parameter we call evanescence of the graph, and this number is tight. We then consider the stronger well-known assumption of 1-interval connectivity when the number of edges missing at each time is bounded. We provide tight bounds also in this setting, proving the existence of a difference between Fsync and Ssync , as well as between anonymous and non-anonymous agents.

We develop a model of many-to-one matching markets in which agents with multiunit demand aim to maximize a cardinal linear objective subject to multidimensional knapsack constraints. The choice functions of agents with multiunit demand are therefore not substitutable. As a result, pairwise stable matchings may not exist and even when they do, may be highly inefficient. We provide an algorithm that finds a group-stable matching that approximately satisfies all the multidimensional knapsack constraints. The novel ingredient in our algorithm is a combination of matching with contracts and Scarf’s Lemma. We show that the degree of the constraint violation under our algorithm is proportional to the sparsity of the constraint matrix. The algorithm, therefore, provides practical constraint violation bounds for applications in contexts, such as refugee resettlement, day care allocation, and college admissions with diversity requirements. Simulations using refugee resettlement data show that our approach produces outcomes that are not only more stable, but also more efficient than the outcomes of the Deferred Acceptance algorithm. Moreover, simulations suggest that in practice, constraint violations under our algorithm would be even smaller than the theoretical bounds. This paper was accepted by Gabriel Weintraub, revenue management and market analytics.

This letter addresses the problem of coordinating a team of pursuers to capture a fast evader in reach-avoid games. Coordination is achieved through the minimization of a locational cost objective, which results in a coverage control strategy. Coverage control dynamics are equivalently expressed as consensus dynamics. This formulation is used to guarantee optimal coverage of an implicit defense manifold without needing to rely on projection mappings as in previous works. Control barrier functions (CBFs) are used to guarantee the existence of a pursuer-defendable defense manifold for as long as feasible throughout the engagement and guarantee capture. A greedy evader strategy is proposed in terms of the solution to a quadratically constrained quadratic program, and simulation results are presented comparing the performance of an uncoordinated strategy and a pure coverage strategy to the proposed coordinated CBF strategy.

In this paper we give sublinear-time distributed algorithms in the CONGEST model for subgraph detection for two classes of graphs: cliques and even-length cycles. We show for the first time that all copies of 4-cliques and 5-cliques in the network graph can be listed in sublinear time, O(n^{5/6+o(1)}) rounds and O(n^{21/22+o(1)}) rounds, respectively. Prior to our work, it was not known whether it was possible to even check if the network contains a 4-clique or a 5-clique in sublinear time. For even-length cycles, C_{2k}, we give an improved sublinear-time algorithm, which exploits a new connection to extremal combinatorics. For example, for 6-cycles we improve the running time from O~(n^{5/6}) to O~(n^{3/4}) rounds. We also show two obstacles on proving lower bounds for C_{2k}-freeness: First, we use the new connection to extremal combinatorics to show that the current lower bound of Omega~(sqrt{n}) rounds for 6-cycle freeness cannot be improved using partition-based reductions from 2-party communication complexity, the technique by which all known lower bounds on subgraph detection have been proven to date. Second, we show that there is some fixed constant delta in (0,1/2) such that for any k, a Omega(n^{1/2+delta}) lower bound on C_{2k}-freeness implies new lower bounds in circuit complexity. For general subgraphs, it was shown in [Orr Fischer et al., 2018] that for any fixed k, there exists a subgraph H of size k such that H-freeness requires Omega~(n^{2-Theta(1/k)}) rounds. It was left as an open problem whether this is tight, or whether some constant-sized subgraph requires truly quadratic time to detect. We show that in fact, for any subgraph H of constant size k, the H-freeness problem can be solved in O(n^{2 - Theta(1/k)}) rounds, nearly matching the lower bound of [Orr Fischer et al., 2018].

An $H$-free editing problem asks whether we can edit at most $k$ edges to make a graph contain no induced copy of the fixed graph $H$. We obtain a polynomial kernel for this problem when $H$ is a diamond. The incompressibility dichotomy for $H$ being a 3-connected graph and the classical complexity dichotomy suggest that except for $H$ being a complete/empty graph, $H$-free editing problems admit polynomial kernels only for a few small graphs $H$. Therefore, we believe that our result is an essential step toward a complete dichotomy on the compressibility of $H$-free editing. Additionally, we give a cubic-vertex kernel for the diamond-free edge deletion problem, which is far simpler than the previous kernel of the same size for the problem.

We propose a new grid unfolding without refinement of a new sub-class of polycubes that we call Manhattan towers with an H-convex base. Such poly-cubes can be seen both as a Manhattan tower and as an orthostack. At the end of the paper we show that an extension of this algorithm to Up-and-Down Orthoterrains is also possible.

Several formal systems, such as resolution and minimal model semantics, provide a framework for logic programming. In this paper, we will survey the use of structural proof theory as an alternative foundation. Researchers have been using this foundation for the past 35 years to elevate logic programming from its roots in first-order classical logic into higher-order versions of intuitionistic and linear logic. These more expressive logic programming languages allow for capturing stateful computations and rich forms of abstractions, including higher-order programming, modularity, and abstract data types. Term-level bindings are another kind of abstraction, and these are given an elegant and direct treatment within both proof theory and these extended logic programming languages. Logic programming has also inspired new results in proof theory, such as those involving polarity and focused proofs. These recent results provide a high-level means for presenting the differences between forward-chaining and backward-chaining style inferences. Anchoring logic programming in proof theory has also helped identify its connections and differences with functional programming, deductive databases, and model checking., To appear in Theory and Practice of Logic Programming (TPLP)

Constraint answer set programming or CASP, for short, is a hybrid approach in automated reasoning putting together the advances of distinct research areas such as answer set programming, constraint processing, and satisfiability modulo theories. Constraint answer set programming demonstrates promising results, including the development of a multitude of solvers: acsolver, clingcon, ezcsp, idp, inca, dingo, mingo, aspmt, clingo[l,dl], and ezsmt. It opens new horizons for declarative programming applications such as solving complex train scheduling problems. Systems designed to find solutions to constraint answer set programs can be grouped according to their construction into, what we call, integrational or translational approaches. The focus of this paper is an overview of the key ingredients of the design of constraint answer set solvers drawing distinctions and parallels between integrational and translational approaches. The paper also provides a glimpse at the kind of programs its users develop by utilizing a CASP encoding of Travelling Salesman problem for illustration. In addition, we place the CASP technology on the map among its automated reasoning peers as well as discuss future possibilities for the development of CASP., Under consideration in Theory and Practice of Logic Programming (TPLP)

This paper studies the online energy scheduling problem in a hybrid model where the cost of energy is proportional to both the volume and peak usage, and where energy can be either locally generated or drawn from the grid. Inspired by recent advances in online algorithms with Machine Learned (ML) advice, we develop parameterized deterministic and randomized algorithms for this problem such that the level of reliance on the advice can be adjusted by a trust parameter. We then analyze the performance of the proposed algorithms using two performance metrics: robustness that measures the competitive ratio as a function of the trust parameter when the advice is inaccurate, and consistency for competitive ratio when the advice is accurate. Since the competitive ratio is analyzed in two different regimes, we further investigate the Pareto optimality of the proposed algorithms. Our results show that the proposed deterministic algorithm is Pareto-optimal, in the sense that no other online deterministic algorithms can dominate the robustness and consistency of our algorithm. Furthermore, we show that the proposed randomized algorithm dominates the Pareto-optimal deterministic algorithm. Our large-scale empirical evaluations using real traces of energy demand, energy prices, and renewable energy generations highlight that the proposed algorithms outperform worst-case optimized algorithms and fully data-driven algorithms.

We investigate the problem of securely outsourcing the modular exponentiations in cryptography to an untrusted server, and analyze the security and the efficiency of three privacy-preserving outsourcing protocols for exponentiations proposed in Ding et al. (2017) [18] . Based on Coppersmith's lattice-based method, we present heuristic polynomial-time and ciphertext-only weak-key attacks on these protocols, which shows that the recommended size of the secret keys in their protocols can not assure the input privacy of the exponents. Correspondingly, we explicitly estimate the size of the secure secret keys to circumvent our attacks, and analyze the efficiency of the revised protocols with security settings. Our theoretical analysis and experimental results demonstrate that the protocol of single modular exponentiation is unavailable, the protocol of simultaneous modular exponentiations is not so efficient as claimed but still available, and the protocol of multiple modular exponentiations becomes more efficient as the number of exponentiations increases.

Spiking neural P systems with rules on synapses (RSSNP systems) are a class of computation models which are inspired by the information processing and communication manner of neurons. In this work, we consider labeled RSSNP systems (lRSSNP systems), where each rule is assigned either with a label chosen from an alphabet Σ or with the empty label λ. A string over an alphabet is accepted by an lRSSNP system if the string is processed from left to right by the system in the sense that in a step only rules labeled with the processed symbol or with λ are used (not both), and the system reaches a final configuration in the moment when the whole string is processed. The set of all accepted strings is categorized as the restricted (computations are done with the application of the rules labeled with symbols from the given alphabet) control language and the unrestricted (rules labeled with λ are allowed in the computations) control language of the system. We study the language accepting power of lRSSNP systems using only standard spiking rules by comparing the family of control languages of lRSSNP systems with the families of languages in the Chomsky hierarchy. It is proved that restricted lRSSNP systems can accept no more than context-sensitive languages, and unrestricted lRSSNP systems can accept recursively enumerable languages.

In 2014, Jeandel proved that two dynamical properties regarding Turing machines can be computable with any desired error ϵ > 0 , the Turing machine Maximum Speed and Topological Entropy. Both problems were proved in parallel, using equivalent properties. Those results were unexpected, as most (if not all) dynamical properties are undecidable. Nevertheless, Topological Entropy positiveness for reversible and complete Turing machines was shortly proved to be undecidable, with a reduction of the halting problem with empty counters in 2-reversible Counter machines. Unfortunately, the same proof could not be used to prove undecidability of Speed Positiveness. In this research, we prove the undecidability of Homogeneous Tape Reachability Problem for aperiodic and reversible Turing machines, in order to use it to prove the undecidability of the Speed Positiveness Problem for complete and reversible Turing machines.

The basic goal of threshold group testing is to identify up to $d$ defective items among a population of $n$ items, where $d$ is usually much smaller than $n$. The outcome of a test on a subset of items is positive if the subset has at least $u$ defective items, negative if it has up to $\ell$ defective items, where $0\leq\ell0$, i.e., threshold group testing with a gap. Note that the results presented here are also applicable to the case $g = 0$; however, the results are not as efficient as those in related work. Currently, a few reported studies have investigated test designs and decoding algorithms for identifying defective items. Most of the previous studies have not been feasible because there are numerous constraints on their problem settings or the decoding complexities of their proposed schemes are relatively large. Therefore, it is compulsory to reduce the number of tests as well as the decoding complexity, i.e., the time for identifying the defective items, for achieving practical schemes. The work presented here makes five contributions. The first is a more accurate theorem for a non-adaptive algorithm for threshold group testing proposed by Chen and Fu. The second is an improvement in the construction of disjunct matrices, which are the main tools for tackling (threshold) group testing and other tasks such as constructing cover-free families or learning hidden graphs. The third and fourth contributions are a reduced exact upper bound on the number of tests and a reduced asymptotic bound on the decoding time for identifying defective items in a noisy setting on test outcomes. The fifth contribution is a simulation on the number of tests of the resulting improvements for previous work and the proposed theorems., Comment: 27 pages, 8 figures

The Minimum Spanning Tree problem (abbr. MSTP) is a well-known combinatorial optimization problem that has been extensively studied by the researchers in the field of evolutionary computing to theoretically analyze the optimization performance of evolutionary algorithms. Within the paper, we consider a constrained version of the problem named 2-Hop ( 1 , 2 )-Minimum Spanning Tree problem (abbr. 2H-( 1 , 2 )-MSTP) in the context of evolutionary algorithms, which has been shown to be NP-hard. Following how evolutionary algorithms are applied to solve the MSTP, we first consider the evolutionary algorithms with search points in edge-based representation adapted to the 2H-( 1 , 2 )-MSTP (including the ( 1 + 1 ) EA, Global Simple Evolutionary Multi-Objective Optimizer and its two variants). More specifically, we separately investigate the upper bounds on their expected time (i.e., the expected number of fitness evaluations) to obtain a 3 2 -approximate solution with respect to different fitness functions. Inspired by the special structure of 2-hop spanning trees, we also consider the ( 1 + 1 ) EA with search points in vertex-based representation that seems not so natural for the problem and give an upper bound on its expected time to obtain a 3 2 -approximate solution, which is better than the above mentioned ones.

Meta-learning aims to leverage experience from previous tasks to achieve an effective and fast adaptation ability when encountering new tasks. However, it is unclear how the generalization property applies to new tasks. Probably approximately correct (PAC) Bayes bound theory provides a theoretical framework to analyze the generalization performance for meta-learning with an explicit numerical generalization error upper bound. A tighter upper bound may achieve better generalization performance. However, for the PAC-Bayes meta-learning bound, the prior distribution is selected randomly which results in poor generalization performance. In this paper, we derive three novel generalization error upper bounds for meta-learning based on the PAC-Bayes relative entropy bound. Furthermore, in order to avoid randomly prior distribution, based on the empirical risk minimization (ERM) method, a data-dependent prior for the PAC-Bayes meta-learning bound algorithm is developed and the sample complexity and computational complexity are analyzed. The experiments illustrate that the proposed three PAC-Bayes bounds for meta-learning achieve a competitive generalization guarantee, and the extended PAC-Bayes bound with a data-dependent prior can achieve rapid convergence ability.

Toward combating the malicious rumor spreading on online social networks, we discuss a hybrid control strategy that combines a continuous truth spreading method and an impulsive rumor blocking method in this article. In this strategy, the truth is introduced as an anti-rumor to compete with the rumor while the rumor-infected users would be quarantined with a limited isolation period. The stability of the rumor-free equilibrium of the rumor-truth propagation system is analyzed and conditions to reach uniform asymptotic stability as well as global exponential stability are obtained. For the endemic case, the conditions under which rumor would persist uniformly are obtained. An optimal hybrid control problem is formulated to address the tradeoff between restraining rumor and minimizing the cost of control. The necessary conditions for optimal system and the structure of optimal hybrid control are obtained. Numerical simulations are carried out to illustrate the theoretical results and evaluate the potential roles of the hybrid control strategy.

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 Journees Montoises of Theoretical Computer Science [32] .

As the current society is increasingly facing major challenges from extremism and terrorism, protecting key urban public facilities and important targets from destruction is an important challenge facing the security departments of all countries. Based on real scene, this paper conducts researches on anti-terrorism security game algorithms and emergency response models in response to the three key links of before, during and after terrorist attacks. First of all, this paper constructs a multi-round joint attack game and emergency response model based on cooperation, establishes the optimization problem of solving the defender’s optimal strategy in mathematical form, and then obtains the optimal defense strategy. Secondly, in response to the fact that terrorists are not completely rational, a new hybrid model is constructed to propose an efficient allocation and scheduling algorithm for safe resources in response to terrorist attacks. Thirdly, a model of crowd evacuation strategy after a terrorist attack is built based on the problem of crowd evacuation in multiple rounds of premeditated cooperative attacks. Finally, taking the area of the first ring of a certain city as a real scene, a complete game system of the whole process is constructed, and the game effectiveness evaluation of the existing security resource allocation scheme in the first ring area is carried out. Through the research of this thesis, the author puts forward some new technical ideas for the current society’s anti-terrorism governance, and hopes to provide some technical references for the decision-making of security agencies.