Search results for "algorithm"
showing 10 items of 4887 documents
Computing the Probability for Data Loss in Two-Dimensional Parity RAIDs
2017
Parity RAIDs are used to protect storage systems against disk failures. The idea is to add redundancy to the system by storing the parity of subsets of disks on extra parity disks. A simple two-dimensional scheme is the one in which the data disks are arranged in a rectangular grid, and every row and column is extended by one disk which stores the parity of it.In this paper we describe several two-dimensional parity RAIDs and analyse, for each of them, the probability for dataloss given that f random disks fail. This probability can be used to determine the overall probability using the model of Hafner and Rao. We reduce subsets of the forest counting problem to the different cases and show…
Nondeterministic Unitary OBDDs
2017
We investigate the width complexity of nondeterministic unitary OBDDs (NUOBDDs). Firstly, we present a generic lower bound on their widths based on the size of strong 1-fooling sets. Then, we present classically “cheap” functions that are “expensive” for NUOBDDs and vice versa by improving the previous gap. We also present a function for which neither classical nor unitary nondeterminism does help. Moreover, based on our results, we present a width hierarchy for NUOBDDs. Lastly, we provide the bounds on the widths of NUOBDDs for the basic Boolean operations negation, union, and intersection.
Very Narrow Quantum OBDDs and Width Hierarchies for Classical OBDDs
2014
In the paper we investigate a model for computing of Boolean functions – Ordered Binary Decision Diagrams (OBDDs), which is a restricted version of Branching Programs. We present several results on the comparative complexity for several variants of OBDD models. We present some results on the comparative complexity of classical and quantum OBDDs. We consider a partial function depending on a parameter k such that for any k > 0 this function is computed by an exact quantum OBDD of width 2, but any classical OBDD (deterministic or stable bounded-error probabilistic) needs width 2 k + 1. We consider quantum and classical nondeterminism. We show that quantum nondeterminism can be more efficient …
Centering and Compound Conditionals under Coherence
2016
There is wide support in logic , philosophy , and psychology for the hypothesis that the probability of the indicative conditional of natural language, \(P(\textit{if } A \textit{ then } B)\), is the conditional probability of B given A, P(B|A). We identify a conditional which is such that \(P(\textit{if } A \textit{ then } B)= P(B|A)\) with de Finetti’s conditional event, B|A. An objection to making this identification in the past was that it appeared unclear how to form compounds and iterations of conditional events. In this paper, we illustrate how to overcome this objection with a probabilistic analysis, based on coherence, of these compounds and iterations. We interpret the compounds a…
The computational complexity of the relative robust shortest path problem with interval data
2004
Abstract The paper deals with the relative robust shortest path problem in a directed arc weighted graph, where arc lengths are specified as intervals containing possible realizations of arc lengths. The complexity status of this problem has been unknown in the literature. We show that the problem is NP -hard.
Periodicity and repetitions in parameterized strings
2008
AbstractOne of the most beautiful and useful notions in the Mathematical Theory of Strings is that of a Period, i.e., an initial piece of a given string that can generate that string by repeating itself at regular intervals. Periods have an elegant mathematical structure and a wealth of applications [F. Mignosi and A. Restivo, Periodicity, Algebraic Combinatorics on Words, in: M. Lothaire (Ed.), Cambridge University Press, Cambridge, pp. 237–274, 2002]. At the hearth of their theory, there are two Periodicity Lemmas: one due to Lyndon and Schutzenberger [The equation aM=bNcP in a free group, Michigan Math. J. 9 (1962) 289–298], referred to as the Weak Version, and the other due to Fine and …
Extremal problems of approximation theory in fuzzy context
1999
Abstract The problem of approximation of a fuzzy subset of a normed space is considered. We study the error of approximation, which in this case is characterized by an L -fuzzy number. In order to do this we define the supremum of an L -fuzzy set of real numbers as well as the supremum and the infimum of a crisp set of L -fuzzy numbers. The introduced concepts allow us to investigate the best approximation and the optimal linear approximation. In particular, we consider approximation of a fuzzy subset in the space L p m of differentiable functions in the L q -metric. We prove the fuzzy counterparts of duality theorems, which in crisp case allows effectively to solve extremal problems of the…
Quantum Algorithms for Learning Symmetric Juntas via Adversary Bound
2014
In this paper, we study the following variant of the junta learning problem. We are given oracle access to a Boolean function f on n variables that only depends on k variables, and, when restricted to them, equals some predefined function h. The task is to identify the variables the function depends on. This is a generalisation of the Bernstein-Vazirani problem (when h is the XOR function) and the combinatorial group testing problem (when h is the OR function). We analyse the general case using the adversary bound, and give an alternative formulation for the quantum query complexity of this problem. We construct optimal quantum query algorithms for the cases when h is the OR function (compl…
A class of label-correcting methods for the K shortest paths problem
2001
In this paper we deal with the problem of finding the first K shortest paths from a single origin node to all other nodes of a directed graph. In particular, we define the necessary and sufficient conditions for a set of distance label vectors, on the basis of which we propose a class of methods which can be viewed as an extension of the generic label-correcting method for solving the classical single-origin all-destinations shortest path problem. The data structure used is characterized by a set of K lists of candidate nodes, and the proposed methods differ in the strategy used to select the node to be extracted at each iteration. The computational results show that: 1. some label-correct…
Time-Efficient Quantum Walks for 3-Distinctness
2013
We present two quantum walk algorithms for 3-Distinctness. Both algorithms have time complexity $\tilde{O}(n^{5/7})$, improving the previous $\tilde{O}(n^{3/4})$ and matching the best known upper bound for query complexity (obtained via learning graphs) up to log factors. The first algorithm is based on a connection between quantum walks and electric networks. The second algorithm uses an extension of the quantum walk search framework that facilitates quantum walks with nested updates.