Security policies enforcement using finite and pushdown edit automata

Edit automata have been introduced by J.Ligatti et al. as a model for security enforcement mechanisms which work at run time. In a distributed interacting system, they play a role of a monitor that runs in parallel with a target program and transforms its execution sequence into a sequence that obeys the security property. In this paper, we characterize security properties which are enforceable by finite edit automata (i.e. edit automata with a finite set of states) and deterministic context-free edit automata (i.e. finite edit automata extended with a stack). We prove that the properties enforceable by finite edit automata are a sub-class of regular sets. Moreover, given a regular set $P$ , one can decide in time $O(n^2)$ , whether $P$ is enforceable by a finite edit automaton (where $n$ is the number of states of the finite automaton recognizing $P$ ) and we give an algorithm to synthesize the controller. Moreover, we prove that safety policies are always enforced by a deterministic context-free edit automaton. We also prove that it is possible to check if a policy is a safety policy in $O(n^4)$ . Finally, we give a topological condition on the deterministic automaton expressing a regular policy enforceable by a deterministic context-free edit automaton.     

An improved FPTAS for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem

Recently, Shabtay and Bensoussan (2012) developed an original exact pseudo-polynomial algorithm and an efficient $\upvarepsilon $ -approximation algorithm (FPTAS) for maximizing the weighted number of just-in-time jobs in a two-machine flow shop problem. The complexity of the FPTAS is $O$ (( $n^{4}/\upvarepsilon $ )log( $n$ / $\upvarepsilon $ )), where $n$ is the number of jobs. In this note we suggest another pseudo-polynomial algorithm that can be converted to a new FPTAS which improves Shabtay–Bensoussan’s complexity result and runs in $O(n^{3}/\upvarepsilon )$ time.     

The suffix-free-prefix-free hash function construction and its indifferentiability security analysis

In this paper, we observe that in the seminal work on indifferentiability analysis of iterated hash functions by Coron et al. and in subsequent works, the initial value $(IV)$ of hash functions is fixed. In addition, these indifferentiability results do not depend on the Merkle–Damg?rd (MD) strengthening in the padding functionality of the hash functions. We propose a generic $n$ -bit-iterated hash function framework based on an $n$ -bit compression function called suffix-free-prefix-free (SFPF) that works for arbitrary $IV$ s and does not possess MD strengthening. We formally prove that SFPF is indifferentiable from a random oracle (RO) when the compression function is viewed as a fixed input-length random oracle (FIL-RO). We show that some hash function constructions proposed in the literature fit in the SFPF framework while others that do not fit in this framework are not indifferentiable from a RO. We also show that the SFPF hash function framework with the provision of MD strengthening generalizes any $n$ -bit-iterated hash function based on an $n$ -bit compression function and with an $n$ -bit chaining value that is proven indifferentiable from a RO.     

Time versus space trade-offs for rendezvous in trees

Two identical (anonymous) mobile agents start from arbitrary nodes of an unknown tree and have to meet at some node. Agents move in synchronous rounds: in each round an agent can either stay at the current node or move to one of its neighbors. We consider deterministic algorithms for this rendezvous task. The main result of this paper is a tight trade-off between the optimal time of completing rendezvous and the size of memory of the agents. For agents with $k$ memory bits, we show that optimal rendezvous time is $\Theta (n+n^2/k)$ in $n$ -node trees. More precisely, if $k \ge c\log n$ , for some constant $c$ , we design agents accomplishing rendezvous in arbitrary trees of size $n$ (unknown to the agents) in time $O(n+n^2/k)$ , starting with arbitrary delay. We also show that no pair of agents can accomplish rendezvous in time $o(n+n^2/k)$ , even in the class of lines of known length and even with simultaneous start. Finally, we prove that at least logarithmic memory is necessary for rendezvous, even for agents starting simultaneously in a $n$ -node line.     

The bideterminants of matrices over semirings

This paper deals with the relationships between the concepts of linear dependence and independence of vectors, and the bideterminant of a matrix including the links between the bideterminant and rank of a square matrix in semilinear spaces of $n$ -dimensional vectors over commutative zerosumfree semirings. First, it discusses some properties of bideterminant of a matrix, then introduces the concepts of semi-linear dependence and strong linear independence of a set of vectors, respectively, and gives a necessary and sufficient condition that the bideterminant of a matrix is equal to $0$ . In the end, it shows a necessary and sufficient condition that the rank of an $n$ -square matrix is equal to $n$ .     

