Search results for "computational complexity"
showing 10 items of 249 documents
Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants
2018
We consider extensions of the two-variable guarded fragment, GF2, where distinguished binary predicates that occur only in guards are required to be interpreted in a special way (as transitive relations, equivalence relations, pre-orders or partial orders). We prove that the only fragment that retains the finite (exponential) model property is GF2 with equivalence guards without equality. For remaining fragments we show that the size of a minimal finite model is at most doubly exponential. To obtain the result we invent a strategy of building finite models that are formed from a number of multidimensional grids placed over a cylindrical surface. The construction yields a 2NExpTime-upper bou…
Quantum Query Complexity for Some Graph Problems
2004
The paper [4] by H. Buhrman and R. de Wolf contains an impressive survey of solved and open problems in quantum query complexity, including many graph problems. We use recent results by A.Ambainis [1] to prove higher lower bounds for some of these problems. Some of our new lower bounds do not close the gap between the best upper and lower bounds. We prove in these cases that it is impossible to provide a better application of Ambainis’ technique for these problems.
Work Partitioning on Parallel and Distributed Agent-Based Simulation
2017
Work partitioning is a key challenge with ap- plications in many scientific and technological fields. The problem is very well studied with a rich literature on both distributed and parallel computing architectures. In this paper we deal with the work partitioning problem for parallel and distributed agent-based simulations which aims at (i) balancing the overall load distribution, (ii) minimizing, at the same time, the communication overhead due to agents' inter-dependencies. We introduce a classification taxonomy of work partitioning strategies and present a space-based work partitioning ap- proach, based on a Quad-tree data structure, which enables to: identify a good space partitioning …
An Introduction to Computational Complexity
2016
This chapter is not strictly about algebra. However, this chapter offers a set of mathematical and computational instruments that will allow us to introduce several concepts in the following chapters. Moreover, the contents of this chapter are related to algebra as they are ancillary concepts that help (and in some cases allow) the understanding of algebra.
Understanding Quantum Algorithms via Query Complexity
2017
Query complexity is a model of computation in which we have to compute a function $f(x_1, \ldots, x_N)$ of variables $x_i$ which can be accessed via queries. The complexity of an algorithm is measured by the number of queries that it makes. Query complexity is widely used for studying quantum algorithms, for two reasons. First, it includes many of the known quantum algorithms (including Grover's quantum search and a key subroutine of Shor's factoring algorithm). Second, one can prove lower bounds on the query complexity, bounding the possible quantum advantage. In the last few years, there have been major advances on several longstanding problems in the query complexity. In this talk, we su…
Optimal Classical Random Access Codes Using Single d-level Systems
2015
Recently, in the letter [Phys. Rev. Lett. {\bf 114}, 170502 (2015)], Tavakoli et al. derived interesting results by studying classical and quantum random access codes (RACs) in which the parties communicate higher-dimensional systems. They construct quantum RACs with a bigger advantage over classical RACs compared to previously considered RACs with binary alphabet. However, these results crucially hinge upon an unproven assertion that the classical strategy "majority-encoding-identity-decoding" leads to the maximum average success probability achievable for classical RACs; in this article we provide a proof of this intuition. We characterize all optimal classical RACs and show that indeed "…
The computational power of continuous time neural networks
1997
We investigate the computational power of continuous-time neural networks with Hopfield-type units. We prove that polynomial-size networks with saturated-linear response functions are at least as powerful as polynomially space-bounded Turing machines.
An advanced variant of an interpolatory graphical display algorithm
2004
In this paper an advanced interpolatory graphical display algorithm based on cardinal B-spline functions is provided. It is well-known that B-spline functions are a flexible tool to design various scale rapresentations of a signal. The proposed method allows to display without recursion a function at any desiderable resolution so that only initial data and opportune vectors weight are involved. In this way the structure of the algorithm is independent across the scale and a computational efficiency is reached. In this paper mono and bi-dimensional vectors weight generated by means of centered cubic cardinal B-spline functions have been supplied. (© 2004 WILEY-VCH Verlag GmbH & Co. KGaA, Wei…
Use of wavelet for image processing in smart cameras with low hardware resources
2013
International audience; Images from embedded sensors need digital processing to recover high-quality images and to extract features of a scene. Depending on the properties of the sensor and on the application, the designer fits together different algorithms to process images. In the context of embedded devices, the hardware supporting those applications is very constrained in terms of power consumption and silicon area. Thus, the algorithms have to be compliant with the embedded specifications i.e. reduced computational complexity and low memory requirements. We investigate the opportunity to use the wavelet representation to perform good quality image processing algorithms at a lower compu…
Almost disjoint spanning trees: relaxing the conditions for completely independent spanning trees
2017
International audience; The search of spanning trees with interesting disjunction properties has led to the introduction of edge-disjoint spanning trees, independent spanning trees and more recently completely independent spanning trees. We group together these notions by dening (i, j)-disjoint spanning trees, where i (j, respectively) is the number of vertices (edges, respectively) that are shared by more than one tree. We illustrate how (i, j)-disjoint spanning trees provide some nuances between the existence of disjoint connected dominating sets and completely independent spanning trees. We prove that determining if there exist two (i, j)-disjoint spanning trees in a graph G is NP-comple…