Search results for "Computational complexity theory"
showing 10 items of 111 documents
A local complexity based combination method for decision forests trained with high-dimensional data
2012
Accurate machine learning with high-dimensional data is affected by phenomena known as the “curse” of dimensionality. One of the main strategies explored in the last decade to deal with this problem is the use of multi-classifier systems. Several of such approaches are inspired by the Random Subspace Method for the construction of decision forests. Furthermore, other studies rely on estimations of the individual classifiers' competence, to enhance the combination in the multi-classifier and improve the accuracy. We propose a competence estimate which is based on local complexity measurements, to perform a weighted average combination of the decision forest. Experimental results show how thi…
Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions
2007
For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) queries, which is optimal. It follows that the (2-o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.
Complexity of decision trees for boolean functions
2004
For every positive integer k we present an example of a Boolean function f/sub k/ of n = (/sub k//sup 2k/) + 2k variables, an optimal deterministic tree T/sub k/' for f/sub k/ of complexity 2k + 1 as well as a nondeterministic decision tree T/sub k/ computing f/sub k/. with complexity k + 2; thus of complexity about 1/2 of the optimal deterministic decision tree. Certain leaves of T/sub k/ are called priority leaves. For every input a /spl isin/ {0, 1}/sup n/ if any of the parallel computation reaches a priority leaves then its label is f/sub k/ (a). If the priority leaves are not reached at all then the label on any of the remaining leaves reached by the computation is f/sub k/. (a).
On the decision problem for the guarded fragment with transitivity
2002
The guarded fragment with transitive guards, [GF+TG], is an extension of GF in which certain relations are required to be transitive, transitive predicate letters appear only in guards of the quantifiers and the equality symbol may appear everywhere. We prove that the decision problem for [GF+TG] is decidable. This answers the question posed in (Ganzinger et al., 1999). Moreover, we show that the problem is 2EXPTIME-complete. This result is optimal since the satisfiability problem for GF is 2EXPTIME-complete (Gradel, 1999). We also show that the satisfiability problem for two-variable [GF+TG] is NEXPTIME-hard in contrast to GF with bounded number of variables for which the satisfiability pr…
On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity
2005
We study the finite satisfiability problem for the guarded fragment with transitivity. We prove that in case of one transitive predicate the problem is decidable and its complexity is the same as the general satisfiability problem, i.e. 2Exptime-complete. We also show that finite models for sentences of GF with more transitive predicate letters used only in guards have essentially different properties than infinite ones.
On the Computational Complexity of Binary and Analog Symmetric Hopfield Nets
2000
We investigate the computational properties of finite binary- and analog-state discrete-time symmetric Hopfield nets. For binary networks, we obtain a simulation of convergent asymmetric networks by symmetric networks with only a linear increase in network size and computation time. Then we analyze the convergence time of Hopfield nets in terms of the length of their bit representations. Here we construct an analog symmetric network whose convergence time exceeds the convergence time of any binary Hopfield net with the same representation length. Further, we prove that the MIN ENERGY problem for analog Hopfield nets is NP-hard and provide a polynomial time approximation algorithm for this p…
Descriptive Complexity, Lower Bounds and Linear Time
1999
This paper surveys two related lines of research: Logical characterizations of (non-deterministic) linear time complexity classes, and non-expressibility results concerning sublogics of existential second-order logic. Starting from Fagin’s fundamental work there has been steady progress in both fields with the effect that the weakest logics that are used in characterizations of linear time complexity classes are closely related to the strongest logics for which inexpressibility proofs for concrete problems have been obtained. The paper sketches these developments and highlights their connections as well as the obstacles that prevent us from closing the remaining gap between both kinds of lo…
Efficient and accurate methodology for solving multiserver retrial systems
2005
Proposed is a novel methodology for solving retrial systems which is based on the aggregation of levels of the Markov model beyond a given one. Its evaluation concludes that it is more accurate than previous approximations while requiring a low computational cost.
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…
New super-orthogonal space-time trellis codes using differential M-PSK for noncoherent mobile communication systems with two transmit antennas
2010
Published version of an article in the journal: Annals of Telecommunications-Annales Des Telecommunications. Also available from the publisher at: http://dx.doi.org/10.1007/s12243-010-0191-1 In this paper, we develop super-orthogonal space-time trellis codes (SOSTTCs) using differential binary phase-shift keying, quadriphase-shift keying and eight-phase shift keying for noncoherent communication systems with two transmit antennas without channel state information at the receiver. Based on a differential encoding scheme proposed by Tarokh and Jafarkhani, we propose a new decoding algorithm with reduced decoding complexity. To evaluate the performance of the SOSTTCs by way of computer simulat…