Finding large k-clubs in undirected graphs

Finding cohesive subgroups is an important issue in studying social networks. Many models exist for defining cohesive subgraphs in social networks, such as clique, $k$ -clique, and $k$ -clan. The concept of $k$ -club is one of them. A $k$ -club of a graph is a maximal subset of the vertex set which induces a subgraph of diameter $k$ . It is a relaxation of a clique, which induces a subgraph of diameter $1$ . We conducted algorithmic studies on finding a $k$ -club of size as large as possible. In this paper, we show that one can find a $k$ -club of maximum size in $O^{*}(1.62^n)$ time where $n$ is the number of vertices of the input graph. We implemented a combinatorial branch-and-bound algorithm that finds a $k$ -club of maximum size and a new heuristic algorithm called IDROP given in this paper. To speed up the programs, we introduce a dynamic data structure called $k$ -DN which, under deletion of vertices from a graph, maintains for a given vertex $v$ the set of vertices at distances at most $k$ . From the experimental results that we obtained, we concluded that a $k$ -club of maximum size can be easily found in sparse graphs and dense graphs. Our heuristic algorithm finds, within reasonable time, $k$ -clubs of maximum size in most of experimental instances. The gap between the size of a $k$ -club of maximum size and a $k$ -club found by IDROP is a constant for the number of vertices that we are able to test.     

Self-orthogonal codes with dual distance three and quantum codes with distance three over \mathbb F _5

Self-orthogonal codes with dual distance three and quantum codes with distance three constructed from self-orthogonal codes over $\mathbb F _5$ are discussed in this paper. Firstly, for given code length $n\ge 5$ , a $[n,k]_{5}$ self-orthogonal code with minimal dimension $k$ and dual distance three is constructed. Secondly, for each $n\ge 5$ , two nested self-orthogonal codes with dual distance two and three are constructed, and consequently quantum code of length $n$ and distance three is constructed via Steane construction. All of these quantum codes constructed via Steane construction are optimal or near optimal according to the quantum Hamming bound.     

UV-diagram: a voronoi diagram for uncertain spatial databases

The Voronoi diagram is an important technique for answering nearest-neighbor queries for spatial databases. We study how the Voronoi diagram can be used for uncertain spatial data, which are inherent in scientific and business applications. Specifically, we propose the Uncertain-Voronoi diagram (or UV-diagram), which divides the data space into disjoint “UV-partitions”. Each UV-partition $P$ is associated with a set $S$ of objects, such that any point $q$ located in $P$ has the set $S$ as its nearest neighbor with nonzero probabilities. The UV-diagram enables queries that return objects with nonzero chances of being the nearest neighbor (NN) of a given point $q$ . It supports “continuous nearest-neighbor search”, which refreshes the set of NN objects of $q$ , as the position of $q$ changes. It also allows the analysis of nearest-neighbor information, for example, to find out the number of objects that are the nearest neighbors of any point in a given area. A UV-diagram requires exponential construction and storage costs. To tackle these problems, we devise an alternative representation of a UV-diagram, by using a set of UV-cells. A UV-cell of an object $o$ is the extent $e$ for which $o$ can be the nearest neighbor of any point $q \in e$ . We study how to speed up the derivation of UV-cells by considering its nearby objects. We also use the UV-cells to design the UV-index, which supports different queries, and can be constructed in polynomial time. We have performed extensive experiments on both real and synthetic data to validate the efficiency of our approaches.     

Universal regular control for generic semilinear systems

