Search results for "Computational complexity"
showing 10 items of 249 documents
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…
Irrelevant Features, Class Separability, and Complexity of Classification Problems
2011
In this paper, analysis of class separability measures is performed in attempt to relate their descriptive abilities to geometrical properties of classification problems in presence of irrelevant features. The study is performed on synthetic and benchmark data with known irrelevant features and other characteristics of interest, such as class boundaries, shapes, margins between classes, and density. The results have shown that some measures are individually informative, while others are less reliable and only can provide complimentary information. Classification problem complexity measurements on selected data sets are made to gain additional insights on the obtained results.
Efficient boundary integral-resonant mode expansion method implementation for full-wave analysis of passive devices based on circular waveguides with…
2013
In this study, the efficient full-wave analysis of passive devices composed of circular and arbitrarily-shaped waveguides is considered. For this purpose, the well-known boundary integral-resonant mode expansion (BI RME) method has been properly extended. Circular waveguides are used for resonant mode expansion, whereas the arbitrary contour is defined by any combination of straight, circular and elliptical segments, thus allowing the exact representation of the most widely used geometries. The proposed algorithm extends previous implementations of the BI RME method based on circular waveguides by considering circular and elliptical arcs for defining arbitrary geometries. Similarly, it allo…
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
2012
It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.
An Improved Detection Technique for Cyclic-Prefixed OFDM
2010
A novel Orthogonal Frequency Division Multiplexing detection technique compatible to standard (e.g. Wireless LAN) transmitters is proposed. It features enhanced error-rate performance with flexible computational complexity and robustness to imperfect channel estimation. It is based on exploitation of the redundancy available in the cyclic prefix after cancellation of interference from the preceding block. In order to show the effectiveness of our proposal, an analysis of computational complexity and a number of comparisons to the standard per-subcarrier receiver and a previously existing method in terms of error rates are reported.
Equivalence closure in the two-variable guarded fragment
2015
We consider the satisfiability and finite satisfiability problems for the extension of the two-variable guarded fragment in which an equivalence closure operator can be applied to two distinguished binary predicates. We show that the satisfiability and finite satisfiability problems for this logic are 2-ExpTime-complete. This contrasts with an earlier result that the corresponding problems for the full two-variable logic with equivalence closures of two binary predicates are 2-NExpTime-complete.
Population Monte Carlo Schemes with Reduced Path Degeneracy
2017
Population Monte Carlo (PMC) algorithms are versatile adaptive tools for approximating moments of complicated distributions. A common problem of PMC algorithms is the so-called path degeneracy; the diversity in the adaptation is endangered due to the resampling step. In this paper we focus on novel population Monte Carlo schemes that present enhanced diversity, compared to the standard approach, while keeping the same implementation structure (sample generation, weighting and resampling). The new schemes combine different weighting and resampling strategies to reduce the path degeneracy and achieve a higher performance at the cost of additional low computational complexity cost. Computer si…