Search results for " Complexity theory"
showing 10 items of 131 documents
An Anonymous Delegatable Attribute-based Credential Scheme for a Collaborative E-health Environment
2019
We propose an efficient anonymous, attribute-based credential scheme capable of provisioning multi-level credential delegations. It is integrated with a mechanism to revoke the anonymity of credentials for resolving access disputes and making users accountable for their actions. The proposed scheme has a lower end-user computational complexity in comparison to existing credential schemes with delegatability and has a comparable level of performance with the credential standards of U-Prove and Idemix. Furthermore, we demonstrate how the proposed scheme can be applied to a collaborative e-health environment to provide its users with the necessary anonymous access with delegation capabilities.
Reducing Local Alphabet Size in Recognizable Picture Languages
2021
A recognizable picture language is defined as the projection of a local picture language defined by a set of two-by-two tiles, i.e. by a strictly-locally-testable (SLT) language of order 2. The family of recognizable picture languages is also defined, using larger k by k tiles, \(k>2\), by the projection of the corresponding SLT language. A basic measure of the descriptive complexity of a picture language is given by the size of the SLT alphabet using two-by-two tiles, more precisely by the so-called alphabetic ratio of sizes: SLT-alphabet/picture-alphabet. We study how the alphabetic ratio changes moving from two to larger tile sizes, and we obtain the following result: any recognizable pi…
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.
Feasibility of Ultra-short Term Complexity Analysis of Heart Rate Variability in Resting State and During Orthostatic Stress
2022
In this work, we study ultra-short term (UST) complexity of Heart Rate Variability (HRV) and its agreement with analysis of standard short-term (ST) HRV recordings obtained at rest and during orthostatic stress. Conditional Entropy (CE) measures have been computed using both a linear Gaussian approximation and a more accurate model-free approach based on nearest neighbors. The agreement between UST and ST indices has been compared via statistical tests and correlation analysis, suggesting the feasibility of exploiting faster algorithms and shorter time series for detecting changes in cardiovascular control during various states.
Fast Channel Estimation in the Transformed Spatial Domain for Analog Millimeter Wave Systems
2021
Fast channel estimation in millimeter-wave (mmWave) systems is a fundamental enabler of high-gain beamforming, which boosts coverage and capacity. The channel estimation stage typically involves an initial beam training process where a subset of the possible beam directions at the transmitter and receiver is scanned along a predefined codebook. Unfortunately, the high number of transmit and receive antennas deployed in mmWave systems increase the complexity of the beam selection and channel estimation tasks. In this work, we tackle the channel estimation problem in analog systems from a different perspective than used by previous works. In particular, we propose to move the channel estimati…
Random Feature Approximation for Online Nonlinear Graph Topology Identification
2021
Online topology estimation of graph-connected time series is challenging, especially since the causal dependencies in many real-world networks are nonlinear. In this paper, we propose a kernel-based algorithm for graph topology estimation. The algorithm uses a Fourier-based Random feature approximation to tackle the curse of dimensionality associated with the kernel representations. Exploiting the fact that the real-world networks often exhibit sparse topologies, we propose a group lasso based optimization framework, which is solve using an iterative composite objective mirror descent method, yielding an online algorithm with fixed computational complexity per iteration. The experiments con…
Inference of Spatio-Temporal Functions over Graphs via Multi-Kernel Kriged Kalman Filtering
2018
Inference of space-time varying signals on graphs emerges naturally in a plethora of network science related applications. A frequently encountered challenge pertains to reconstructing such dynamic processes, given their values over a subset of vertices and time instants. The present paper develops a graph-aware kernel-based kriged Kalman filter that accounts for the spatio-temporal variations, and offers efficient online reconstruction, even for dynamically evolving network topologies. The kernel-based learning framework bypasses the need for statistical information by capitalizing on the smoothness that graph signals exhibit with respect to the underlying graph. To address the challenge o…
Energy Efficiency Optimization for Multi-cell Massive MIMO : Centralized and Distributed Power Allocation Algorithms
2021
This paper investigates the energy efficiency (EE) optimization in downlink multi-cell massive multiple-input multiple-output (MIMO). In our research, the statistical channel state information (CSI) is exploited to reduce the signaling overhead. To maximize the minimum EE among the neighbouring cells, we design the transmit covariance matrices for each base station (BS). Specifically, optimization schemes for this max-min EE problem are developed, in the centralized and distributed ways, respectively. To obtain the transmit covariance matrices, we first find out the closed-form optimal transmit eigenmatrices for the BS in each cell, and convert the original transmit covariance matrices desi…
Reducing complexity in H.264/AVC motion estimation by using a GPU
2011
H.264/AVC applies a complex mode decision technique that has high computational complexity in order to reduce the temporal redundancies of video sequences. Several algorithms have been proposed in the literature in recent years with the aim of accelerating this part of the encoding process. Recently, with the emergence of many-core processors or accelerators, a new approach can be adopted for reducing the complexity of the H.264/AVC encoding algorithm. This paper focuses on reducing the inter prediction complexity adopted in H.264/AVC and proposes a GPU-based implementation using CUDA. Experimental results show that the proposed approach reduces the complexity by as much as 99% (100x of spe…
Simplified spiking neural network architecture and STDP learning algorithm applied to image classification
2015
Spiking neural networks (SNN) have gained popularity in embedded applications such as robotics and computer vision. The main advantages of SNN are the temporal plasticity, ease of use in neural interface circuits and reduced computation complexity. SNN have been successfully used for image classification. They provide a model for the mammalian visual cortex, image segmentation and pattern recognition. Different spiking neuron mathematical models exist, but their computational complexity makes them ill-suited for hardware implementation. In this paper, a novel, simplified and computationally efficient model of spike response model (SRM) neuron with spike-time dependent plasticity (STDP) lear…