We consider discrete-time projective semilinear control systems \(\xi _{t+1} = A(u_t) \cdot \xi _t\) , where the states \(\xi _t\) are in projective space \(\mathbb {R}\hbox {P}^{d-1}\) , inputs \(u_t\) are in a manifold \(\mathcal {U}\) of arbitrary finite dimension, and \(A :\mathcal {U}\rightarrow \hbox {GL}(d,\mathbb {R})\) is a differentiable mapping. An input sequence \((u_0,\ldots ,u_{N-1})\) is called universally regular if for any initial state \(\xi _0 \in \mathbb {R}\hbox {P}^{d-1}\) , the derivative of the time- \(N\) state with respect to the inputs is onto. In this paper, we deal with the universal regularity of constant input sequences \((u_0, \ldots , u_0)\) . Our main result states that generically in the space of such systems, for sufficiently large \(N\) , all constant inputs of length \(N\) are universally regular, with the exception of a discrete set. More precisely, the conclusion holds for a \(C^2\) -open and \(C^\infty \) -dense set of maps \(A\) , and \(N\) only depends on \(d\) and on the dimension of \(\mathcal {U}\) . We also show that the inputs on that discrete set are nearly universally regular; indeed, there is a unique non-regular initial state, and its corank is 1. In order to establish the result, we study the spaces of bilinear control systems. We show that the codimension of the set of systems for which the zero input is not universally regular coincides with the dimension of the control space. The proof is based on careful matrix analysis and some elementary algebraic geometry. Then the main result follows by applying standard transversality theorems.     

Efficient broadcasting in radio networks with long-range interference

We study broadcasting, also known as one-to-all communication, in synchronous radio networks with known topology modeled by undirected (symmetric) graphs, where the interference range of a node is likely exceeding its transmission range. In this model, if two nodes are connected by a transmission edge they can communicate directly. On the other hand, if two nodes are connected by an interference edge they cannot communicate directly and transmission of one node disables recipience of any message at the other node. For a network $G,$ we term the smallest integer $d$ , s.t., for any interference edge $e$ there exists a simple path formed of at most $d$ transmission edges connecting the endpoints of $e$ as its interference distance $d_I$ . In this model the schedule of transmissions is precomputed in advance. It is based on the full knowledge of the size and the topology (including location of transmission and interference edges) of the network. We are interested in the design of fast broadcasting schedules that are energy efficient, i.e., based on a bounded number of transmissions executed at each node. We adopt $n$ as the number of nodes, $D_T$ is the diameter of the subnetwork induced by the transmission edges, and $\varDelta $ refers to the maximum combined degree (formed of transmission and interference edges) of the network. We contribute the following new results: (1) We prove that for networks with the interference distance $d_I\ge 2$ any broadcasting schedule requires at least $D_T+\varOmega (\varDelta \cdot \frac{\log {n}}{\log {\varDelta }})$ rounds. (2) We provide for networks modeled by bipartite graphs an algorithm that computes $1$ -shot (each node transmits at most once) broadcasting schedules of length $O(\varDelta \cdot \log {n})$ . (3) The main result of the paper is an algorithm that computes a $1$ -shot broadcasting schedule of length at most $4 \cdot D_T + O(\varDelta \cdot d_I \cdot \log ^4{n})$ for networks with arbitrary topology. Note that in view of the lower bound from (1) if $d_I$ is poly-logarithmic in $n$ this broadcast schedule is a poly-logarithmic factor away from the optimal solution.     

A quantum multiply-accumulator

This paper proposes a quantum multiply-accumulator circuit (QMAC), which can perform the calculation on conventional integers faster than its classical counterpart. Whereas classically applying a multiply–adder (MAC) $n$ times to $k$ bit integers would require $O(n \log k)$ parallel steps, the hybrid QMAC needs only $O(n + k)$ steps for the exact result and $O(n + \log k)$ steps for an approximate result. The proposed circuit could potentially be embedded in a conventional computer architecture as a quantum device or accelerator, enabling a wide range of applications to execute faster.     

Renaming and the weakest family of failure detectors

We address the question of the weakest failure detector to circumvent the impossibility of $(2n-2)$ -renaming in a system of up to $n$ participating processes. We derive that in a restricted class of eventual failure detectors there does not exist a single weakest oracle, but a weakest family of oracles $\zeta _n$ : every two oracles in $\zeta _n$ are incomparable, and every oracle that allows for solving renaming provides at least as much information about failures as one of the oracles in $\zeta _n$ . As a by product, we obtain one more evidence that renaming is strictly easier to solve than set agreement.     

Multi-dimensional color image storage and retrieval for a normal arbitrary quantum superposition state

