This paper studies the capacity of fast-fading channels from an algorithmic perspective, examining whether the channel capacity can be computed algorithmically or not. To address this question, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It is shown that certain computable continuous fading probability distribution functions yield capacities that are non-computable. Furthermore, the implications of this non-computability in information theory and coding are discussed, particularly the impossibility of designing universal algorithms that, given the fast-fading channel parameters and a predefined decoding error$\epsilon$, can compute codes operating at the maximum rate with a decoding error probability no higher than$\epsilon$.

As we advance towards 6G networks, the concept of ultra-reliability takes center stage. For ensuring ultra-reliabile communication the outage requirement is crucial. In this paper, the outage capacity of slow fading channels with additive white Gaussian noise is studied from a fundamental algorithmic point of view by addressing the question of whether or not the outage capacity can be algorithmically computed. For this purpose, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It is shown that there are fading channels having a computable continuous and differentiable probability density function whose outage capacity yields a non-computable number. Moreover, it is demonstrated that for these channels, it is impossible to algorithmically determine the minimum blocklength for transmission codes needed to operate at a certain precision relative to their outage capacity.

This paper studies the computability of the secrecy capacity of fast-fading wiretap channels from an algorithmic perspective, examining whether it can be computed algorithmically. To address this question, the concept of Turing machines is used, providing the fundamental performance limits of digital computers. It is shown that certain computable continuous fading probability distribution functions yield secrecy capacities that are non-computable numbers. Additionally, we assess the secrecy capacity's classification within the arithmetic hierarchy, revealing absence of computable achievability and converse bounds.

Designing capacity-achieving coding schemes for the band-limited additive colored Gaussian noise (ACGN) channel has been and is still a challenge. In this paper, the capacity of the band-limited ACGN channel is studied from a fundamental algorithmic point of view by addressing the question of whether or not the capacity can be algorithmically computed. To this aim, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It is shown that there are band-limited ACGN channels having computable continuous spectral densities whose capacity are non-computable numbers. Moreover, it is demonstrated that for those channels, it is impossible to find computable sequences of asymptotically sharp upper bounds for their capacities. Furthermore, the implications of the non-computability of the ACGN channel capacity in information theory and coding are discussed, particularly regarding the impossibility of computing achievable rates in the finite blocklength regime and the challenges of finding universal algorithms that compute capacity-achieving power spectral densities for the ACGN channel.

This paper examines the computability of optimal power allocation strategies for utility maximization and maxmin fairness. It is demonstrated that a computable constraint power function exists. However, when both total and individual power constraints are taken into account, it is determined that the optimal power allocation for maximizing network utility is not computable since every single power value is a non-computable number. Furthermore, it is established that within the same constraint context, both the max-min fairness level and its corresponding power values are non-computable numbers.

This paper investigates the computational complexity involved in determining the capacity of the band-limited additive colored Gaussian noise (ACGN) channel and its capacity-achieving input power spectral density (p.s.d.). A band-limited polynomial time computable continuous and strictly positive noise p.s.d. is constructed for the ACGN channel such that the computation of its corresponding capacity is$\# \mathrm{P}_{1}$-complete. This means that it is even more complex than problems that are$\text{NP}_{1}$-complete. Additionally, it is shown that computing the capacity-achieving input p.s.d. is also$\# \mathrm{P}_{1}$-complete. Furthermore, under the widely accepted assumption that$\text{FP}_{1}\neq\# \mathrm{P}_{1}$, there are two significant implications for the ACGN channel. First, there exists a polynomial time computable noise p.s.d. for which computing its capacity is not polynomial-time feasible, meaning the number of computational steps on a Turing Machine grows faster than any polynomial. Second, there is a polynomial time computable noise p.s.d. where determining its capacity-achieving input p.s.d. is also not achievable in polynomial time.

This paper explores the computability of the optimal point in convex problems with inequality constraints. It is shown that feasible sets, defined by computable convex functions, can yield non-computable optimal points for strictly convex and computable objective functions. Additionally, the optimal point of the Lagrangian dual problem associated with such convex constraints is also proven to be non-computable. Despite converging sequences of computable numbers towards the Lagrangian's optimal point, algorithmic control of the approximation error is shown to be impossible.

