Search results for "boolean"
showing 10 items of 98 documents
On the collision property of chaotic iterations based post-treatments over cryptographic pseudorandom number generators
2018
International audience; There is not a proper mathematical definition of chaos, we have instead a quite big amount of definitions, each of one describes chaos in a more or less general context. Taking in account this, it is clear why it is hard to design an algorithm that produce random numbers, a kind of algorithm that could have plenty of concrete appliceautifat (anul)d bions. However we must use a finite state machine (e.g. a laptop) to produce such a sequence of random numbers, thus it is convenient, for obvious reasons, to redefine those aimed sequences as pseudorandom; also problems arise with floating point arithmetic if one wants to recover some real chaotic property (i.e. propertie…
Qualitative methods of structural analysis : layer-based methods are informationally trivial
2000
Some methods of qualitative structural analysis, as MFA, are based on the analysis of layers (flow matrices generated at each iteration when the equilibrium of an input-output model is computed). MFA mixes the analysis of the pure structure of production (the technical coefficients) and of the final demand. I have demonstrated that all column-coefficient matrices (or row-coefficient matrices) computed from each layer are the same in MFA: the information brought by one layer is identical to those of another layer. For a given structure of production, the only element of variability over layers is caused by the flows that final demand generates.If the new definition of layers proposed by the …
Quadratically Tight Relations for Randomized Query Complexity
2020
In this work we investigate the problem of quadratically tightly approximating the randomized query complexity of Boolean functions R(f). The certificate complexity C(f) is such a complexity measure for the zero-error randomized query complexity R0(f): C(f) ≤R0(f) ≤C(f)2. In the first part of the paper we introduce a new complexity measure, expectational certificate complexity EC(f), which is also a quadratically tight bound on R0(f): EC(f) ≤R0(f) = O(EC(f)2). For R(f), we prove that EC2/3 ≤R(f). We then prove that EC(f) ≤C(f) ≤EC(f)2 and show that there is a quadratic separation between the two, thus EC(f) gives a tighter upper bound for R0(f). The measure is also related to the fractional…
Properties and application of nondeterministic quantum query algorithms
2006
Many quantum algorithms can be analyzed in a query model to compute Boolean functions where input is given by a black box. As in the classical version of decision trees, different kinds of quantum query algorithms are possible: exact, zero-error, bounded-error and even nondeterministic. In this paper, we study the latter class of algorithms. We introduce a fresh notion in addition to already studied nondeterministic algorithms and introduce dual nondeterministic quantum query algorithms. We examine properties of such algorithms and prove relations with exact and nondeterministic quantum query algorithm complexity. As a result and as an example of the application of discovered properties, we…
Recent Developments in Quantum Algorithms and Complexity
2014
We survey several recent developments in quantum algorithms and complexity: Reichardt’s characterization of quantum query algorithms via span programs [15]; New bounds on the number of queries that are necessary for simulating a quantum algorithm that makes a very small number of queries [2]; Exact quantum algorithms with superlinear advantage over the best classical algorithm [4].
Upper bound on the communication complexity of private information retrieval
1997
We construct a scheme for private information retrieval with k databases and communication complexity O(n 1/(2k−1) ).
Closedness Properties in EX-Identification of Recursive Functions
1998
In this paper we investigate in which cases unions of identifiable classes of recursive functions are also necessarily identifiable. We consider identification in the limit with bounds on mindchanges and anomalies. Though not closed under the set union, these identification types still have features resembling closedness. For each of them we find such n that 1) if every union of n - 1 classes out of U1;, . . ., Un is identifiable, so is the union of all n classes; 2) there are such classes U1;, . . ., Un-1 that every union of n-2 classes out of them is identifiable, while the union of n - 1 classes is not. We show that by finding these n we can distinguish which requirements put on the iden…
Unions of identifiable families of languages
1996
This paper deals with the satisfiability of requirements put on the identifiability of unions of language families. We consider identification in the limit from a text with bounds on mindchanges and anomalies. We show that, though these identification types are not closed under the set union, some of them still have features that resemble closedness. To formalize this, we generalize the notion of closedness. Then by establishing “how closed” these identification types are we solve the satisfiability problem.
Logical Consensus for Distributed Network Agreement
2008
In this paper we introduce a novel consensus mechanism where agents of a network are able to share logical values, or Booleans, representing their local opinions on e.g. the presence of an intruder or of a fire within an indoor environment. Under suitable joint conditions on agents? visibility and communication capability, we provide an algorithm generating a logical linear consensus system that is globally stable. The solution is optimal in terms of the number of messages to be exchanged and the time needed to reach a consensus. Moreover, to cope with possible sensor failure, we propose a second design approach that produces robust logical nonlinear consensus systems tolerating a maximum n…
Canonical Extensions of Conditional Probabilities and Compound Conditionals
2022
In this paper we show that the probability of conjunctions and disjunctions of conditionals in a recently introduced framework of Boolean algebras of conditionals are in full agreement with the corresponding operations of conditionals as defined in the approach developed by two of the authors to conditionals as three-valued objects, with betting-based semantics, and specified as suitable random quantities. We do this by first proving that the canonical extension of a full conditional probability on a finite algebra of events to the corresponding algebra of conditionals is compatible with taking subalgebras of events.