Multi-dimensional color image processing has two difficulties: One is that a large number of bits are needed to store multi-dimensional color images, such as, a three-dimensional color image of $1024 \times 1024 \times 1024$ needs $1024 \times 1024 \times 1024 \times 24$  bits. The other one is that the efficiency or accuracy of image segmentation is not high enough for some images to be used in content-based image search. In order to solve the above problems, this paper proposes a new representation for multi-dimensional color image, called a $(n\,+\,1)$ -qubit normal arbitrary quantum superposition state (NAQSS), where $n$ qubits represent colors and coordinates of ${2^n}$ pixels (e.g., represent a three-dimensional color image of $1024 \times 1024 \times 1024$ only using 30 qubits), and the remaining 1 qubit represents an image segmentation information to improve the accuracy of image segmentation. And then we design a general quantum circuit to create the NAQSS state in order to store a multi-dimensional color image in a quantum system and propose a quantum circuit simplification algorithm to reduce the number of the quantum gates of the general quantum circuit. Finally, different strategies to retrieve a whole image or the target sub-image of an image from a quantum system are studied, including Monte Carlo sampling and improved Grover’s algorithm which can search out a coordinate of a target sub-image only running in $O(\sqrt{N/r} )$ where $N$ and $r$ are the numbers of pixels of an image and a target sub-image, respectively.     

Parameterized complexity of three edge contraction problems with degree constraints

For any graph class \(\mathcal{H}\) , the \(\mathcal{H}\) -Contraction problem takes as input a graph \(G\) and an integer \(k\) , and asks whether there exists a graph \(H\in \mathcal{H}\) such that \(G\) can be modified into \(H\) using at most \(k\) edge contractions. We study the parameterized complexity of \(\mathcal{H}\) -Contraction for three different classes \(\mathcal{H}\) : the class \(\mathcal{H}_{\le d}\) of graphs with maximum degree at most  \(d\) , the class \(\mathcal{H}_{=d}\) of \(d\) -regular graphs, and the class of \(d\) -degenerate graphs. We completely classify the parameterized complexity of all three problems with respect to the parameters \(k\) , \(d\) , and \(d+k\) . Moreover, we show that \(\mathcal{H}\) -Contraction admits an \(O(k)\) vertex kernel on connected graphs when \(\mathcal{H}\in \{\mathcal{H}_{\le 2},\mathcal{H}_{=2}\}\) , while the problem is \(\mathsf{W}[2]\) -hard when \(\mathcal{H}\) is the class of \(2\) -degenerate graphs and hence is expected not to admit a kernel at all. In particular, our results imply that \(\mathcal{H}\) -Contraction admits a linear vertex kernel when \(\mathcal{H}\) is the class of cycles.     

Informational correlation between two parties of a quantum system: spin-1/2 chains

We introduce the informational correlation \(E^{AB}\) between two interacting quantum subsystems \(A\) and \(B\) of a quantum system as the number of arbitrary parameters \(\varphi _i\) of a unitary transformation \(U^A\) (locally performed on the subsystem \(A\) ) which may be detected in the subsystem \(B\) by the local measurements. This quantity indicates whether the state of the subsystem \(B\) may be effected by means of the unitary transformation applied to the subsystem \(A\) . Emphasize that \(E^{AB}\ne E^{BA}\) in general. The informational correlations in systems with tensor product initial states are studied in more details. In particular, it is shown that the informational correlation may be changed by the local unitary transformations of the subsystem \(B\) . However, there is some non-reducible part of \(E^{AB}(t)\) which may not be decreased by any unitary transformation of the subsystem \(B\) at a fixed time instant \(t\) . Two examples of the informational correlations between two parties of the four-node spin-1/2 chain with mixed initial states are studied. The long chains with a single initially excited spin (the pure initial state) are considered as well.     

The categories L-\mathbf{Top}_{0} and L-\mathbf{Sob} as epireflective hulls

We show that the category \(L\) - \(\mathbf{Top}_{0}\) of \(T_{0}\) - \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}\) of \(L\) -topological spaces and the category \(L\) - \(\mathbf{Sob}\) of sober \(L\) -topological spaces is the epireflective hull of Sierpinski \(L\) -topological space in the category \(L\) - \(\mathbf{Top}_{0}\) .     

A study of single-machine scheduling problem to maximize throughput