This paper explores the computational complexity involved in determining the capacity of the band-limited additive colored Gaussian noise (ACGN) channel and its capacity-achieving power spectral density (p.s.d.). The study reveals that when the noise p.s.d. is a strictly positive computable continuous function, computing the capacity of the band-limited ACGN channel becomes a #P1-complete problem within the set of polynomial time computable noise p.s.d.s. Meaning that it is even more complex than problems that are NP1-complete. Additionally, it is shown that computing the capacity-achieving distribution is also #P1-complete. Furthermore, under the widely accepted assumption that FP1≠ #P1, it has two significant implications for the ACGN channel. The first implication is the existence of a polynomial time computable noise p.s.d. for which the computation of its capacity cannot be performed in polynomial time, i.e., the number of computational steps on a Turing Machine grows faster than all polynomials. The second one is the existence of a polynomial time computable noise p.s.d. for which determining its capacity-achieving p.s.d. cannot be done within polynomial time. This implies that either the sequence of achievable rates with guaranteed distance to capacity is not polynomial time computable, or the corresponding blocklength sequence is not polynomial time computable.

The capacity of finite state channels (FSCs) with feedback has been expressed by a limit of a sequence of multi-letter expressions. Despite many efforts, a closed-form single-letter capacity characterization remains unknown to date. In this paper, the feedback capacity is studied from a fundamental algorithmic point of view by addressing the question of whether or not the capacity can be algorithmically computed. To this aim, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It is shown that the feedback capacity of FSCs is not Banach-Mazur computable and therefore also not Borel-Turing computable. It is further shown that it is even impossible to approximate the feedback capacity function of FSCs by a computable function. As a consequence, it is shown that computable achievability and converse can never be tight, which means that there are FSCs for which it is impossible to find computable tight upper and lower bounds. Furthermore, it is shown that the feedback capacity cannot be characterized as the maximization of a finite-letter formula of entropic quantities.

Designing capacity-achieving coding schemes for the band-limited additive colored Gaussian noise (ACGN) channel has been and is still a challenge. In this paper, the capacity of the band-limited ACGN channel is studied from a fundamental algorithmic point of view by addressing the question of whether or not the capacity can be algorithmically computed. For this purpose, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It is shown that there are band-limited ACGN channels having a computable continuous spectral density whose capacity is a non-computable number. Moreover, it is demonstrated that for these channels, it is impossible to find a computable sequence of asymptotically sharp upper bounds for their capacity.

The capacity of finite state channels (FSCs) with feedback has been expressed by a limit of a sequence of multi-letter expressions. Despite many efforts, a closed-form single-letter capacity characterization remains unknown to date. In this paper, the feedback capacity is studied from a fundamental algorithmic point of view by addressing the question of whether or not the capacity can be algorithmically computed. To this aim, the concept of Turing machines is used, which provides fundamental performance limits of digital computers. It is shown that the feedback capacity of FSCs is not Banach-Mazur computable and therefore also not Borel-Turing computable. As a consequence, it is shown that either achievability or converse (or both) is not Banach-Mazur computable, which means that there are FSCs for which it is impossible to find computable tight upper and lower bounds. Furthermore, it is shown that the feedback capacity cannot be characterized as the maximization of a finite-letter formula of entropic quantities.

Differential power analysis (DPA) attacks exploit the variance in power measurements of cryptographic devices to recover secret keys. What can an adversary achieve with power measurements? In this work, information-theoretic tools are used to quantity the amount of sensitive information revealed by a power measurement. It is shown that in order to find a secret key, an adversary needs to try a number of different keys. The number is exponential to the key size and the exponent is given by the key's entropy, conditioned on the power measurement.

The compound broadcast channel with confidential messages (BCC) generalizes the BCC by modeling the uncertainty of the channel. For the compound BCC, it is known only that the actual channel realization belongs to a pre-specified uncertainty set of channels and that it is constant during the entire transmission. For reliable and secure communication it is necessary to operate at a rate pair within the compound BCC capacity region. Therefore, the question of whether small variations of the uncertainty set lead to large losses of the compound BCC capacity region is of interest, and this problem is studied here. In particular, it is shown that the compound BCC model is robust, i.e., the capacity region depends continuously on the uncertainty set.

In this correspondence information theoretical tools are used to investigate the statistical properties of modeled cochlear nucleus globular bushy cell spike trains. The firing patterns are obtained from a simulation software that generates sample spike trains from any auditory input. Here we analyze for the first time the responses of globular bushy cells to voiced and unvoiced speech sounds. Classical entropy estimates, such as the direct method, are improved upon by considering a time-varying and time-dependent entropy estimate. With this method we investigated the relationship between the predictability of the neuronal response and the frequency content in the auditory signals. The analysis quantifies the temporal precision of the neuronal coding and the memory in the neuronal response.