We study inherent structural properties of a strongly NP-hard problem of scheduling $n$ jobs with release times and due dates on a single machine to minimize the number of late jobs. Our study leads to two polynomial-time algorithms. The first algorithm with the time complexity $O(n^3\log n)$ solves the problem if during its execution no job with some special property occurs. The second algorithm solves the version of the problem when all jobs have the same length. The time complexity of the latter algorithm is $O(n^2\log n)$ , which is an improvement over the earlier known algorithm with the time complexity $O(n^5)$ .     

Order optimal information spreading using algebraic gossip

In this paper we study gossip based information spreading with bounded message sizes. We use algebraic gossip to disseminate $k$ distinct messages to all $n$ nodes in a network. For arbitrary networks we provide a new upper bound for uniform algebraic gossip of $O((k+\log n + D)\varDelta )$ rounds with high probability, where $D$ and $\varDelta $ are the diameter and the maximum degree in the network, respectively. For many topologies and selections of $k$ this bound improves previous results, in particular, for graphs with a constant maximum degree it implies that uniform gossip is order optimal and the stopping time is $\varTheta (k + D)$ . To eliminate the factor of $\varDelta $ from the upper bound we propose a non-uniform gossip protocol, TAG, which is based on algebraic gossip and an arbitrary spanning tree protocol $\mathcal{S } $ . The stopping time of TAG is $O(k+\log n +d(\mathcal{S })+t(\mathcal{S }))$ , where $t(\mathcal{S })$ is the stopping time of the spanning tree protocol, and $d(\mathcal{S })$ is the diameter of the spanning tree. We provide two general cases in which this bound leads to an order optimal protocol. The first is for $k=\varOmega (n)$ , where, using a simple gossip broadcast protocol that creates a spanning tree in at most linear time, we show that TAG finishes after $\varTheta (n)$ rounds for any graph. The second uses a sophisticated, recent gossip protocol to build a fast spanning tree on graphs with large weak conductance. In turn, this leads to the optimally of TAG on these graphs for $k=\varOmega (\text{ polylog }(n))$ . The technique used in our proofs relies on queuing theory, which is an interesting approach that can be useful in future gossip analysis.     

Quantum secret sharing with continuous variable graph state

In this paper, we study several physically feasible quantum secret sharing (QSS) schemes using continuous variable graph state (CVGS). Their implementation protocols are given, and the estimation error formulae are derived. Then, we present a variety of results on the theory of QSS with CVGS. Any $(k,n)$ threshold protocol of the three specific schemes satisfying $\frac{n}{2}<k\le n$ , where $n$ denotes the total number of players and $k$ denotes the minimum number of players who can collaboratively access the secret, can be implemented by certain weighted CVGS. The quantum secret is absolutely confidential to any player group with number less than threshold. Besides, the effect of finite squeezing to these results is properly considered. In the end, the duality between two specific schemes is investigated.     

On space complexity of self-stabilizing leader election in mediated population protocol

Chatzigiannakis et al. (Lect Notes Comput Sci 5734:56–76, 2009) extended the Population Protocol (PP) of Angluin et al. (2004) and introduced the Mediated Population Protocol (MPP) by introducing an extra memory on every agent-to-agent communication link (i.e., edge), in order to model more powerful networks of mobile agents with limited resources. For a general distributed system of autonomous agents, Leader Election (LE) plays a key role in their efficient coordination. A Self-Stabilizing (SS) protocol has ideal properties required for distributed systems of huge numbers of not highly reliable agents typically modeled by PP or MPP; it does not require any initialization and tolerates a finite number of transient failures. Cai et al. (2009) showed that for a system of $n$ agents, any PP for SS-LE requires at least $n$ agent-states, and gave a PP with $n$ agent-states for SS-LE. In this paper, we show, for a system of $n$ agents, any MPP for SS-LE with 2 edge-states (i.e., 1 bit memory) on every edge requires at least $(1/2) \lg {n}$ agent-states, and give an MPP for SS-LE with $(2/3)n$ agent-states and 2 edge-states on every edge. Furthermore, we show that a constant number of edge-states on every edge do not help in designing an MPP for SS-LE with a constant number of agent-states, and that there is no MPP for SS-LE with 2 agent-states, regardless of the number of edge-states; the edge-state is not a complete alternative of the agent-state, although it can help in reducing the number of agent-states, when solving SS-LE.