This paper considers the source coding problem with broadcast side information. The side information is sent to two receivers through a noisy broadcast channel. We provide an outer bound of the rate--distortion--bandwidth (RDB) quadruples and achievable RDB quadruples when the helper uses a separation-based scheme. Some special cases with full characterization are also provided. We then compare the separation-based scheme with the uncoded scheme in the quadratic Gaussian case.

We study pure disjoint $(r,δ)$-quantum locally recoverable codes (qLRCs) without assuming a stabilizer structure. We formulate local Knill--Laflamme conditions for recovery from up to $δ-1$ erasures within a recovery block, and introduce blockwise Shor--Laflamme and unitary weight enumerators that capture how error weight is distributed across recovery sets. We establish several properties of these enumerators and use them to derive a Singleton-like bound that strengthens the known bound for disjoint $(r,δ)$-qLRCs under a purity assumption, as well as a linear-programming upper bound on the code dimension. These results provide a non-stabilizer, weight-enumerator-based approach to the study of pure disjoint $(r,δ)$-qLRCs.

The capacity-distortion (C-D) trade-offs for joint state and message communications (JSMC) over single- and multi-user channels are investigated, where the transmitters have access to generalized state information and feedback while the receivers jointly decode the messages and estimate the channel state. A coding scheme is proposed based on backward simultaneous decoding of messages and compressed state descriptions without the need for the Wyner-Ziv random binning technique. For the point-to-point channel, the proposed scheme results in the optimal C-D function. For the state-dependent discrete memoryless degraded broadcast channel (SD-DMDBC), the successive refinement method is adopted for designing multi-stage state descriptions. With the simultaneous decoding approach, the derived achievable region is shown to be larger than the region obtained by the sequential decoding approach that is utilized in existing works. As for the state-dependent discrete memoryless multiple access channel (SD-DMMAC), in addition to the proposed method, Willem’s coding strategy is applied to enable partial collaboration between transmitters through the feedback links. Moreover, the state descriptions are shown to enhance both communication and state estimation performance. Examples are provided for the derived results to verify the analysis, either numerically or analytically. With particular focus, simple but representative integrated sensing and communications (ISAC) systems are also considered, and their fundamental performance limits are studied.

We consider a formalism ofquantum compiler functions– functions that map unitary matrices to corresponding gate-circuit approximations – and prove the infeasibility of digitally computing such functions. Since the gate-circuit model of quantum computing emerged, much research has been conducted to find algorithmic solutions to thequantum compiler problem. The renownedSolovay-Kitaev theoremproves the existence of quantum compiler functions that provide low-complexity gatecircuit approximations to arbitrary unitary matrices, which is indispensable for the practical feasibility of gate-based quantum computing. However, the mere existence of such functions does not imply theirrealizabilityby means of analgorithm– a constructive procedure executed by aTuring machine. In fact, no algorithm for computing any quantum compiler function is known today. The present article demonstrates that no such algorithm can exist. We prove that no quantum compiler function can satisfyBanach-Mazur computability, which is a formalization of algorithmic feasibility with (mathematically) weak requirements. In consequence, there definitely does not exist a Turing machine that computes any quantum compiler function in the above sense, nor can there exist aconstructive proofof the existence of any such function. Furthermore, we discuss proposed methods of quantum compiling and analyze them in the context of our results.

The maximum likelihood attack strategy is known to be the optimal attack strategy for an eavesdropper in a wiretap channel scenario with additive white Gaussian noise channels under the distinguishing security criterion. The main drawback of this optimal attack is its high computational complexity. While this complexity doesn’t hinder the eavesdropper since he has unlimited computing power, it does present a significant challenge for legitimate parties. For them, it is extremely difficult, if not impossible, to estimate the outcome of the optimal attacker strategy to validate the secrecy of their communication system. In this paper, we introduce a low complexity method for generating upper and lower bounds on the attack performance of the eavesdropper to validate the security against the maximum likelihood attack strategy. We theoretically establish that the derived bounds represent valid constraints on the attack success probability under suitable constraints. The validation method is based on list generation and can be used for any linear block code. Furthermore, we propose a list generation algorithm for this validation method and show different ways to further reduce the complexity. We compare the proposed validation method with state-of-the-art attack strategies in numerical simulations for various error-correcting codes.

This work proposes a unified framework for the joint estimation and control of mobile robots communicating over wireless channels. To this end, we consider a MIMO-OFDM point-to-point (P2P) link between a static base station (BS) and user equipment (UE) mounted on a robotic platform. In this setting, we study the particular scenario in which the robot must reach a target position while maintaining a high communication rate and estimating its pose from demodulated OFDM signals. We formulate this problem as a joint estimation and control task within a nonlinear, stochastic dynamical system. To address it, we leverage the iterative Linear Quadratic Gaussian (ILQG) method to derive a locally convergent and computationally efficient solution. Extensive simulations validate the proposed approach and shed light on the critical interplay between wireless communication and control, revealing an inherent trade-off between rate maximization and goal tracking, offering new insights into the co-design of next-generation autonomous, connected robotic systems.

Determining the period of a function is the main step in Shor’s factorization algorithm which is a cornerstone in the theory of quantum computing and a primary motivation for developing quantum computers. This paper investigates whether it is possible to have a universal Turing machine that is able to compute the minimum (or fundamental) period of a given periodic computable continuous function. It is shown that for every periodic computable continuous function, its fundamental period is always a computable number. Therefore, there always exists a specific Turing machine for computing the period of this function. Nevertheless, it is also shown that there exists no universal algorithm that is able to compute the period for all functions having periods that are known to be smaller than a given upper bound.

We present an information-theoretic framework for secure storage and message identification utilizing fully quantum physically unclonable functions (QPUFs). Extending prior models rooted in classical and hybrid classical-quantum PUFs, we propose a fully quantum setting that enables robust identification protocols in the presence of a powerful quantum wiretapper holding correlated side information. We derive achievable second-order identification rates under stringent privacy leakage constraints and show that secure identification is feasible whenever a positive secret key rate can be extracted from the QPUF output—establishing a quantum analogue of the classical dichotomy theorem. Furthermore, we demonstrate that augmenting the system with an auxiliary public quantum source enhances identification capacity without increasing privacy leakage. Our results provide a rigorous theoretical foundation for quantum-secure identification and storage, with implications for next-generation communication systems and adversarial environments requiring low-latency, energy-efficient quantum-secure storage protocols.

In this study, we examine different functions for the security layer of a seeded modular coding scheme for semantic security. We investigated the separation of the seed set into dispersing and non-dispersing seeds. The separation exists for all five implemented security functions in combination with all three tested error correcting codes. We show a simple procedure to reduce the probability of dispersing seeds for all security functions in two of three error correcting codes. Additionally, it was shown that Eve has an advantage in extracting information from her channel output if dispersing seeds are used. The simulations showed that this advantage can lead in special cases to a better information extraction despite larger encoding randomness. To the best of the authors’ knowledge, this is the first analytic comparison of different security functions for a seeded modular coding scheme of this kind.

Molecular communication (MC) enables information transfer via molecules, making it ideal for biomedical applications where traditional methods fall short. In many such scenarios, identifying specific events is more critical than decoding full messages, motivating the use of deterministic identification (DI). This paper investigates DI over discrete-time Poisson channels (DTPCs) with inter-symbol interference (ISI), a realistic setting due to channel memory effects. We consider memory scaling as K = 2κ log n, where κ represents the coding rate and n the code length. We improve the known upper bound on DI capacity under power constraints from $\frac{3}{2} + \kappa $ to $\frac{{1 + \kappa }}{2}$. Additionally, we present the first results on deterministic identification with feedback (DIF) in this context, providing a constructive lower bound. These findings enhance the theoretical understanding of MC and support more efficient, feedback-driven biomedical systems.

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 integrated sensing and communication (ISAC) systems with two rate-limited helpers who observe the channel state sequence and the feedback sequence, respectively. Depending on the timing to compress and use the state information, our proposed coding scheme gives an inner bound of the capacity-compression-distortion tradeoff region. The tradeoff is realized by sending part of the state information at the beginning of the transmission to facilitate the communication and compressing the remaining part together with the feedback signal. A special case with a tight bound is also provided.

We investigate deterministic identification over arbitrary memoryless channels under the constraint that the error probabilities of first and second kind are exponentially small in the block length$n$, controlled by reliability exponents$E_{1}, E_{2}>0$. We find that, in contrast to the case of slowly vanishing errors where the identifiable message length scales as$\Theta(n \log n)$, here linear scaling is restored, now as a function of the reliability exponents. We give upper and lower bounds on the ensuing ratereliability function in terms of (the logarithm of) the packing and covering numbers of the channel output set, which for small error exponents$E_{1}, E_{2}>0$are bounded below and above in terms of the product of the Minkowski dimension and$\log \min \left\{E_{1}, E_{2}\right\}$. These allow us to recover the previously observed slightly superlinear identification rates, and offer a different perspective for understanding them in more traditional information theory terms.

Multi-task large language models (MTLLMs) are important for many applications at the wireless edge, where users demand specialized models to handle multiple tasks efficiently. However, training MTLLMs is complex and exhaustive, particularly when tasks are subject to change. Recently, the concept of model fusion via task vectors has emerged as an efficient approach for combining fine-tuning parameters to produce an MTLLM. In this paper, the problem of enabling edge users to collaboratively craft such MTLMs via tasks vectors is studied, under the assumption of worst-case adversarial attacks. To this end, first the influence of adversarial noise to multi-task model fusion is investigated and a relationship between the so-called weight disentanglement error and the mean squared error (MSE) is derived. Using hypothesis testing, it is directly shown that the MSE increases interference between task vectors, thereby rendering model fusion ineffective. Then, a novel resilient MTLLM fusion (R-MTLLMF) is proposed, which leverages insights about the LLM architecture and fine-tuning process to safeguard task vector aggregation under adversarial noise by realigning the MTLLM. The proposed R-MTLLMF is then compared for both worst-case and ideal transmission scenarios to study the impact of the wireless channel. Extensive model fusion experiments with vision LLMs demonstrate R-MTLLMF's effectiveness, achieving close-to-baseline performance across eight different tasks in ideal noise scenarios and significantly outperforming unprotected model fusion in worst-case scenarios. The results further advocate for additional physical layer protection for a holistic approach to resilience, from both a wireless and LLM perspective.

This paper investigates the problem of computing capacity-cost ($\mathbf{C}-\mathbf{C}$) functions for continuous channels. Motivated by the Kullback-Leibler divergence (KLD) proximal reformulation of the classical Blahut-Arimoto (BA) algorithm, the Wasserstein distance is introduced to the proximal term for the continuous case, resulting in an iterative algorithm related to the Wasserstein gradient descent. Practical implementation involves moving particles along the negative gradient direction of the objective function's first variation in the Wasserstein space and approximating integrals by the importance sampling (IS) technique. Such formulation is also applied to the rate-distortion (R-D) function for continuous source spaces and thus provides a unified computation framework for both problems.

An information-theoretic analysis of secure authentication based on Quantum Physically Unclonable Functions (QPUF) is presented in this paper. The proposed model employs a secret key generated through QPUF to authenticate pre-enrolled user and device identities while maintaining secrecy and limiting privacy leakage. We analyze the system's robustness against an active adversary who exploits publicly available data to impersonate legitimate users with fraudulent inputs. Our analysis focuses on characterizing the capacity region of the adversary's false acceptance exponent alongside the privacy leakage under reliability conditions. We further demonstrate that the achievable capacity region in the quantum domain surpasses that of classical systems. Additionally, we derive an optimal trade-off among the false acceptance exponent, public storage rate, and privacy leakage rate, offering key insights into the system's asymptotic performance.

Physical Unclonable Functions (PUFs) have emerged as a powerful cryptographic tool for various applications due to their inherent physical uniqueness and unclonability. However, the advent of quantum computers has posed significant threats to classical PUFs. In response, Quantum PUFs (QPUFs), which exploit the principles of quantum mechanics, have been introduced as a robust alternative. This paper analyzes two key applications of QPUFs utilizing their distinctive output: secure storage and identification, from an information theoretic perspective. We establish achievability under different constraints and derive the secure storage capacity and a doubly exponential identification rate, even in the presence of an active adversary attempting to deceive the system by exploiting publicly stored data. We further demonstrate that within the quantum domain, we achieve higher rates compared to classical counterparts.

Many communication applications incorporate eventtriggered behavior, where the conventional Shannon capacity may not effectively gauge performance. Consequently, we advocate for the concept of identification capacity as a more suitable metric for assessing these systems. We consider deterministic identification codes for the Gaussian AWGN, the slow fading, and the fast fading channels with power constraints. We prove lower bounds on capacities for the slow and the fast fading channels with side information for a wide range of fading distributions. Additionally, we present the code construction with efficient encoding which achieves the lower bound on capacity both for the slow and the fast fading channels. At last, we prove the same lower bound on the capacity of the fast fading channel without side information, i.e., the same lower bound holds even when the receiver does not know the fading coefficients. As a result we show that compared with Shannon's message transmission paradigm we achieved completely different capacity scaling for deterministic identification codes for all relevant fading channels.

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.

This paper studies the effective convergence of iterative methods for solving convex minimization problems using block Gauss–Seidel algorithms. It investigates whether it is always possible to algorithmically terminate the iteration in such a way that the outcome of the iterative algorithm satisfies any predefined error bound. It is shown that the answer is generally negative. Specifically, it is shown that even if a computable continuous function which is convex in each variable possesses computable minimizers, a block Gauss-Seidel iterative method might not be able to effectively compute any of these minimizers. This means that it is impossible to algorithmically terminate the iteration such that a given performance guarantee is satisfied. The paper discusses two reasons for this behavior and gives simple and concrete examples.

Joint message and state transmission under arbitrarily varying jamming attack is investigated. An inner bound of the robust capacity-distortion region is provided, which includes the worst-case communication rate and the worst-case estimation rate. The bound is optimal for a special case of joint message and lossless state communication.

We study the problem of common randomness (CR) generation in a fundamental two-party communication scenario, where a sender and a receiver seek to agree-with high probability-on a shared random variable. Both parties observe independent and identically distributed (i.i.d.) samples from sources defined over a Polish alphabet with an arbitrary joint distribution. Communication is restricted to a unidirectional, minimally interactive exchange over a noisy, memoryless channel. For this setting, we establish single-letter lower and upper bounds on the CR capacity. These bounds coincide except possibly at a countable set of points where discontinuities may arise.

This paper aims at computing the capacity-distortion-cost (CDC) function for continuous memoryless channels, which is defined as the supremum of the mutual information between channel input and output, constrained by an input cost and an expected distortion of estimating channel state. Solving the optimization problem is challenging because the input distribution does not lie in a finite-dimensional Euclidean space and the optimal estimation function has no closed form in general. We propose to adopt the Wasserstein proximal point method and parametric models such as neural networks (NNs) to update the input distribution and estimation function alternately. To implement it in practice, the importance sampling (IS) technique is used to calculate integrals numerically, and the Wasserstein gradient descent is approximated by pushing forward particles. The algorithm is then applied to an integrated sensing and communications (ISAC) system, validating theoretical results at minimum and maximum distortion as well as the randomdeterministic trade-off.

This work introduces a Quantum PUF (QPUF)-based approach to enhance cryptographic key generation and secure storage. An information-theoretic model is developed to analyze trade-offs between key generation, secure storage, and privacy leakage under unconditional and conditional secrecy constraints. Additionally, the use of shared private keys is explored to achieve zero privacy leakage. The results extend classical and classical-quantum findings to the fully quantum regime, to provide a pathway toward robust authentication and data security and offering a foundation for next-generation hardware security.

Stochastic network codes for consensus testing (CT) via a relay are proposed, where each of two or more parties knows a message and can find out if all these messages are equal, e.g. as an integrity check in a decentralized storage system or the control of mobile autonomous robots. The proposed codes achieve the CT capacity for memoryless uplinks channels when common randomness (CR) is available and no local randomness is used. With only local randomness at the edge nodes, upper and lower bounds for the capacity are given. The lower bound is achieved by CR generation via decode-and-forward transmission, and then using a common-randomness (CR)-assisted code. The upper bound is imposed by the CT over the uplink, when this consists of independent parallel channels to the relay. A recent derandomization result for encoders shows that, unlike deterministic encoding and CR shared between both encoders, the use of local randomness prevents the relay from successfully testing consensus. Therefore, in the proposed coding scheme, the relay recodes only to transmit random seeds and message hashes generated with these seeds. This scheme relies on an underlying CT code based on almost-universal hashing, where hashing is done with random seeds.

The understanding of achievable rates for quantum identification is far behind that of quantum transmission, as well as classical identification and transmission. Notably, in the classical case, common randomness shared between Alice and Bob before communication begins can greatly enhance the identification capacity. In the quantum regime, pre-shared entanglement may have an even more profound impact on the quantum identification (ID) capacity. This paper presents a regularized expression for the quantum ID capacity with entanglement assistance and demonstrates how it grows with the entanglement rate. Additionally, we provide deeper insights into the nature of quantum ID capacity. Interestingly, while the classical ID capacity becomes unbounded with unlimited common randomness, we find that the quantum ID capacity remains bounded even with unlimited entanglement assistance. Additionally, we find that entanglement plays the same role as an additional noiseless channel that is amortized, i.e., only used to make the rate positive.

This paper presents a novel approach to enhance sensing capabilities in UAV-enabled MIMO-OFDM ISAC systems by leveraging UAV mobility as a mono-static radar. By integrating uniform planar arrays (UPAs) and modeling the UAV dynamics in$S E(3)$, we address key challenges such as 3D space sensing and trajectory design. We propose a target tracking scheme using extended Kalman filtering (EKF) in$S E(3)$, along with trajectory optimization based on the conditional Posterior Cramer-Rao bound (CPCRB). Numerical results demonstrate the effectiveness of the proposed trajectory design in enhancing performance of target tracking and physical parameter estimation in UAVenabled MIMO-OFDM ISAC systems.

This paper investigates secure communication over a broadcast channel in the presence of an unreliable cooperation link between the two decoders. Two messages are sent over the channel. One receiver aims to decode both messages while ensuring that the second message remains confidential from the other receiver. The second receiver is only interested in the first message, decoding either a part of it when the cooperation link fails or the entire message when the link is operational. A communication scheme is proposed that ensures reliability, confidentiality, and robustness against potential link failures. The capacity regions are characterized for both the discrete memoryless and the Gaussian version of the channel. Additionally, several notable special cases of the problem are examined.

Physically Unclonable Functions (PUFs) have emerged as critical primitives for secure authentication and key generation. However, classical PUFs are increasingly vulnerable to machine learning and quantum-enabled attacks. Quantum PUFs, leveraging the principles of quantum mechanics, provide a promising alternative offering information-theoretic security. In this work, we present an information-theoretic framework for two key applications of QPUFs: secret key generation and secure data storage. We rigorously characterize the trade-offs between achievable key and storage rates under various privacy leakage constraints—unconditional, conditional, and zero-leakage—extending classical results into the quantum domain. We derive single-letter capacity expressions based on Holevo information and analyze the impact of shared private randomness on achieving zero privacy leakage. Our results establish fundamental performance limits for QPUF-based security systems and lay the foundation for cryptographic key generation and storage protocols in future quantum-resilient communication infrastructures.

We introduce the concept of locally homomorphic channels (LHCs) as a framework for analyzing the composition and decomposition of channels that simulate functions. We establish an equivalence between a specific class of LHCs and function computation codes for noisy channels. Further, we show for LHCs composed of multiple parts, e.g., an encoder, a noisy channel, and a decoder, that each component is independently locally homomorphic. A key implication is that stochastic decoding offers only very limited improvements in reliability. In scenarios where two messages from a large set are encoded independently, such as in K-identification, we prove that, in general, at most one of the encoders can compress the messages to logarithmic size. This result has significant consequences: for instance, it implies that consensus testing (CT) over discrete memoryless multiple-access channels becomes impossible when the message set has double-exponential size. In contrast, independent encoders can be reliable in such a setting, when the number of messages is only exponential. We demonstrate this for the example of deterministic consensus testing over a pair of binary symmetric channels.

Identification capacity has been established as a relevant performance metric for various goal-/task-oriented applications, where the receiver may be interested in only a particular message that represents an event or a task. For example, in olfactory molecular communications (MCs), odors or pheromones, which are often a mixture of various molecule types, may signal nearby danger, food, or a mate. In this paper, we examine the identification capacity with deterministic encoder for the discrete affine Poisson channel which can be used to model MC systems with molecule counting receivers. We establish lower and upper bounds on the identification capacity in terms of features of the affinity matrix between the released molecules and receptors at the receiver. As a key finding, we show that even when the number of receptor types scales sub-linearly in the number of molecule types N, the number of reliably identifiable messages can grow super-exponentially with the rank of the affinity matrix, T, i.e., ~ 2(T log T)R, where R denotes the coding rate. We further derive lower and upper bounds on R, and show that the proposed capacity theorem includes several known results in the literature as its special cases.

Recent work on large language models (LLMs) has increasingly focused on post-training and alignment with datasets curated to enhance instruction following, world knowledge, and specialized skills. However, most post-training datasets used in leading open- and closed-source LLMs remain inaccessible to the public, with limited information about their construction process. This lack of transparency has motivated the recent development of open-source post-training corpora. While training on these open alternatives can yield performance comparable to that of leading models, systematic comparisons remain challenging due to the significant computational cost of conducting them rigorously at scale, and are therefore largely absent. As a result, it remains unclear how specific samples, task types, or curation strategies influence downstream performance when assessing data quality. In this work, we conduct the first comprehensive side-by-side analysis of two prominent open post-training datasets: Tulu-3-SFT-Mix and SmolTalk. Using the Magpie framework, we annotate each sample with detailed quality metrics, including turn structure (single-turn vs. multi-turn), task category, input quality, and response quality, and we derive statistics that reveal structural and qualitative similarities and differences between the two datasets. Based on these insights, we design a principled curation recipe that produces a new data mixture, TuluTalk, which contains 14% fewer samples than either source dataset while matching or exceeding their performance on key benchmarks. Our findings offer actionable insights for constructing more effective post-training datasets that improve model performance within practical resource limits. To support future research, we publicly release both the annotated source datasets and our curated TuluTalk mixture.

We investigate the feasibility of computing quantum gate-circuit emulation (QGCE) and quantum gate-circuit concatenation (QGCC) on digital hardware. QGCE serves the purpose of rewriting gate circuits comprised of gates from a varying input gate set to gate circuits formed of gates from a fixed target gate set. Analogously, QGCC serves the purpose of finding an approximation to the concatenation of two arbitrary elements of a varying list of input gate circuits in terms of another element from the same list. Problems of this kind occur regularly in quantum computing and are often assumed an easy task for the digital computers controlling the quantum hardware. Arguably, this belief is due to analogical reasoning: The classical Boolean equivalents of QGCE and QGCC are natively computable on digital hardware. In the present paper, we present two insights in this regard: Upon applying a rigorous theory of computability, QGCE and QGCC turn out to be uncomputable on digital hardware. The results remain valid when we restrict the set of feasible inputs for the relevant functions to one parameter families of fixed gate sets. Our results underline the possibility that several ideas from quantum-computing theory may require a rethinking to become feasible for practical implementation.

We investigate deterministic identification over arbitrary memoryless channels under the constraint that the error probabilities of first and second kind are exponentially small in the block length n, controlled by reliability exponents E1,E2≥ 0. In contrast to the regime of slowly vanishing errors, where the identifiable message length scales linearithmically as Θ(n log n), here we find that for positive exponents linear scaling is restored, now with a rate that is a function of the reliability exponents. We give upper and lower bounds on the ensuing rate-reliability function in terms of (the logarithm of) the packing and covering numbers of the channel output set, which for small error exponents E1,E2> 0 can be expanded in leading order as the product of the Minkowski dimension of a certain parametrisation the channel output set and log min{E1,E2}. These allow us to recover the previously observed slightly superlinear identification rates, and offer a different perspective for understanding them in more traditional information theory terms. We also show that even if only one of the two errors is required to be exponentially small, the linearithmic scaling is lost. We further illustrate our results with a discussion of the case of dimension zero, and extend them to classical-quantum channels and quantum channels with tensor product input restriction.

Many communication applications incorporate event-triggered behavior, where the conventional Shannon capacity may not effectively gauge performance. Consequently, we advocate for the concept of identification capacity as a more suitable metric for assessing these systems. We consider deterministic identification codes for the Gaussian AWGN, the slow fading, and the fast fading channels with power constraints. We prove lower bounds on capacities for the slow and the fast fading channels with side information for a wide range of fading distributions. Additionally, we present the code construction with efficient encoding which achieves the lower bound on capacity both for the slow and the fast fading channels. At last, we prove the same lower bound on the capacity of the slow and fast fading channel without side information, i.e., the same lower bound holds even when the receiver does not know the fading coefficients. As a result we show that compared with Shannon’s message transmission paradigm we achieved completely different message set scaling for deterministic identification codes for all relevant fading channels.

Split federated learning (SFL) is a compute-efficient paradigm in distributed machine learning (ML), where components of large ML models are outsourced to remote servers. A significant challenge in SFL, particularly when deployed over wireless channels, is the susceptibility of transmitted model parameters to adversarial jamming that could jeopardize the learning process. This is particularly pronounced for embedding parameters in large language models (LLMs) and vision language models (VLMs), which are learned feature vectors essential for domain understanding. In this paper, rigorous insights are provided into the influence of jamming embeddings in SFL by deriving an expression for the ML training loss divergence and showing that it is upper-bounded by the mean squared error (MSE). Based on this analysis, a physical layer framework is developed for resilient SFL with LLMs (R-SFLLM1) over wireless networks. R-SFLLM leverages wireless sensing data to gather information on the jamming directions-of-arrival (DoAs) for the purpose of devising a novel, sensing-assisted anti-jamming strategy while jointly optimizing beamforming, user scheduling, and resource allocation. Extensive experiments using both LLMs and VLMs demonstrate R-SFLLM’s effectiveness, achieving close-to-baseline performance across various natural language processing (NLP) and computer vision (CV) tasks, datasets, and modalities. The proposed methodology further introduces an adversarial training component, where controlled noise exposure significantly enhances the model’s resilience to perturbed parameters during training. The results show that more noise-sensitive models, such as RoBERTa, benefit from this feature, especially when resource allocation is unfair. It is also shown that worst-case jamming in particular translates into worst-case model outcomes, thereby necessitating the need for jamming-resilient SFL protocols.

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.

Distribution-preserving integrated sensing and communication is investigated in this paper. In addition to the distortion constraint, we impose another constraint on the distance between the reconstructed sequence distribution and the original state distribution to force the system to preserve the statistical property of the channel states. An inner bound of the distribution-preserving capacity-distortion region is provided with some capacity region results under special cases. Furthermore, we consider the case where the system aims to keep the reconstructed sequence secret from an eavesdropper who also observes the channel output and receives rate-limited side information about the estimator. An inner bound of the tradeoff region and a capacity-achieving special case are presented. In addition, we provide some numerical examples to illustrate the tradeoff between the communication rate, distortion, and the preservation of the distribution.

Following initial work by JaJa, Ahlswede and Cai, and inspired by a recent renewed surge in interest in deterministic identification (DI) via noisy channels, we consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets. Such a channel is essentially given by its output distributions as a subset in the probability simplex. Our main findings are that the maximum length of messages thus identifiable scales superlinearly as$R\,n\log n$with the block length n, and that the optimal rate R is bounded in terms of the covering (aka Minkowski, or Kolmogorov, or entropy) dimension d of a certain algebraic transformation of the output set:$\frac {1}{4} d \leq R \leq \frac {1}{2} d$. Remarkably, both the lower and upper Minkowski dimensions play a role in this result. Along the way, we present a Hypothesis Testing Lemma showing that it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code. Although we do not know the exact capacity formula, we can conclude that the DI capacity exhibits superactivation: there exist channels whose capacities individually are zero, but whose product has positive capacity. We also generalise these results to classical-quantum channels with finite-dimensional output quantum system, in particular to quantum channels on finite-dimensional quantum systems under the constraint that the identification code can only use tensor product inputs.

We investigate the problem of generating common randomness (CR) from a finite compound source aided by unidirectional communication over a rate-limited perfect channel. The two communicating parties observe independent and identically distributed (i.i.d.) samples of a finite compound source and aim to agree on a common random variable with high probability for every possible state. Both parties know the set of source states as well as their statistics. However, they don’t know the actual state. We establish a single-letter formula for the compound CR capacity in the presence of communication over the channel and study key properties of the compound CR capacity: superadditivity, concavity, and continuity. We also consider the case where there is no communication between the terminals, and only the source outputs observed by the terminal at the receiving end of the perfect channel are state-dependent. In this setting, we establish single-letter bounds on the compound CR capacity. The single-letter lower bound is derived under the assumption that the source distributions are pairwise distinct for all states. Finally, within the same setting, we propose a CR generation scheme for a two-state binary source example. Notably, this scheme does not depend on the previously mentioned assumption.

Communication over a classical multiple-access channel (MAC) with entanglement resources is considered, whereby two transmitters share entanglement resources a priori before communication begins. Leditzky et al. (2020) presented an example of a classical MAC, defined in terms of a pseudo telepathy game, such that the sum rate with entangled transmitters is strictly higher than the best achievable sum rate without such resources. Here, we establish inner and outer bounds on the capacity region for the general MAC with entangled transmitters, and show that the previous result can be obtained as a special case. It has long been known that the capacity region of the classical MAC under a message-average error criterion can be strictly larger than with a maximal error criterion (Dueck, 1978). We observe that given entanglement resources, the regions coincide. Furthermore, we address the combined setting of entanglement resources and conferencing, where the transmitters can also communicate with each other over rate-limited links. Using superdense coding, entanglement can double the conferencing rate.

In this paper, the problem of training large language models (LLMs) in split federated learning over real-world wireless networks is investigated. In the considered system, the embedding layers of an LLM are first computed at a client and then trans-mitted over a wireless MIMO-OFDM link to a server instance for further processing, continuing the forward- and initiating the backpropagation of the training to the originating client. Due to channel impairments and adversarial attacks, the server needs to compute the model losses and gradients using corrupted parameters such as embeddings in LLMs. The computation of the corresponding model losses is rigorously characterized using such perturbed embeddings and a direct connection to the communication mean-squared error (MSE) for models beyond simple neural networks is established. Subsequently, the communication errors are modeled as part of the training process, and a method to design beamforming, scheduling and power allocation is proposed, ensuring high task performance and model convergence even in the case of worst-case jamming. Results on two natural language processing tasks using different LLM architectures confirm the validity of the theoretical analysis and prove the effectiveness of the proposed wireless system design in terms of accuracy and F1 score.

Physical-layer network codes for consensus-testing (CT) via a relay are proposed, where each of two parties knows a message and can find out if all messages are equal, e.g. as an integrity check in a decentralized storage system or the control of mobile autonomous robots. By assumption, the encoders cannot randomize. The proposed codes achieve the CT capacity for channels with a memoryless uplink multiple-access channel that is a binary adder channel or a pair of q-ary symmetric or erasure channels. There, the capacity of noiseless uplinks can always be achieved, by using generalized deterministic identification (ID) codes for the uplink, testing consensus at the relay, and broadcasting the one-bit result using zero rate. For pairs of Gaussian channels and Gaussian adder channels, the capacity bounds equal those known for ID over certain noiseless uplinks, where the code sizes scale superexponentially in the block length. Using a recent derandomization result for decoders, it is shown that for general channels, the ID capacity of certain noiseless uplinks upper-bounds the CT capacity. In contrast, both for transmission coding for the uplink and additive linear network codes, the asymptotically achievable code sizes and necessary block lengths are shown to be suboptimal.

This paper introduces several techniques for minimal trellis construction for degenerate decoding of quantum stabilizer codes, specifically the minimal multi-goal trellis for the cosets of the stabilizer group S in the normalizer group N. The methods include a merging algorithm, a Shannon-product approach, and the BCJR-Wolf method. The study establishes the necessary properties of multi-goal trellises and bounds on the decoding complexity of the minimal multi-goal trellis using the sum-product Viterbi algorithm. The proposed multi-goal trellises decrease the decoding complexity by a factor O(n), where n is the code length.

In contrast to Shannon transmission codes, the size of identification (ID) codes for discrete memoryless channels (DMCs) experiences doubly exponential growth with the block length when randomized encoding is used. Additional enhancements within the ID paradigm can be realized through supplementary resources such as quantum entanglement, common randomness (CR), and feedback. Joint transmission and sensing demonstrate significant benefits over separation-based methods. Inspired by the significant impact of feedback on the ID capacity, our work delves into the realm of joint ID and sensing (JIDAS) for state-dependent multiple access channels (SD-MACs) with noiseless strictly casual feedback. Here, the senders aim to convey ID messages to the receiver while simultaneously sensing the channel states. We establish a lower bound on the capacity-distortion region of the SD-MACs. An example shows that JIDAS outperforms the separation-based approach.

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.

We consider the problem of computing gate-circuit approximations of quantum algorithms, i.e., unitary operators, from the perspective of computable (effective) analysis. The scientific community thinks the Solovay-Kitaev theorem a mile-stone in quantum compiling - the task of computing gate-circuit approximations - because it proves the existence of efficient quantum compilers in an analytic sense. However, since we cannot represent unitary operators in a mere analytical way on digital computers, contemporary digital implementations of quantum compiling resort to heuristic numerics and remain below the computational performance engineers hope to realize using the result of Solovay and Kitaev. This paper discusses quantum compiling within a framework of computable analysis, establishing a concept of computable unitary operators for digital computing based on the theory of Turing machines. Particularly, we prove that digital quantum compiling is uncomputable due to the underlying algebraic structure. Finally, we discuss several implications of our findings for heuristic digital implementations of quantum compiling, hinting toward possible research directions to thoroughly understand the relevant bottlenecks.

Motivated by deterministic identification via channels, where the encoder cannot use randomisation, we revisit the problem of identification via quantum channels with the additional restriction that the message encoding must use pure quantum states, rather than general mixed states. Together with the previously considered distinction between simultaneous and general decoders, this suggests a two-dimensional spectrum of different identification capacities, whose behaviour could a priori be very different. We demonstrate two new main results: first, we show that all of the four combinations (pure/mixed encoder, simultaneous/general decoder) have a double-exponentially growing code size, and that indeed the corresponding identification capacities are lower bounded by the classical transmission capacity for a general quantum channel, which is given by the Holevo-Schumacher- Westmoreland theorem. Secondly, we show that the simultaneous identification capacity of a quantum channel equals the simultaneous identification capacity with pure state encodings, thus leaving three linearly ordered identification capacities. By considering some simple examples we finally show that these three are all different: general identification capacity can be larger than pure-state-encoded identification capacity which in turn can be larger than pure-state-encoded simultaneous identification capacity,

In-Network Computing has brought computing and communication together at every communication node in the digital world, this work lays the foundations for doing the same in the quantum world, improving communication properties in the process - a combination of quantum computing and quantum communication. Full network softwarization, in-network intelligence, and massive connectivity will create an unprecedented demand for computing resources in the digital world. Accordingly, the scientific and industrial communities have begun to explore technologies such as quantum computing and have made significant efforts to demonstrate an algorithmic advantage for various problems. However, practical quantum computers are resource-inefficient and difficult to build. This article introduces a new communication paradigm leading to the concept of quantum in-network computing in the context of entanglement-assisted communication and computing for inherent distributed resilience and sensing. We review the fundamentals of digital hardware as characterized by Turing’s computability theory and demonstrate their relevance to mathematically rigorous characterizations of gate-based quantum computing. We then provide such a characterization using methods from effective analysis, leading to significant results that reveal the inherent theoretical limitations of universal gate-based quantum computers. These results support our assessment that gate-based quantum in-network computing is only possible through specialized, non-universal solutions that are seamlessly integrated with high-performance digital computing.

The lack of trustworthiness is a major downside of deep learning. To mitigate the associated risks clear obligations of deep learning models have been proposed via regulatory guidelines. Therefore, a crucial question is to what extent trustworthy deep learning can be realized. Establishing trust-worthiness requires that the factors influencing an algorithmic computation can be retraced, i.e., the algorithmic implementation is transparent. Motivated by the observation that the current evolution of deep learning models necessitates a change in computing technology, we derive a mathematical framework that enables us to analyze whether a transparent implementation in a given computing model is feasible. We exemplarily apply our trustworthiness framework to analyze deep learning approaches for inverse problems in digital and analog computing models represented by Turing and Blum-Shub-Smale Machines, respectively. Based on previous results, we find that Blum-Shub-Smale Machines have the potential to establish trustworthy solvers for inverse problems under fairly general conditions, whereas, Turing machines cannot guarantee trustworthiness to the same degree. For a longer version of this paper with more details and proofs, we refer to [1].

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.

We investigate the feasibility of computing quantum gate-circuit emulation (QGCE)functions and quantum gate-circuit concatenation (QGCC) functions on digital hardware. QGCE functions serve the purpose of rewriting gate-circuits comprised of gates from a varying (possibly universal) input gate-set to gate-circuits comprised of gates from a fixed target gate set. Analogously, QGCC functions serve the purpose of finding an approximation to the concatenation of two arbitrary elements of a varying list of input gate circuits in terms of another element from the same list. Problems of this kind occur regularly in quantum computing and are often considered an easy task for the digital computers controlling the quantum hardware. However, recent results employing a rigorous mathematical theory of computability indicate that this may not be the case. This paper extends the aforementioned theory, providing two relevant insights: Upon applying a rigorous theory of computability, QGCE functions and QGCC functions turn out to be uncomputable on digital hardware. The results remain valid when we restrict the set of feasible inputs for these functions to one-parameter families of fixed gate sets, which is applicable even to standard one-qubit systems. Our insights underline the possibility that several ideas from the theory of quantum computing may require a rethinking in order to become feasible for practical implementation.

Distribution-preserving integrated sensing and communication with secure reconstruction is investigated in this paper. In addition to the distortion constraint, we impose another constraint on the distance between the reconstructed sequence distribution and the original state distribution to force the system to preserve the statistical property of the channel states. An inner bound of the distribution-preserving capacity-distortion region is provided with some capacity region results under special cases. A numerical example demonstrates the tradeoff between the communication rate, reconstruction distortion and distribution preservation. Furthermore, we consider the case that the reconstructed sequence should be kept secret from an eavesdropper who also observes the channel output. An inner bound of the tradeoff region and a capacity-achieving special case are presented.

Following initial work by JaJa, and Ahlswede and Cai, and inspired by a recent renewed surge in interest in deterministic identification (DI) via noisy channels, we consider the problem in its generality for memoryless channels with finite output, but arbitrary input alphabets. Such a channel is essentially given by (the closure of) the subset of its output distributions in the probability simplex. Our main findings are that the maximum number of messages thus identifiable scales super-exponentially as$2^{Rn\log n}$with the block length$n$, and that the optimal rate$R$is upper and lower bounded in terms of the covering (aka Minkowski, or Kolmogorov, or entropy) dimension$d$of a certain algebraic transformation of the output set:$\frac{1}{4}d\leq R\leq\frac{1}{2}d$, Along the way, we present a Hypothesis Testing Lemma that shows it is sufficient to ensure pairwise reliable distinguishability of the output distributions to construct a DI code. Although we do not know the exact capacity formula, we can conclude that the DI capacity exhibits super-activation: there exist channels whose capacity is zero, but whose product has positive capacity. These results are then generalised to classical-quantum channels with finite-dimensional output quantum system (but arbitrary input alphabet), and in particular to quantum channels on finite-dimensional quantum systems under the constraint that the identification code can only use tensor product inputs.

We investigate the problem of generating common randomness (CR) from finite compound sources aided by unidirectional communication over rate-limited perfect channels. The two communicating parties, often referred to as terminals, observe independent and identically distributed (i.i.d.) samples of a finite compound source and aim to agree on a common random variable with a high probability for every possible realization of the source state. Both parties know the set of source states as well as their statistics. However, they are unaware of the actual realization of the source state. We establish a single-letter lower and upper bound on the compound CR capacity for the specified model. Furthermore, we present two special scenarios where the established bounds coincide.

Physical Unclonable Functions (PUFs) are hardware devices with the assumption of possessing inherent, non-clonable physical randomness which leads to unique pairs of inputs and outputs that provide a secure fingerprint for cryptographic protocols like Authentication. In the case of quantum PUFs (QPUFs), the input-output pairs consists of quantum states instead of classical bitstrings, offering advantages over classical PUFs (CPUFs) such as challenge reusability via public channels and non-reliance over any trusted party due to the no-cloning theorem. In recent literature, a generalized mathematical frame-work for studying QPUFs was developed, which paved the way for having QPUF models with provable security. It was proved that existential unforgeability against Quantum Polynomial Time (QPT) adversaries cannot be achieved by any random unitary QPUF. Since measurements are non-unitary quantum processes, we define a QPUF based on random von Neumann measurements. We prove that such a QPUF is existentially unforgeable. Thus, we introduce the first model in existing literature that depicts such a high level of provable security. We also prove that the Quantum Phase Estimation (QPE) protocol applied on a Haar random unitary serves as an approximate implementation for this kind of QPUF as it approximates a von Neumann measurement on the eigenbasis of the unitary.

An information-theoretic model is presented for a general quantum physically unclonable function (QPUF) that generates a bipartite classical-quantum output. We first define achievable secret key rate versus privacy leakage rate pairs featuring perfect secrecy and uniform distribution of the secret key. To analyze the secret key generation from this QPUF model, we focus on two cases: first, without any constraints on the storage of public information, i.e., the helper data, and second, with rate constraints on it. This, in turn, provides a solution for the case of privacy leakage constraint. We calculate the maximum secret key that a QPUF can generate and derive the capacity region corresponding to this definition of achievability.

Many communication applications are event-triggered, but current applications still use the Shannon communication model to transmit and decode messages. Due to the ever-growing number of users in communication networks, this leads to a weakening of performance. To counteract this, it makes sense to use post-Shannon methods such as deterministic identification (DI) codes. The information theory analysis carried out so far has shown how performance can be increased through DI codes. In this paper we provide a new constructive proof of the capacity of deterministic identification codes for discrete memoryless channels (DMC), while so far only existence proofs exist. Based on this idea, we implement DI codes of finite length and analyze their performance both analytically and experimentally. For the latter, we build a prototype using software-defined radios and a noise generator.

This paper derives an achievable rate-distortion (RD) region for the state-dependent discrete memoryless multiple access channel (SD-DMMAC), where the generalized feedback and causal side information are present at encoders, and the decoder performs the joint task of message decoding and state estimation. The Markov coding and backward-forward two-stage decoding schemes are adopted in the proof. This scenario is shown to be capable of modeling various integrated sensing and communication (ISAC) applications, including the monostatic-uplink system and multi-modal sensor networks, which are then studied as examples.

We investigate message identification over a K-sender Gaussian multiple access channel (K-GMAC). Unlike conventional Shannon transmission codes, the size of randomized identification (ID) codes experiences a doubly exponential growth in the code length. Improvements in the ID approach can be attained through additional resources such as quantum entanglement, common randomness (CR), and feedback. It has been demonstrated that an infinite capacity can be attained for a single-user Gaussian channel with noiseless feedback, irrespective of the chosen rate scaling. We establish the capacity region of both the K-sender Gaussian multiple access channel (K-GMAC) and the K-sender state-dependent Gaussian multiple access channel (K-SD-GMAC) when strictly causal noiseless feedback is available.

Abstract We introduce, motivate and study $$\varepsilon $$ ε -almost collision-flat universal (ACFU) hash functions $$f:\mathcal X\times \mathcal S\rightarrow \mathcal A$$ f : X × S → A . Their main property is that the number of collisions in any given value is bounded. Each $$\varepsilon $$ ε -ACFU hash function is an $$\varepsilon $$ ε -almost universal (AU) hash function, and every $$\varepsilon $$ ε -almost strongly universal (ASU) hash function is an $$\varepsilon $$ ε -ACFU hash function. We study how the size of the seed set $$\mathcal S$$ S depends on $$\varepsilon ,|\mathcal X |$$ ε , | X | and $$|\mathcal A |$$ | A | . Depending on how these parameters are interrelated, seed-minimizing ACFU hash functions are equivalent to mosaics of balanced incomplete block designs (BIBDs) or to duals of mosaics of quasi-symmetric block designs; in a third case, mosaics of transversal designs and nets yield seed-optimal ACFU hash functions, but a full characterization is missing. By either extending $$\mathcal S$$ S or $$\mathcal X$$ X , it is possible to obtain an $$\varepsilon $$ ε -ACFU hash function from an $$\varepsilon $$ ε -AU hash function or an $$\varepsilon $$ ε -ASU hash function, generalizing the construction of mosaics of designs from a given resolvable design (Gnilke et al. in Des. Codes Cryptogr. 86(1):85–95, 2017). The concatenation of an ASU and an ACFU hash function again yields an ACFU hash function. Finally, we motivate ACFU hash functions by their applicability in privacy amplification.

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.

This paper investigates the complexity of computing the minimum mean square prediction error for wide-sense stationary stochastic processes. It is shown that if the spectral density of the stationary process is a strictly positive, computable continuous function then the minimum mean square error (MMSE) is always a computable number. Nevertheless, we also show that the computation of the MMSE is a$\# P_{1}$complete problem on the set of strictly positive, polynomial-time computable, continuous spectral densities. This means that if, as widely assumed,$FP_{1} \neq \# P_{1}$, then there exist strictly positive, polynomial-time computable continuous spectral densities for which the computation of the MMSE is not polynomial-time computable. These results show in particular that under the widely accepted assumptions of complexity theory, the computation of the MMSE is generally much harder than an$NP_{1}$complete problem.

We investigate the problem of message transmission and the problem of common randomness (CR) generation over single-user multiple-input multiple-output (MIMO) slow fading channels with average input power constraint, additive white Gaussian noise (AWGN), arbitrary state distribution and with complete channel state information available at the receiver side (CSIR). We derive a lower and an upper bound on the outage transmission capacity of MIMO slow fading channels for arbitrary state distribution and show that the bounds coincide except possibly at points of discontinuity of the outage transmission capacity, of which there are, at most, countably many. Such discontinuity issues might occur because the channel state distribution is arbitrary. We also establish the capacity of a specific compound MIMO Gaussian channel in order to prove the lower bound on the outage transmission capacity. Furthermore, we define the outage CR capacity for a two-source model with unidirectional communication over a MIMO slow fading channel with arbitrary state distribution and establish a lower and an upper bound on it using our bounds on the outage transmission capacity of the MIMO slow fading channel.

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.

Optimization problems are a staple of today’s scientific and technical landscape. However, at present, solvers of such problems are almost exclusively run on digital hardware. Using Turing machines as a mathematical model for any type of digital hardware, in this paper, we analyze fundamental limitations of this conceptual approach of solving optimization problems. Since in most applications, the optimizer itself is of significantly more interest than the optimal value of the corresponding function, we will focus on computability of the optimizer. In fact, we will show that in various situations the optimizer is unattainable on Turing machines and consequently on digital computers. Moreover, even worse, there does not exist a Turing machine, which approximates the optimizer itself up to a certain constant error. We prove such results for a variety of well-known problems from very different areas, including artificial intelligence, financial mathematics, and information theory, often deriving the even stronger result that such problems are not Banach-Mazur computable, also not even in an approximate sense.

As we become more and more dependent on communication technologies, resilience against any attacks on communication networks is important to guarantee the digital sovereignty of our society. New developments of communication networks approach the problem of resilience through in-network computing approaches for higher protocol layers, while the physical layer remains an open problem. This is particularly true for wireless communication systems which are inherently vulnerable to adversarial attacks due to the open nature of the wireless medium. In denial-of-service (DoS) attacks, an active adversary is able to completely disrupt the communication and it has been shown that Turing machines are incapable of detecting such attacks. As Turing machines provide the fundamental limits of digital information processing and therewith of digital twins, this implies that even the most powerful digital twins that preserve all information of the physical network error-free are not capable of detecting such attacks. This stimulates the question of how powerful the information processing hardware must be to enable the detection of DoS attacks. Therefore, in this paper the need of neuromorphic twins is advocated and by the use of Blum-Shub-Smale machines a first implementation that enables the detection of DoS attacks is shown. This result holds for both cases of with and without constraints on the input and jamming sequences of the adversary.

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.

Deterministic K-Identification (DKI) for the binary symmetric channel (BSC) is developed. A full characterization of the DKI capacity for such a channel, with and without the Hamming weight constraint, is established. As a key finding, we find that for deterministic encoding the number of identifiable messages$K$may grow exponentially with the codeword length$n$, i.e.,$K\ =\ 2^{\kappa n}$, where$\kappa$is the target identification rate. Furthermore, the eligible region for$\kappa$as a function of the channel statistics, i.e., the crossover probability, is determined.

In this paper, we investigate the fundamental limits of MIMO-OFDM integrated sensing and communications (ISAC) systems based on a Bayesian Cramér-Rao bound (BCRB) analysis. We derive the BCRB for joint channel parameter estimation and data symbol detection, in which a performance trade-off between both functionalities is observed. We formulate the optimization problem for a linear precoder design and propose the stochastic Riemannian gradient descent (SRGD) approach to solve the non-convex problem. We analyze the optimality conditions and show that SRGD ensures convergence with high probability. The simulation results verify our analyses and also demonstrate a fast convergence speed. Finally, the performance trade-off is illustrated and investigated.

Communication over a classical multiple-access channel (MAC) with quantum entanglement resources is considered, whereby two transmitters share entanglement resources a priori. Leditzky et al. (2020) presented an example, defined in terms of a pseudo telepathy game, such that the sum rate with entangled transmitters is strictly higher than the best achievable sum rate without such resources. Here, we establish inner and outer bounds on the capacity region for the general MAC with entangled transmitters, and show that the previous result can be obtained as a special case. It has long been known that the capacity region of the classical MAC under a message-average error criterion can be strictly larger than with a maximal error criterion (Dueck, 1978). We observe that given entanglement resources, the regions coincide.

This paper proposes a system architecture that embeds semantically-secure information-theoretic physical layer security (IT-PLS) non-intrusively into a 5G New Radio (NR) system in order to protect uplink transmissions via physical uplink control channels (PUCCH) against post-quantum eaves-dropping attacks. We implement a proof of concept of such system employing a code construction based on a modular coding scheme with a universal hash function that ensures semantic secrecy. We conduct link-level simulations of wiretap channels under different frequency-selective fading conditions and noise characteristics in order to evaluate the performance of such implementation for slow and fast fading scenarios. We model them using tapped delay line channel models involving rural and urban scenarios with line-of-sight (LOS) and non-LOS radio conditions, as specified by the 3GPP TR 38.901. We characterize such system by measuring the distinguishing error rate, block error rate, and secrecy outage probability under different time-varying fading channels. Our case study outlines how IT-PLS can be transparently embedded into future 6G systems as well.

This paper compares different algorithms to check semantic security on AWGN wiretap channels. Each algorithm provides upper and lower bounds on the performance of an attack strategy that is close to the best attack strategy. The advantage of these algorithms is that they have lower computational complexity compared to the best attack strategy. We also show that the proposed algorithms can be further improved by including cyclic redundancy check bits and parity check bits generated in the algorithms, for example, when polar codes or LDPC codes according to the 5G standard are used in the coding layer. Finally, we show the compatibility of the algorithms for both polar codes and LDPC codes.

Physical law learning is the ambiguous attempt at automating the derivation of governing equations with the use of machine learning techniques. This paper shall serve as a first step to build a comprehensive theoretical framework for learning physical laws, aiming to provide reliability to according algorithms. One key problem consists in the fact that the governing equations might not be uniquely determined by the given data. We will study this problem in the common situation that a physical law is described by an ordinary or partial differential equation. For various different classes of differential equations, we provide both necessary and sufficient conditions for a function from a given function class to uniquely determine the differential equation which is governing the phenomenon. We then use our results to determine in extensive numerical experiments whether a function solves a differential equation uniquely.

We consider the task of converting different digital descriptions of analog bandlimited signals and systems into each other. Albeit fundamental, the problem of finding the proper digital description of analog information is crucial to digital twinning. The latter is an emerging concept in the field of digital data processing that is regularly mentioned as key approach in the optimization of future communication technologies like 6G. We prove that quantities such as the peak-to-average power ratio and the bounded-input/bounded-output norm, which determine the behavior of the real-world analog system, cannot generally be determined from the system's digital twin, depending on which of the above-mentioned descriptions is chosen. As a main result, we introduce a new digital description of analog signals and systems and prove it to be algorithmically more powerful than the traditional description based on Shannon's sampling approach.

We study a two-source model for common randomness (CR) generation in which the sender Alice and the receiver Bob generate a common random variable with a high probability of agreement by observing independent and identically distributed (i.i.d.) samples of correlated sources on countably infinite alphabets. The two parties are additionally allowed to communicate over a noisy memoryless channel. In our work, we establish a single-letter lower and upper-bound on the CR capacity for the proposed model. This is a challenging scenario because some of the finite alphabet properties, namely of the entropy can not be extended to the countably infinite case. We use a generalized typicality criterion, called unified typicality, which can be applied to random variables on countably infinite alphabets.

Wireless channel sensing is one of the key enablers for integrated sensing and communication (ISAC) which helps communication networks understand the surrounding environment. In this work, we consider MIMO-OFDM systems and aim to design optimal and robust waveforms for accurate channel parameter estimation given allocated OFDM resources. The Fisher information matrix (FIM) is derived first, and the waveform design problem is formulated by maximizing the log determinant of the FIM. We then consider the uncertainty in the parameters and state the stochastic optimization problem for a robust design. We propose the Riemannian Exact Penalty Method via Smoothing (REPMS) and its stochastic version SREPMS to solve the constrained non-convex problems. In simulations, we show that the REPMS yields comparable results to the semidefinite relaxation (SDR) but with a much shorter running time. Finally, the designed robust waveforms using SREMPS are investigated, and are shown to have a good performance under channel perturbations.

Several applications of molecular communications (MC) feature an alarm-prompt behavior for which the prevalent Shannon capacity may not be the appropriate performance metric. The identification capacity as an alternative measure for such systems has been motivated and established in the literature. In this paper, we study deterministic identification (DI) for the discrete-time Poisson channel (DTPC) with intersymbol interference (ISI) where the transmitter is restricted to an average and a peak molecule release rate constraint. Such a channel serves as a model for diffusive MC systems featuring long channel impulse responses and employing molecule counting receivers. We derive lower and upper bounds on the DI capacity of the DTPC with ISI when the number of ISI channel taps$K$may grow with the codeword length$n$(e.g., due to increasing symbol rate). As a key finding, we establish that for deterministic encoding, the codebook size scales as$2^{(n\log n)R}$assuming that the number of ISI channel taps scales as$K=2^{\kappa\log n}$, where$R$is the coding rate and$\kappa$is the ISI rate. Moreover, we show that optimizing$\kappa$leads to an effective identification rate [bits/s] that scales linearly with$n$, which is in contrast to the typical transmission rate [bits/s] that is independent of$n$.

Sixth Generation (6G) wireless networks will become the system-critical infrastructure for the modern information society. For this reason, 6G communication schemes must fulfill resilience by design. Because of its probabilistic nature, a wireless communication link varies in the ability to transfer information from a transmitter to a legitimate receiver. Additionally, interference generated by malicious nodes performing attacks to achieve Denial-of-Service (DoS) may corrupt the communication link. The Arbitrarily Varying Channel (AVC) model captures this vulnerability. The network must be able to algorithmically detect a DoS attack to ensure resilience by design. We investigate the detectability of these attacks in a detection framework based on Turing computability. We show that the task of algorithmic detection of DoS attacks is infeasible when communicating over AVCs with state constraints.

The duality between time- and frequency-domain representations of information-carrying signals is an established cornerstone of information theory. In terms of computability and signal processing, asymptotically-vanishing sequences are well-behaved in the time-domain, since they can be equipped with Banach-Space norms. It is then possible to define computable asymptotically-vanishing sequences, each of which is characterized by an effective global approximation procedure. In this paper, we investigate whether the time-frequency duality preserves these characteristics, i.e., whether the image of asymptotically-vanishing sequences under the Z-Transform yields a set of computationally well-behaved functions. In particular, we classify the associated radius of convergence into the arithmetical hierarchy of definable numbers by Zheng and Weihrauch, and, as a corollary, present that it may attain non-computable values. We then proceed to investigate the computability of upper and lower bounds on the radius of convergence, as well as several related decidability problems. Lastly, we subsume our insights into a collection of contemporary results on the fundamental limits of numerical techniques in signal processing and information theory.

We consider a standard two-source model for uniform common randomness (UCR) generation, in which Alice and Bob observe independent and identically distributed (i. i. d.) samples of a correlated finite source and where Alice is allowed to send information to Bob over an arbitrary single-user channel. We study the ϵ-UCR capacity for the proposed model, defined as the maximum common randomness rate one can achieve such that the probability that Alice and Bob do not agree on a common uniform or nearly uniform random variable does not exceed ϵ. We establish a lower and an upper bound on the ϵ-UCR capacity using the bounds on the ϵ-transmission capacity proved by Verdú and Han for arbitrary point-to-point channels.A detailed version with all proofs, explanations and more discussions can be found in [1].

In the identification (ID) scheme proposed by Ahlswede and Dueck, the receiver only checks whether a message of special interest to him has been sent or not. In contrast to Shannon transmission codes, the size of ID codes for a Discrete Memoryless Channel (DMC) grows doubly exponentially fast with the blocklength, if randomized encoding is used. This groundbreaking result makes the ID paradigm more efficient than the classical Shannon transmission in terms of necessary energy and hardware components. Further gains can be achieved by taking advantage of additional resources such as feedback. We study the problem of joint ID and channel state estimation over a DMC with independent and identically distributed (i.i.d.) state sequences. The sender simultaneously sends an ID message over the DMC with a random state and estimates the channel state via a strictly causal channel output. The random channel state is available to neither the sender nor the receiver. For the proposed system model, we establish a lower bound on the ID capacity-distortion function.

The Binomial channel serves as a fundamental model for molecular communication (MC) systems employing molecule-counting receivers. Here, deterministic identification (DI) is addressed for the discrete-time Binomial channels (DTBC), subject to an average and a peak constraint on the molecule release rate. We establish that the number of different messages that can be reliably identified for the DTBC scales as 2(n log n)R, where n and R are the codeword length and coding rate, respectively. Lower and upper bounds on the DI capacity of the DTBC are developed.

ε-Almost Collision-Flat Universal (ACFU) hash functions are defined and analyzed. They are motivated by their use in achieving information-theoretic key indistinguishability in privacy amplification. Lower bounds for the size of the seed set are given. A general method is presented by which to construct an ε-ACFU hash function from any ε-almost universal hash function. Several examples are studied. In particular, it turns out that all security functions known so far which achieve key indistinguishability universally are ε-ACFU hash functions.

In this paper we show a way to check semantic security for AWGN wiretap channels. We introduce low complexity decoding methods that provide upper and lower bounds to the performance of an attack strategy that closely resembles the best attack strategy, which has the problem of large computational complexity. We show the assumptions under which these methods can be applied and compare simulation results of the bounds to the performance of the best attack strategy. We use a seeded modular coding scheme, which consists of a coding layer and a security layer. For the coding layer we use polar codes, but the method is neither restricted to the seeded modular coding scheme nor to the polar codes.

The distributed source coding problem is extended by positing that noisy measurements of a remote source are the correlated random variables that should be reconstructed at another terminal. We consider a secure and private distributed lossy source coding problem with two encoders and one decoder such that (i) all terminals noncausally observe a noisy measurement of the remote source; (ii) a private key is available to each legitimate encoder and all private keys are available to the decoder; (iii) rate-limited noiseless communication links are available between each encoder and the decoder; (iv) the amount of information leakage to an eavesdropper about the correlated random variables is defined assecrecyleakage, andprivacyleakage is measured with respect to the remote source; and (v) two passive attack scenarios are considered, where a strong eavesdropper can access both communication links and a weak eavesdropper can choose only one of the links to access. Inner and outer bounds on the rate regions defined under secrecy, privacy, communication, and distortion constraints are derived for both passive attack scenarios. When one or both sources should be reconstructed reliably, the rate region bounds are simplified.

The bandwidth of a signal is an important physical property that is of relevance in many signal- and information-theoretic applications. In this paper we study questions related to the computability of the bandwidth of computable bandlimited signals. To this end we employ the concept of Turing computability, which exactly describes what is theoretically feasible and can be computed on a digital computer. Recently, it has been shown that there exist computable bandlimited signals with finite energy, the actual bandwidth of which is not a computable number, and hence cannot be computed on a digital computer. In this work, we consider the most general class of band-limited signals, together with different computable descriptions thereof. Among other things, our analysis includes a characterization of the arithmetic complexity of the bandwidth of such signals and yields a negative answer to the question of whether it is at least possible to compute non-trivial upper or lower bounds for the bandwidth of a bandlimited signal. Furthermore, we relate the problem of bandwidth computation to the theory of oracle machines. In particular, we consider halting and totality oracles, which belong to the most frequently investigated oracle machines in the theory of computation.

Deep neural networks have seen tremendous success over the last years. Since the training is performed on digital hardware, in this paper, we analyze what actually can be computed on current hardware platforms modeled as Turing machines, which would lead to inherent restrictions of deep learning. For this, we focus on the class of inverse problems, which, in particular, encompasses any task to reconstruct data from measurements. We prove that finite-dimensional inverse problems are not Banach-Mazur computable for small relaxation parameters. Even more, our results introduce a lower bound on the accuracy that can be obtained algorithmically.

The capacity of a channel can usually be characterized as a maximization of certain entropic quantities. From a practical point of view it is of primary interest to not only compute the capacity value, but also to find the corresponding optimizer, i.e., the capacity-achieving input distribution. This paper addresses the general question of whether or not it is possible to find algorithms that can compute the optimal input distribution depending on the channel. For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers and therewith fully specifies which tasks are algorithmically feasible in principle. It is shown for discrete memoryless channels that it is impossible to algorithmically compute the capacity-achieving input distribution, where the channel is given as an input to the algorithm (or Turing machine). Finally, it is further shown that it is even impossible to algorithmically approximate these input distributions.

Over the past decades, the problem of communication over finite-state Markov channels (FSMCs) has been investigated in many works and the capacity of FSMCs has been studied in closed form under the assumption of the availability of partial/complete channel state information at the sender and/or the receiver. In our work, we focus on infinite-state Markov channels by investigating the problem of message transmission over time-varying single-user multiple-input multiple-output (MIMO) Gauss-Markov Rayleigh fading channels, as an example of MIMO ergodic Rayleigh fading channels, with average power constraint and with complete channel state information available at the receiver side (CSIR). We prove a single-letter formula for the channel capacity and in particular the formula pointed out by Telatar for the channel capacity of MIMO ergodic Rayleigh fading channels for the case when the Gaussian noise is uncorrelated across antennas.

Secure communication in a potentially hostile environment is becoming more and more critical. TheArbitrarilyVaryingWiretapChannel (AVWC) provides information-theoretical bounds on how much information can be exchanged even in the presence of an active attacker. If the active attacker has non-causal side information, situations in which a legitimate communication system has been hacked can be modeled. We investigate the AVWC with non-causal side information at the jammer for the case that there exists a best channel to the eavesdropper. Non-causal side information means that the transmitted codeword is known to an active adversary before it is transmitted. By considering the maximum error criterion, we also allow messages to be known at the jammer before the corresponding codeword is transmitted. A single-letter formula for theCommonRandomness (CR)-assisted secrecy capacity is derived. Additionally, we provide a formula for the CR-assisted secrecy capacity for the cases where the channel to the eavesdropper is strongly degraded, strongly noisier, or strongly less capable with respect to the main channel. Furthermore, we compare our results to the CR-assisted secrecy capacity for the cases of maximum error criterion but without non-causal side information at the jammer (blind adversary), maximum error criterion with non-causal side information of the messages at the jammer (semi-blind adversary), and the case of average error criterion without non-causal side information at the jammer (blind adversary).

Entanglement resources can increase transmission rates substantially. Unfortunately, entanglement is a fragile resource that is quickly degraded by decoherence effects. In order to generate entanglement for optical communication, the transmitter and the receiver first prepare entangled spin-photon pairs locally, and then the photon at the transmitter is sent to the receiver through an optical fiber or free space. Without feedback, the transmitter does not know whether the entangled photon has reached the receiver. The present work introduces a new model of unreliable entanglement assistance, whereby the communication system operates whether entanglement assistance is present or not. While the sender is ignorant, the receiver knows whether the entanglement generation was successful. In the case of a failure, the receiver decodes less information. In this manner, the effective transmission rate is adapted according to the assistance status. Regularized formulas are derived for the classical and quantum capacity regions with unreliable entanglement assistance, characterizing the tradeoff between the unassisted rate and the excess rate that can be obtained from entanglement assistance. It is further established that time division between entanglement-assisted and unassisted coding strategies is optimal for the noiseless qubit channel, but can be strictly suboptimal for a noisy channel.

We analyze deterministic message identification via channels with non-discrete additive white noise and with a noiseless feedback link under both average power and peak power constraints. The identification task is part of Post Shannon Theory. The consideration of communication systems beyond Shannon’s approach is useful in order to increase the efficiency of information transmission for certain applications. We propose a coding scheme that first generates infinite common randomness between the sender and the receiver. If the channel has a positive message transmission feedback capacity, for given error thresholds and sufficiently large blocklength this common randomness is then used to construct arbitrarily large deterministic identification codes. In particular, the deterministic identification feedback capacity is infinite regardless of the scaling (exponential, doubly exponential, etc.) chosen for the capacity definition. Clearly, if randomized encoding is allowed in addition to the use of feedback, these results continue to hold.

This paper assesses the impact on the performance that information-theoretic physical layer security (IT-PLS) introduces when integrated into a 5G New Radio (NR) system. For this, we implement a wiretap code for IT-PLS based on a modular coding scheme that uses a universal-hash function in its security layer. The main advantage of this approach lies in its flexible integration into the lower layers of the 5G NR protocol stack without affecting the communication's reliability. Specifically, we use IT-PLS to secure the transmission of downlink control information by integrating an extra pre-coding security layer as part of the physical downlink control channel (PDCCH) procedures, thus not requiring any change of the 3GPP 38 series standard. We conduct experiments using a real-time open-source 5G NR standalone implementation and use software-defined radios for over-the-air transmissions in a controlled laboratory environment. The overhead added by IT-PLS is determined in terms of the latency introduced into the system, which is measured at the physical layer for an end-to-end (E2E) connection between the gNB and the user equipment.

We consider a decision problem associated to the task of estimating the state of a dynamic plant remotely via a noisy communication channel: given the characteristics of some unstable linear time-invariant (LTI) plant and some discrete memoryless channel (DMC), does there exist an encoder/decoder pair that allows for the remote tracking of the plant’s state with bounded error? Questions of this kind are becoming increasingly important in communication technologies, since future communication networks are expected to incorporate distributed control and decision-making. Analytically, this problem has been shown to involve the zero-error capacity of the DMC. Starting from this result, we approach the problem from the view of theoretical computer science, with an explicit treatment of the underlying machine Model. In particular, we prove that for every pair of a finite channel input alphabet and a finite channel output alphabet, there exists a Blum-Shub-Smale (BSS) algorithm that computes the zero-error capacity in dependence of the channel matrix. Based on this, we devise a BSS algorithm that solves the above decision problem given the plant’s and DMC’s characteristics. BSS machines are a promising candidate for a universal model of real number processing hardware, comparable to the Turing machine in the digital domain. Recently, we observe an increased interest in research and development towards real number and/or analog computing hardware, usually referred to by the term "neuromorphic computing".

Trustworthiness verification and integrity testing have been identified as key challenges for the sixth generation (6G) of mobile networks and its variety of envisioned features. In this paper, these issues are addressed from a fundamental, algorithmic point of view. For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers. It is shown that, in general, trustworthiness and integrity cannot be verified by Turing machines and therewith by today’s digital computers. In addition, the trustworthiness problem is further shown to be non-Banach-Mazur computable which is the weakest form of computability. Neuromorphic computing has an enormous potential to overcome the limitations of today’s digital hardware and, accordingly, it is interesting to study the issues of trustworthiness verification and integrity testing also for such powerful computing models. In particular, as considerable progress in the hardware design for neuromorphic computing has been achieved.

We experimentally verify the information-theoretic security of a seeded modular code for the AWGN wiretap channel consisting of a security layer, an error-correction layer and a modulation layer. The security layer is given by a universal family of hash functions. In the error-correction layer and the modulation layer we use polar codes and QAM, respectively. The eavesdropper uses the maximum likelihood (ML) test as an attack strategy. We analyze the security in different communication scenarios using simulations. We show that for small blocklengths the advantage (security measure) at the eavesdropper in the corresponding scenario can be close to 0 for suitable code parameters. Additional insights gathered from the simulation results include the impact of code parameters and seed choice on security.

We study semantic security for classical-quantum channels. Our security functions are functional forms of mosaics of combinatorial designs. We extend methods in [25] from classical channels to classical-quantum channels to demonstrate that mosaics of designs ensure semantic security for classical-quantum channels, and are also capacity achieving coding schemes. An advantage of these modular wiretap codes is that we provide explicit code constructions that can be implemented in practice for every channel, given an arbitrary public code.

The channel reliability function is an important tool that characterizes the reliable transmission of messages over communication channels. For many channels, only upper and lower bounds of the function are known. We analyze the computability of the reliability function and its related functions. We show that the reliability function is not a Turing computable performance function. The same also applies to the functions of the sphere packing bound and the expurgation bound. Furthermore, we show that the R∞function is not Banach Mazur computable and additive.

The bandwidth of a signal is an important physical property that is of relevance in many signal processing applications. In this paper we study questions related to the computability of the bandwidth of bandlimited signals. To this end we employ the concept of Turing computability, which exactly describes what is theoretically feasible and can be computed on a digital machine. Recently, it has been shown that there exist bandlimited signals, the actual bandwidth of which cannot be algorithmically determined, i.e., computed on a digital machine. In this work, we consider the most general class of bandlimited signals and analyze whether it is at least possible to compute nontrivial upper or lower bounds for the actual bandwidth of its members. We show that this is not possible in general.

The capacity of a channel can usually be characterized as a maximization of certain entropic quantities. From a practical point of view it is of crucial interest to not only compute the capacity value, but also to find the corresponding optimizer, i.e., the capacity-achieving input distribution. This paper addresses the general question of whether or not it is possible to find algorithms that can compute the optimal input distribution depending on the channel. For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers and therewith fully specifies which tasks are algorithmically feasible in principle. It is shown that it is impossible to algorithmically compute the capacity-achieving input distribution, where the channel is given as an input to the algorithm or Turing machine. Finally, it is further shown that it is also impossible to algorithmically approximate these input distributions.

We investigate the problem of message transmission over time-varying single-user multiple-input multiple-output (MIMO) Rayleigh fading channels with average power constraint and with complete channel state information available at the receiver side (CSIR). To describe the channel variations over the time, we consider a first-order Gauss-Markov model. We completely solve the problem by giving a single-letter characterization of the channel capacity in closed form and by providing a rigorous proof of it.

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.

We study the problem of common randomness (CR) generation in the basic two-party communication setting in which the sender and the receiver aim to agree on a common random variable with high probability by observing independent and identically distributed (i.i.d.) samples of correlated Gaussian sources and while communicating as little as possible over a noisy memoryless channel. We completely solve the problem by giving a single-letter characterization of the CR capacity for the proposed model and by providing rigorous proof of it We prove that the CR capacity is infinite when the Gaussian sources are perfectly correlated.

Communication over a quantum multiple-access channel (MAC) with cribbing encoders is considered, whereby Transmitter 2 performs a measurement on a system that is entangled with Transmitter 1. Based on the no-cloning theorem, perfect cribbing is impossible. This leads to the introduction of a MAC model with noisy cribbing. In the causal and non-causal cribbing scenarios, Transmitter 2 performs the measurement before the input of Transmitter 1 is sent through the channel. Hence, Transmitter 2’s cribbing may inflict a "state collapse" for Transmitter 1. Achievable regions are derived for each setting. Furthermore, a regularized capacity characterization is established for robust cribbing, i.e. when the cribbing system contains all the information of the channel input, and a partial decode-forward region for non-robust cribbing. For the classical-quantum (c-q) MAC with cribbing encoders, the capacity region is determined with perfect cribbing of the classical input, and a cutset region is derived for noisy cribbing.

Entanglement resources can increase transmission rates substantially. Unfortunately, entanglement is a fragile resource that is quickly degraded by decoherence effects. The present work introduces a new model of unreliable entanglement assistance, whereby the communication system operates whether entanglement assistance is present or not. While the sender is ignorant, the receiver knows whether the entanglement generation was successful. In the case of a failure, the receiver decodes less information. In this manner, the effective transmission rate is adapted according to the assistance status. Regularized formulas are derived for the classical and quantum capacity regions with unreliable entanglement assistance, characterizing the tradeoff between the unassisted rate and the excess rate that can be obtained from entanglement assistance.

We generalize the uniform common randomness capacity formula, initially established by Ahslwede and Csiszár for a two-source model for common randomness generation from independent and identically distributed (i.i.d.) discrete sources with unidirectional communication over rate-limited discrete noiseless channels to the case when the one-way communication is over arbitrary single-user channels. In our proof, we will make use of the transmission capacity formula established by Verdú and Han for arbitrary point-to-point channels.

The problem of secure source coding with multiple terminals is extended by considering a remote source whose noisy measurements are the correlated random variables used for secure source reconstruction. The main additions to the problem include 1) all terminals noncausally observe a noisy measurement of the remote source; 2) a private key is available to all legitimate terminals; 3) the public communication link between the encoder and decoder is rate-limited; and 4) the secrecy leakage to the eavesdropper is measured with respect to the encoder input, whereas the privacy leakage is measured with respect to the remote source. Exact rate regions are characterized for a lossy source coding problem with a private key, remote source, and decoder side information under security, privacy, communication, and distortion constraints. By replacing the distortion constraint with a reliability constraint, we obtain the exact rate region also for the lossless case. Furthermore, the lossy rate region for scalar discrete-time Gaussian sources and measurement channels is established.

Abstract We study security functions which can serve to establish semantic security for the two central problems of information-theoretic security: the wiretap channel, and privacy amplification for secret key generation. The security functions are functional forms of mosaics of combinatorial designs, more precisely, of group divisible designs and balanced incomplete block designs. Every member of a mosaic is associated with a unique color, and each color corresponds to a unique message or key value. Every block index of the mosaic corresponds to a public seed shared between the two trusted communicating parties. The seed set should be as small as possible. We give explicit examples which have an optimal or nearly optimal trade-off of seed length versus color (i.e., message or key) rate. We also derive bounds for the security performance of security functions given by functional forms of mosaics of designs.

A capacity result involves two parts: achievability and converse. The achievability proof is usually non-constructive and only the existence of capacity-achieving codes is shown invoking probabilistic techniques. Recently, capacity-achieving codes have been found for several channels demonstrating that such codes can actually be constructed algorithmically. To this end, each construction is designed for a pre-specified channel so that the corresponding algorithm is specifically tailored to it. This paper addresses the general question of whether or not it is possible to find algorithms that can construct capacity-achieving codes for a whole class of channels. To do so, the concept of Turing machines is used which provides the fundamental performance limits of digital computers and therewith fully specifies which tasks are algorithmically feasible in principle. It is shown that there exists no Turing machine that is able to construct capacity-achieving codes for a whole class of channels, where the channel realization from this class is given as an input to the Turing machine. It is further shown that such an algorithmic construction remains impossible when the optimality condition is dropped and codes only need to achieve a fraction of the capacity. Finally, implications on channel-aware transmission, link adaptation, and cross-layer optimization are discussed.

It is known that there exist mathematical problems of practical relevance which cannot be computed on a Turing machine. An important example is the calculation of the first derivative of continuously differentiable functions. This paper precisely classifies the non-computability of the first derivative, and of the maximum-norm of the first derivative in the Zheng-Weihrauch hierarchy. Based on this classification, the paper investigates whether it is possible that a Turing machine detects this non-computability of the first derivative by observing the data of the problem, and whether it is possible to detect upper bounds for the peak value of the first derivative of continuously differentiable functions. So from a practical point of view, the question is whether it is possible to implement an exit-flag functionality for observing non-computability of the first derivative. This paper even studies two different types of exit-flag functionality. A strong one, where the Turing machine always has to stop, and a weak one, where the Turing machine stops if and only if the input lies within the corresponding set of interest. It will be shown that non-computability of the first derivative is not detectable by a Turing machine for two concrete examples, namely for the problem of computing the input–output behavior of simple analog circuits and for solutions of the three-dimensional wave equation. In addition, it is shown that it is even impossible to detect an upper bound for the maximum norm of the first derivative. In particular, it is shown that all three problems are not even semidecidable. Finally, we briefly discuss implications of these results for analog and quantum computing.

Communication over a quantum multiple-access channel (MAC) with cribbing encoders is considered, whereby Transmitter 2 performs a measurement on a system that is entangled with Transmitter 1. Based on the no-cloning theorem, perfect cribbing is impossible. This leads to the introduction of a MAC model with noisy cribbing. In the causal and non-causal cribbing scenarios, Transmitter 2 performs the measurement before the input of Transmitter 1 is sent through the channel. Hence, Transmitter 2's cribbing may inflict a "state collapse" for Transmitter 1. Achievable regions are derived for each setting. Furthermore, a regularized capacity characterization is established for robust cribbing, i.e. when the cribbing system contains all the information of the channel input. Building on the analogy between the noisy cribbing model and the relay channel, a partial decode-forward region is derived for a quantum MAC with non-robust cribbing. For the classical-quantum MAC with cribbing encoders, the capacity region is determined with perfect cribbing of the classical input, and a cutset region is derived for noisy cribbing. In the special case of a classical-quantum MAC with a deterministic cribbing channel, the inner and outer bounds coincide.

The deterministic identification (DI) capacity is developed in multiple settings of channels with power constraints. A full characterization is established for the DI capacity of the discrete memoryless channel (DMC) with and without input constraints. Originally, Ahlswede and Dueck established the identification capacity with local randomness at the encoder, resulting in a double exponential number of messages in the block length $n$ . In the deterministic setup, the number of messages scales exponentially, as in Shannon's transmission paradigm, but the achievable identification rates are higher. An explicit proof was not provided for the deterministic setting. In this paper, a detailed proof is presented for the DMC. Furthermore, Gaussian channels with fast and slow fading are considered, when channel side information is available at the decoder. A new phenomenon is observed as we establish that the number of messages scales as $2^{n\log (n)R}$ by deriving lower and upper bounds on the DI capacity on this scale. Consequently, the DI capacity of the Gaussian channel is infinite in the exponential scale and zero in the double exponential scale, regardless of the channel noise.

In this paper we use a seeded modular coding scheme for implementing physical layer security in a wiretap scenario. This modular scheme consists of a traditional coding layer and a security layer. For the traditional coding layer, we use a polar code. We evaluate the performance of the seeded modular coding scheme in an experimental setup with software defined radios and compare these results to simulation results. In order to assess the secrecy level of the scheme, we employ the distinguishing security metric. In our experiments, we compare the distinguishing error rate for different seeds and block lengths.

Wireless channels are considered that change over time but remain constant for a certain (coherence) period. This behavior is perfectly captured by block fading channels and affects the performance of the corresponding wireless communication systems. Desired closed-form characterizations of optimal transmission schemes remain unknown in many cases. This paper approaches this issue from a fundamental, algorithmic point of view by studying whether or not it is in principle possible to construct or find such optimal transmission schemes algorithmically (without putting any constraints on the computational complexity of such algorithms). To this end, the concept of averaged channels is considered as a model for block fading and it is shown that, although the averaged channel itself is computable, the corresponding capacity need not be computable, i.e., there exists no (universal) algorithm that takes the channel as an input and computes the corresponding capacity expression. Subsequently, examples of block fading channels are presented for which it is even impossible to find an algorithm that computes for every blocklength the corresponding optimal transmission scheme.

Wireless communication systems are inherently vulnerable to adversarial attacks since malevolent jammers might jam and disrupt the legitimate transmission intentionally. Of particular interest are so- called denial-of-service (DoS) attacks in which the jammer is able to completely disrupt the communication. Accordingly, it is of crucial interest for the legitimate users to detect such DoS attacks. Turing machines provide the fundamental limits of today’s digital computers and therewith of the traditional signal processing. It has been shown that these are incapable of detecting DoS attacks. This stimulates the question of how powerful the signal processing must be to enable the detection of DoS attacks. This paper investigates the general computation framework of Blum-Shub-Smale machines which allows the processing and storage of arbitrary reals. It is shown that such real number signal processing then enables the detection of DoS attacks.

In this work, we study the system of two interacting non-cooperative Q-learning agents, where one agent has the privilege of observing the other's actions. We show that this information asymmetry can lead to a stable outcome of population learning, which does not occur in an environment of general independent learners. Furthermore, we discuss the resulted post-learning policies, show that they are almost optimal in the underlying game sense, and provide numerical hints of almost welfare-optimal of the resulted policies.

For communication systems there is a recent trend towards shifting functionalities from the physical layer to higher layers by enabling software-focused solutions. Having obtained a (physical layer-based) description of the communication channel, such approaches exploit this knowledge to enable various services by subsequently processing it on higher layers. For this it is a crucial task to first find out in which state the underlying communication channel is. This paper develops a framework based on Turing machines and studies whether or not it is in principle possible to algorithmically decide in which state the communication system is. It is shown that there exists no Turing machine that takes the physical description of the communication channel as an input and solves a non-trivial classification task. Subsequently, this general result is used to study communication under adversarial attacks and it is shown that it is impossible to algorithmically detect denial-of-service (DoS) attacks on the transmission. Jamming attacks on ACK/NACK feedback cannot be detected as well and, in addition, ACK/NACK feedback is shown to be useless for the detection of DoS attacks on the actual message transmission.

Proving a capacity result usually involves two parts: achievability and converse which establish matching lower and upper bounds on the capacity. For achievability, only the existence of good (capacity-achieving) codes is usually shown. Although the existence of such optimal codes is known, constructing such capacity-achieving codes has been open for a long time. Recently, significant progress has been made and optimal code constructions have been found including for example polar codes. A crucial observation is that all these constructions are done for a fixed and given channel and this paper addresses the question whether or not it is possible to find universal algorithms that can construct optimal codes for a whole class of channels. For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers. It is shown that there exists no universal Turing machine that takes the channel from the class of interest as an input and outputs optimal codes. Finally, implications on channel-aware transmission schemes are discussed.

Identification capacity is developed without randomization at neither the encoder nor the decoder. In particular, full characterization is established for the deterministic identification (DI) capacity for the Gaussian channel and for the general discrete memoryless channel (DMC) with and without constraints. Originally, Ahlswede and Dueck established the identification capacity with local randomness given at the encoder, resulting in a double exponential number of messages. In the deterministic setup, the number of messages scales exponentially, as in Shannon’s transmission paradigm, but the achievable identification rates can be significantly higher than those of transmission. Ahlswede and Dueck further stated a capacity result for the deterministic setting of a DMC, but did not provide an explicit proof. In this paper, a detailed proof is given for both the Gaussian channel and the general DMC. The DI capacity of a Gaussian channel is infinite regardless of the noise.

Communication systems are subject to adversarial attacks since malevolent adversaries might harm and disrupt legitimate transmissions intentionally. Of particular interest in this paper are so-called denial-of-service (DoS) attacks in which the jammer completely prevents any transmission. Arbitrarily varying classical-quantum channels, providing a suitable model to capture the jamming attacks of interest, are studied. Algorithmic detection frameworks are developed based on Turing machines and also Blum-Shub-Smale (BSS) machines, where the latter can process and store arbitrary real numbers. It is shown that Turing machines are not capable of detecting DoS attacks. However, BSS machines are capable thereof implying that real number signal processing enables the algorithmic detection of DoS attacks.

This paper analyzes the problem of common randomness (CR) generation from correlated discrete sources aided by unidirectional communication over Single-Input Single-Output (SISO) slow fading channels with additive white Gaussian noise (AWGN) and arbitrary state distribution. Slow fading channels are practically relevant in many situations in wireless communications. We completely solve the SISO slow fading case by establishing its corresponding outage CR capacity using our characterization of its channel outage capacity. The generated CR could be exploited to improve the performance gain in the identification scheme. The latter is known to be more efficient than the classical transmission scheme in many new applications, which demand ultra-reliable low latency communication.

We analyze message identification via Gaussian channels with noiseless feedback, which is part of the Post Shannon theory. The consideration of communication systems beyond Shannon's approach is useful in order to increase the efficiency of information transmission for certain applications. If the noise variance is positive, we propose a coding scheme that generates infinite common randomness between the sender and the receiver. We show that any identification rate via the Gaussian channel with noiseless feedback can be achieved. The remarkable result is that this applies to both rate definitions $\frac{1}{n}\log M$ (as defined by Shannon for transmission) and $\frac{1}{n}\ \log \log\ M$ — (as defined by Ahlswede and Dueck for identification). We can even show that our result holds regardless of the selected scaling for the rate. A detailed version with all proofs, explanations and more discussions can be found in [1].

Communication over a quantum broadcast channel with cooperation between the receivers is considered. The first form of cooperation addressed is classical conferencing. Another cooperation setting involves quantum conferencing, where Receiver 1 can teleport a quantum state to Receiver 2. The conferencing setting is intimately related to quantum repeaters, as the sender, Receiver 1, and Receiver 2 can be viewed as the transmitter, the repeater, and the destination receiver, respectively. We develop lower and upper bounds on the capacity region in each setting. At last, we show that as opposed to the MAC with entangled encoders, entanglement between decoders does not increase the classical communication rates for the broadcast dual.

We study security functions which can serve to establish semantic security for privacy amplification in secret key generation. The security functions are functional forms of mosaics of combinatorial designs, more precisely, of group divisible designs and balanced incomplete block designs. Every member of a mosaic corresponds to a unique key value. We give explicit examples which have an optimal or nearly optimal tradeoff of seed size, given by the size of the block index set of the mosaics, versus key rate. We also derive bounds for the security performance in privacy amplification of security functions given by functional forms of mosaics of designs.

Zero-error capacity plays an important role in a whole range of operational tasks, in addition to the fact that it is necessary for practical applications. Due to the importance of zero-error capacity, it is necessary to investigate its algorithmic computability, as there has been no known closed formula for the zero-error capacity until now. We show that the zero-error capacity of noisy channels is not Banach-Mazur computable and therefore not Borel-Turing computable. This result also implies the uncomputability of the zero-error capacity for real-valued channel matrices characterized by means of an oracle machine. We also investigate the relationship between the zero-error capacity of discrete memoryless channels, the Shannon capacity of graphs, and Ahlswede’s characterization of the zero-errorcapacity of noisy channels with respect to the maximum error capacity of 0-1-arbitrarily varying channels. We will show that important questions regarding semi-decidability are equivalent for all three capacities. So far, the Borel-Turing computability of the Shannon capacity of graphs is completely open. This is why the coupling with semi-decidability is interesting. The authors conjecture that the zero-error capacity of a noisy channel may be computable with respect to some computation models other than the Turing machine, like neuromorphic-computers and specific types of quantum computers.

We investigate the problem of common randomness (CR) generation from discrete correlated sources aided by one-way communication over single-user multiple-input multiple-output (MIMO) slow fading channels with additive white Gaussian noise (AWGN), arbitrary state distribution and with channel state information available at the receiver side (CSIR). We completely solve the problem by first characterizing the channel outage capacity of MIMO slow fading channels for arbitrary state distribution. For this purpose, we also provide an achievable rate for a specific compound MIMO Gaussian channel. Second, we define the outage CR capacity of the MIMO slow fading channel and establish a single-letter characterization of it using our result on its outage transmission capacity.

The bandwidth of a bandlimited signal is an important number that is relevant in many applications and concepts. For example, according to the Shannon sampling theorem, the bandwidth determines the minimum sampling rate that is required for a perfect reconstruction. In this paper we consider bandlimited signals with finite energy and bandlimited signals that are absolutely integrable and analyze whether the bandwidth of these signals can be determined algorithmically. We employ the concept of Turing computability, a theoretical model that describes the fundamental limits of what can be solved algorithmically on a digital hardware, and ask if, for a given computable bandlimited signal, it is possible to compute its bandwidth on a Turing machine. We show that this is not possible in general, because there exist computable bandlimited signals for which the bandwidth is a non-computable real number. Even the weaker question if the bandwidth of a given signal is smaller than a predefined value cannot be always answered algorithmically. Further, we prove that in the case where the bandwidth in not computable, it is even impossible to algorithmically determine a sequence of upper bounds that converges to the actual bandwidth of the signal. As a positive result, we show that the set of signals whose bandwidth is larger than some given value is semi-decidable.

Communication over a quantum channel that depends on a quantum state is considered when the encoder has channel side information (CSI) and is required to mask information on the quantum channel state from the decoder. A full characterization is established for the entanglement-assisted masking equivocation region with a maximally correlated channel state, and a regularized formula is given for the quantum capacity-leakage function without assistance. For Hadamard channels without assistance, we derive single-letter inner and outer bounds, which coincide in the standard case of a channel that does not depend on a state.

High-dimensional identification systems consisting of two groups of users in the presence of statistical uncertainties are considered in this work. The task is to design enrollment mappings to compress users' information and an identification mapping that combines the stored information in the database and an observation to estimate the underlying user index. The compression-identification trade-off regions are established for the compound, extended compound, general and mixture settings. It is shown that several settings admit the same compression-identification trade-offs. We then study a connection between the Wyner-Ahlswede-Körner network and the identification setting. It indicates that a strong converse for the WAK network is equivalent to a strong converse for the identification setting. Finally, we present strong converse arguments for the discrete identification setting that are extensible to the Gaussian scenario.

A novel type of functions called biregular irreducible functions is introduced and applied as security components (instead of, e.g., universal hash functions) in seeded modular wiretap coding schemes, whose second component is an error-correcting code. These schemes are called modular BRI schemes. An upper bound on the semantic security information leakage of modular BRI schemes in a one-shot setting is derived which separates the effects of the biregular irreducible function on the one hand and the error-correcting code plus the channel on the other hand. The effect of the biregular irreducible function is described by the second-largest eigenvalue of an associated stochastic matrix. A characterization of biregular irreducible functions is given in terms of connected edge-disjoint biregular graphs. It allows for the construction of new biregular irreducible functions from families of edge-disjoint Ramanujan graphs, which are shown to exist. A concrete and frequently used arithmetic universal hash function can be converted into a biregular irreducible function for certain parameters. Sequences of Ramanujan biregular irreducible functions are constructed which exhibit an optimal trade-off between the size of the regularity set and the rate of decrease of the associated second-largest eigenvalue. Together with the one-shot bound on the information leakage, the existence of these sequences implies an asymptotic coding result for modular BRI schemes applied to discrete and Gaussian wiretap channels. It shows that the separation of error correction and security as done in a modular BRI scheme is secrecy capacity-achieving for every discrete and Gaussian wiretap channel. The same holds for a derived construction where the seed is generated locally by the sender and reused several times. It is shown that the optimal sequences of biregular irreducible functions used in the above constructions must be nearly Ramanujan.

For communication systems there is a recent trend towards shifting functionalities from the physical layer to higher layers by enabling software-focused solutions. Having obtained a (physical layer-based) description of the communication channel, such approaches exploit this knowledge to enable various services by subsequently processing it on higher layers. For this it is a crucial task to first find out in which state the underlying communication channel is. This paper develops a framework based on Turing machines and studies whether or not it is in principle possible to algorithmically solve such classification tasks, i.e., to decide in which state the communication system is. Turing machines have no limitations on computational complexity, computing capacity and storage, and can simulate any given algorithm and therewith are a simple but very powerful model of computation. They characterize the fundamental performance limits for today's digital computers. It is shown that there exists no Turing machine that takes the physical description of the communication channel as an input and solves a non-trivial classification task. Subsequently, this general result is used to study communication under adversarial attacks and it is shown that it is impossible to algorithmically detect denial-of-service (DoS) attacks on the transmission. Jamming attacks on ACK/NACK feedback cannot be detected as well and, in addition, ACK/NACK feedback is shown to be useless for the detection of DoS on the actual message transmission. Further applications are discussed including DoS attacks on the Post Shannon task of identification, and on physical layer security and resilience by design.

Common randomness (CR), as a resource, is not commonly used in existing practical communication systems. In the common randomness framework, both sender and receiver, often described as terminals, aim to generate a common random variable observable to both, perhaps with low error probability. The knowledge of this CR allows to implement correlated random protocols that could lead to faster and more efficient algorithms. We characterize CR over Gaussian channels for their practical relevance in many communication situations by deriving the CR capacity for both Gaussian Single-Input Single-Output (SISO) and Multiple-Input Multiple-Output (MIMO) cases. Furthermore, CR plays a key role in the identification scheme. In many new applications such as several machine-to-machine and human-to-machine systems and the tactile internet, which demand ultra-reliable low latency, the identification or also called post-Shannon scheme is proved to be more efficient than the classical transmission. It has been proved that through CR generation, the post-Shannon communication task allows to achieve an enormous performance gain. We consider a correlation-assisted secure identification scheme over Gaussian wiretap channels (GWC) and develop a lower bound on the corresponding secure identification capacity.

In this paper we study the peak value problem, i.e., the task of computing the peak value of a bandlimited signal from its samples. The peak value problem is important, for example, in communications, where the peak value of the transmit signal has to be controlled in order that the amplifier is not overloaded, which would generate out-of-band radiation. We prove that the peak value of a computable bandlimited signal is computable on digital hardware if oversampling is used. The computability ensures that the approximation error can be effectively controlled. Further, we provide an algorithm that can be used to perform this computation and prove that oversampling is indeed necessary, because there exist signals for which the peak value problem cannot be algorithmically solved without oversampling. Hence, without oversampling the peak value of such signals cannot be computed on any digital hardware, including DSPs, FPGAs, and CPUs.

Shannon's sampling theorem is of high importance in signal processing, because it links the continuous-time and discrete-time worlds. For bandlimited signals we can switch from one domain into the other without loosing information. In this paper we analyze if and how this transition affects the computability of the signal. Computability is important in order that the approximation error can be controlled. We show that the computability of the signal is not always preserved. Further, we provide a simple necessary and sufficient condition for the computability of the continuous-time signal, and a simple canonical algorithm that can be used for the computation.

The bandwidth of a bandlimited signal is a key quantity that is relevant in numerous applications. For example, it determines the minimum sampling rate that is necessary to reconstruct a bandlimited signal from its samples. In this paper we study if it is possible to algorithmically determine the actual bandwidth of a bandlimited signal. We prove that this is not possible in general, because there exist bandlimited computable signals, which have a bandwidth that is not computable. To this end we employ the concept of Turing computability, which provides a theoretical model that describes the fundamental limits of any practically realizable digital hardware, such as CPUs, DSPs, or FPGAs. Further, we answer the weaker question if it can be algorithmically answered whether the bandwidth of a given signal is larger than a predefined value.

A Turing machine is a model describing the fundamental limits of any realizable computer, digital signal processor (DSP), or field programmable gate array (FPGA). This paper shows that there exist very simple linear time-invariant (LTI) systems which can not be simulated on a Turing machine. In particular, this paper considers the linear system described by the voltage-current relation of an ideal capacitor. For this system, it is shown that there exist continuously differentiable and computable input signals such that the output signal is a continuous function which is not computable. Moreover, for this particular system, we present sharp results characterizing computable input signals which guarantee that the output signal is computable. Additionally, it is shown that the computability of the step response of an LTI system does not necessarily imply that the impulse response is computable.

Although the Hilbert transform and the spectral factorization are of central importance in signal processing, both operations can generally not be calculated in closed form. Therefore, algorithmic solutions are prevalent which provide an approximation of the true solution. Then it is important to effectively control the approximation error of these approximate solutions. This paper characterizes for both operations precisely those signal spaces of differentiable functions for which such an effective control of the approximation error is possible. In other words, the paper provides a precise characterization of signal spaces of smooth functions on which these two operations are computable on Turing machines.

The availability and quality of channel state information heavily influences the performance of wireless communication systems. For perfect channel knowledge, optimal signal processing and coding schemes are well studied and often closed-form solutions are known. On the other hand, the case of imperfect channel information is much less understood and closed-form solutions remain unknown in general. This paper approaches this question from a fundamental, algorithmic point of view to study whether or not such optimal schemes can be found algorithmically in principle (without putting any constraints on the computational complexity of such algorithms). To this end, the compound channel is considered as a model for channel uncertainty and it is shown that although the compound channel itself is a computable channel, the corresponding capacity is not computable in general, i.e., there exists no algorithm or Turing machine that takes the channel as an input and computes the corresponding capacity. As an implication of this, it is then shown that for such compound channels, there are no effectively constructible optimal signal processing and coding schemes that achieve the capacity. This is particularly noteworthy as such schemes must exist (since the capacity is known), but they cannot be effectively, i.e., algorithmically, constructed.

New applications in modern communications are demanding robust and ultra-reliable low latency information exchange such as machine-to-machine and human-to-machine communications. For many of these applications, the identification approach of Ahlswede and Dueck is much more efficient than the classical transmission scheme proposed by Shannon. Previous studies concentrate mainly on identification over discrete channels. We focus on Gaussian channels for their known practical relevance. We deal with secure identification over Gaussian channels. In particular, we provide a suitable coding scheme for the Gaussian wiretap channel (GWC) and determine the corresponding secure identification capacity.

Online-learning literature has focused on designing algorithms that ensure sub-linear growth of the cumulative long-term constraint violations. The drawback of this guarantee is that strictly feasible actions may cancel out constraint violations on other time slots. For this reason, we introduce a new performance measure, whose particular instance is the cumulative positive part of the constraint violations. We propose a class of non-causal algorithms for online-decision making, which guarantees, in slowly changing environments, sub-linear growth of this quantity despite noisy first-order feedback. Furthermore, we demonstrate by numerical experiments the performance gain of our method relative to state of the art.

We consider the problem of resource congestion control for competing online learning agents under privacy and security constraints. Based on the non-cooperative game as the model for agents' interaction and the noisy online mirror ascent as the model for the rationality of the agents, we propose a novel pricing mechanism that gives the agents incentives for sustainable use of the resources. An advantage of our method is that it is privacy-preserving in the sense that mainly the resource congestion serves as an orientation for our pricing mechanism, in place of the agents' preference and state. Moreover, our method is robust against adversary agents' feedback in the form of the noisy gradient. We present the following result of our theoretical investigation: In case that the feedback noise is persistent, and for several choices of the intrinsic parameter (the learning rate) of the agents and of the mechanism parameters (the learning rate of the price-setters, their progressivity, and the extrinsic price sensitivity of the agents), we show that the accumulative violation of the resource constraints of the resulted iterates is sub-linear w.r.t the time horizon. To support our theoretical findings, we provide some numerical simulations.

We determine the semantic security capacity for quantum wiretap channels. We extend methods for classical channels to quantum channels to demonstrate that a strongly secure code guarantees a semantically secure code with the same secrecy rate. Furthermore, we show how to transform a non-secure code into a semantically secure code by means of biregular irreducible functions (BRI functions). We analyze semantic security for classical-quantum channels and for quantum channels.

The zero-error capacity of a discrete classical channel was first defined by Shannon as the least upper bound of rates for which one transmits information with zero probability of error. The problem of finding the zero-error capacity C0, which assigns a capacity to each channel as a function, was reformulated in terms of graph theory as a function Θ, which assigns a value to each simple graph. This paper studies the computability of the zero-error capacity. For the computability, the concept of a Turing machine and a Kolmogorov oracle is used. It is unknown if the zero-error capacity is computable in general. We show that in general the zero-error capacity is semi-computable with the help of a Kolmogorov Oracle. Furthermore, we show that C0and Θ are computable functions if and only if there is a computable sequence of computable functions of upper bounds, i.e. the converse exist in the sense of information theory, which point-wise converges to C0or Θ. Finally, we examine Zuiddam's characterization of C0and Θ in terms of algorithmic computability.

We derive universal codes for transmission of broadcast and confidential messages over classical- quantum-quantum and fully quantum channels. These codes are robust to channel uncertainties considered in the compound model. To construct these codes we generalize random codes for transmission of public messages, to derive a universal superposition coding for the compound quantum broadcast channel. As an application, we give a multi-letter characterization of regions corresponding to capacity of the compound quantum broadcast channel for transmitting broadcast and confidential messages simultaneously. This is done for two types of broadcast messages, one called public and the other common.

A coding theorem consists of two parts: achievability and converse which establish lower and upper bounds on the capacity. This paper analyzes these bounds from a fundamental, algorithmic point of view by studying whether or not such bounds can be computed algorithmically in principle (without putting any constraints on the computational complexity of such algorithms). For this purpose, the concept of Turing machines is used which provides the fundamental performance limits of digital computers. To this end, computable continuous functions are studied and properties of computable sequences of such functions are identified. Subsequently, these findings are exemplarily applied to two different open problems. The first one is the ϵ-capacity of compound channels which is unknown to date. It is studied whether or not the ϵ-capacity can be algorithmically computed and it is shown that there is no computable characterization of the difference between computable upper and lower bounds possible. Thus, computable sharp lower and upper bounds on the ϵ-capacity of computable compound channels cannot exist. The crucial consequence is that the ϵ-capacity cannot be characterized by a finite-letter entropic expression. The second application involves asymptotic bounds for error-correcting codes which is a long-standing open problem in coding theory. Only lower and upper bounds are known which are not sharp. It is conjectured that the asymptotic bound is indeed a non-computable function which would then imply with the previous findings that it is impossible to find computable lower and upper bounds that are asymptotically tight.

We investigate the Arbitrarily Varying Wiretap Channel (AVWC) with non-causal side information at the jammer for the case that there exists a best channel to the eavesdropper and under the condition that strong degradedness holds. Non-causal side information means that codewords are known at an active adversary before they are transmitted. By considering the maximum error criterion, we allow also messages to be known at the jammer before the corresponding codeword is transmitted. A single letter formula for the common randomness secrecy capacity is derived.

Fekete's lemma is a well known assertion that states the existence of limit values of superadditive sequences. In information theory, superadditivity of rate functions occurs in a variety of channel models, making Fekete's lemma essential to the corresponding capacity problems. We analyze Fekete's lemma with respect to effective convergence and computability and show that Fekete's lemma exhibits no constructive derivation. In particular, we devise a superadditive, computable sequence of rational numbers so that the associated limit value in the sense of Fekete's lemma is not a computable number. We further characterize the requirements for effective convergence and investigate the speed of convergence, as proposed by Rudolf Ahlswede in his 2006 Shannon lecture.

Communication over a quantum channel that depends on a quantum state is considered, when the encoder has channel side information (CSI) and is required to mask information on the quantum channel state from the decoder. A full characterization is established for the entanglement-assisted masking equivocation region, and a regularized formula is given for the quantum capacity-leakage function without assistance. For Hadamard channels without assistance, we derive single-letter inner and outer bounds, which coincide in the standard case of a channel that does not depend on a state.

Deterministic identification (DI) is addressed for Gaussian channels with fast and slow fading, where channel side information is available at the decoder. In particular, it is established that the number of messages scales as 2nlog(n)R, where n is the block length and R is the coding rate. Lower and upper bounds on the DI capacity are developed in this scale for fast and slow fading. Consequently, the DI capacity is infinite in the exponential scale and zero in the double-exponential scale, regardless of the channel noise.

The source model for secret key generation with one way public communication refers to a setting in which a secret key should be agreed upon at two terminals. At both terminals correlated components of a common source are available. In addition, a message can be sent from one terminal to the other via a public channel. In this paper, a related scenario is considered where instead of secret key generation, the goal is to securely store data in a public database. The database allows for error-free storing of the data, but is constrained in its size which imposes a rate constraint on storing. The corresponding capacity for secure storage is known and it has been shown that the capacity-achieving strategy satisfies the strong secrecy criterion. Here, the case when the storage in the public database is subject to errors is considered and the corresponding capacity is characterized. In addition, the continuity properties of the two capacity functions are analyzed. These capacity functions are continuous as opposed to the discontinuous secret key capacity with rate constraint. It is shown that for secure storage the phenomenon of super activation can occur. Finally, it is discussed how the results in this paper differ from previous results on super activation.

Modern communication systems need to satisfy pre-specified requirements on spectral efficiency and security. Physical layer security is a concept that unifies both and connects them with entropic quantities. In this paper, a framework based on Turing machines is developed to address the question of deciding whether or not a communication system meets these requirements. It is known that the class of Turing solvable problems coincides with the class of algorithmically solvable problems so that this framework provides the theoretical basis for effective verification of such performance requirements. A key issue here is to decide whether or not the performance functions, i.e., capacities, of relevant communication scenarios, particularly those with secrecy requirements and active adversaries, are Turing computable. This is a necessary condition for the corresponding communication protocols to be effectively verifiable. Within this framework, it is then shown that for certain scenarios including the wiretap channel the corresponding capacities are Turing computable. Next, a general necessary condition on the performance function for Turing computability is established. With this, it is shown that for certain scenarios, including the wiretap channel with an active jammer, the performance functions are not computable when deterministic codes are used. As a consequence, such performance functions are also not computable on all other computer architectures such as the von Neumann-architecture or the register machines.

Spectral factorization is an operation which appears in many different engineering applications. This paper studies whether spectral factorization can be algorithmically computed on an abstract machine (a Turing machine). It is shown that there exist computable spectral densities with very good analytic properties (i.e. smooth with finite energy) such that the corresponding spectral factor cannot be determined on a Turing machine. Further, it will be proved that it is impossible to decide algorithmically whether or not a given computable density possesses a computable spectral factor. This negative result has consequences for applications of spectral factorization in computer-aided design, because there it is necessary that this problem be decidable. Conversely, this paper will show that if the logarithm of a computable spectral density belongs to certain Sobolev space of sufficiently smooth functions, then the spectral factor is always computable. As an application, the paper discusses the possibility of calculating the optimal causal Wiener filter on an abstract machine.

The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not, and the identification-feedback (IDF) capacity of channels with feedback is studied. The IDF capacity is shown to be discontinuous and super-additive for both deterministic and randomized encoding. For the deterministic IDF capacity the phenomenon of super-activation occurs, which is the strongest form of super-additivity. This is the first time that super-activation is observed for discrete memoryless channels. On the other hand, for the randomized IDF capacity, super-activation is not possible. Finally, the developed theory is studied from an algorithmic point of view by using the framework of Turing computability. The problem of computing the IDF capacity on a Turing machine is connected to problems in pure mathematics and it is shown that if the IDF capacity would be Turing computable, it would provide solutions to other problems in mathematics including Goldbach's conjecture and the Riemann Hypothesis. However, it is shown that the deterministic and randomized IDF capacities are not Banach-Mazur computable. This is the weakest form of computability implying that the IDF capacity is not computable even for universal Turing machines. On the other hand, the identification capacity without feedback is Turing computable revealing the impact of the feedback: It transforms the identification capacity from being computable to non-computable.

In this paper we study downsampling for bandlimited signals. Downsampling in the discrete-time domain corresponds to a removal of samples. For any downsampled signal that was created from a bandlimited signal with finite energy, we can always compute a bandlimited continuous-time signal such that the samples of this signal, taken at Nyquist rate, are equal to the downsampled discrete-time signal. However, as we show, this is no longer true for the space of bounded bandlimited signals that vanish at infinity. We explicitly construct a signal in this space, which after downsampling does not have a bounded bandlimited interpolation. This shows that downsampling in this signal space is an operation that can lead out of the set of discrete-time signals for which we have a one-to-one correspondence with continuous-time signals.

In this paper we study whether it is possible to decide algorithmically if the Fourier series of a continuous function converges uniformly. We show that this decision cannot be made algorithmically, because there exists no Turing machine that can decide for each and every continuous functions whether its Fourier series converges uniformly. Turing computability describes the theoretical feasible that can be implemented on a digital computer, hence the result shows that there exists no algorithm that can perform this decision.

This paper considers the problem of approximating continuous functions of finite Dirichlet energy from samples of these functions. It will be shown that there exists no sampling-based method which is able to approximate every function in this space from its samples. Specifically, we are going to show that for any sampling based approximation method, the energy of the approximation tends to infinity as the number of samples is increased for almost every continuous function of finite energy. As an application, we study the problem of solving the Dirichlet problem on a bounded region. It will be shown that if only samples of the boundary function can be processed then the energy of the solution can not be controlled for any function from a non-meager dense set.

Secret key generation refers to the problem of generating a common secret key without revealing any information about it to an eaves-dropper. All users observe correlated components of a common source and can further use a rate-limited public channel for discussion which is open to eavesdroppers. This paper studies the Turing computability of the secret key capacity with a single rate-limited public forward transmission. Turing computability provides fundamental performance limits for today’s digital computers. It is shown that the secret key capacity under rate constraints is not Turing computable, and consequently there is no algorithm that can simulate or compute the secret key capacity, even if there are no limitations on computational complexity and computing power. On the other hand, if there are no rate constraints on the forward transmission, the secret key capacity is Turing computable. This shows that restricting the communication rate over the public channel transforms a Turing computable problem into a non-computable problem. To the best of our knowledge, this is the first time that such a phenomenon has been observed.

Wireless communication systems are inherently vulnerable to adversarial attacks since malevolent jammers might jam and disrupt the legitimate transmission intentionally. Accordingly it is of crucial interest for the legitimate users to detect such adversarial attacks. This paper develops a detection framework based on Turing machines and studies the detectability of adversarial attacks. Of particular interest are so-called denial-of-service attacks in which the jammer is able to completely prevent any transmission. It is shown that there exists no Turing machine which can detect such an attack and consequently there is no algorithm that can decide whether or not such a denialof-service attack takes place, even if there are no limitations on computational complexity and computing capacity of the hardware.

We study reliable communication in uncoordinated vehicular communication from the perspective of Shannon theory. Our system model for the information transmission is that of an Arbitrarily Varying Channel (AVC): One sender-receiver pair wants to communicate reliably, no matter what the input of a second sender is. The second sender is assumed to be uncoordinated and interfering, but is supposed to follow the rational goal of transmitting information otherwise. We prove that repetition coding can increase the capacity of such a system by relating the notion of symmetrizability of an arbitrarily varying channel to invertibility of the corresponding channel matrix. Explicit upper bounds on the number of repetitions needed to prevent system breakdown through diversity are provided. Further we introduce the notion of block-restricted jamming and present a lower and an upper bound on the maximum error capacity of the corresponding restricted AVC.

In this paper we analyze the capacity of a special model for arbitrarily varying classical-quantum channels when the sender and the receiver use a weak resource. In this model a jammer has side information about the channel input. We determine the correlation assisted capacity. As an application, we determine the correlation assisted common randomness capacity with informed jammer. We also analyze these both capacities when only a small amount of correlation is available.

We derive universal codes for simultaneous transmission of classical messages and entanglement through quantum channels, possibly under attack of a malignant third party. These codes are robust to different kinds of channel uncertainty. We show these codes to be optimal by giving a multi-letter characterization of regions corresponding to capacity of compound quantum channels for simultaneously transmitting and generating entanglement with classical messages. Also, we give dichotomy statements in which we characterize the capacity of arbitrarily varying quantum channels for simultaneous transmission of classical messages and entanglement.

The Fourier transform is an essential operation in information sciences. However, it can rarely be calculated in closed form. Nowadays, digital computers are used to compute the Fourier transform. In this paper we study the computability of the Fourier transform. We construct an absolutely integrable bandlimited function that is computable as an element of L2, such that its Fourier transform is not Turing computable. This means the Fourier transform is not computable on a digital computer, because we have no way of effectively controlling the approximation error. This result has consequences for algorithms that use the Fourier transform of bandlimited function, e.g., the computation of the convolution via a multiplication in the Fourier domain.

The spectral factorization is an important operation in many different applications. This paper studies whether the spectral factor of a given computable spectral density can always be computed on an abstract machine (a Turing machine). It is shown that there are computable spectral densities with very comfortable analytic properties (smoothness and finite energy) such that the corresponding spectral factor can not be determined on a Turing machine. As an application, the paper discusses the possibility of calculating the optimal Wiener filter from computable spectral densities.

The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not. Identification via correlation-assisted discrete memoryless channels is studied, where the transmitter and the receiver further have access to correlated source observations. Analytical properties and representations of the corresponding identification capacity are studied. In this paper, it is shown that the identification capacity cannot be represented as a maximization of a single-letter (or multi-letter with fixed length) expression of entropic quantities. Further, it is shown that the identification capacity is not Banach-Mazur computable and therewith not Turing computable. Consequently, there is no algorithm that can simulate or compute the identification capacity, even if there are no limitations on computational complexity and computing power.

It is investigated how to achieve semantic security for the wiretap channel. A new type of functions called biregular irreducible (BRI) functions, similar to universal hash functions, is introduced. BRI functions provide a universal method of establishing secrecy. It is proved that the known secrecy rates of any discrete and Gaussian wiretap channel are achievable with semantic security by modular wiretap codes constructed from a BRI function and an error-correcting code. A characterization of BRI functions in terms of edge-disjoint biregular graphs on a common vertex set is derived. This is used to study examples of BRI functions and to construct new ones.

Finite state channels (FSCs) model discrete channels with memory where the channel output depends on the channel input and the actual channel state. The capacity of general FSCs has been established as the limit of a sequence of multi-letter expressions; a corresponding finite-letter characterization is not known to date. In this paper, it is shown that it is indeed not possible to find such a finite-letter entropic characterization for FSCs whose input, output, and state alphabets satisfy |X| ≥2, |Y| ≥2, and |S| ≥q2. Further, the algorithmic computability of the capacity of FSCs is studied. To account for this, the concept of a Turing machine is adopted as it provides fundamental performance limits for today's digital computers. It is shown that the capacity of a FSC is not Banach-Mazur computable and therewith not Turing computable for |X| ≥2, |Y| ≥2, |S| ≥2.

The theory of Verdú and Han provides a powerful framework to analyze and study general non-independent and identically distributed (non-i.i. d.) sources and channels. Already for simple non-i.i. d. sources and channels, this framework can result in complicated general capacity formulas. Ahlswede asked in his Shannon lecture if these general capacity formulas can be effectively, i.e., algorithmically, computed. In this paper, it is shown that there exist computable non-i.i. d. sources and channels, for which the capacity is a non-computable number. Even worse, it is shown that there are non-i.i. d. sources and channels for which the capacity is a computable number, i.e., the limit of the corresponding sequence of multi-letter capacity expressions is computable, but the convergence of this sequence is not effective. This answers Ahlswede's question in a strong form, since in this case, the multi-letter capacity expressions for these sources and channels cannot be used to approximate the optimal performance algorithmically.

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.

We consider transmissions of secure messages over a burst erasure wiretap channel under decoding delay constraint. For block codes we introduce and study delay optimal secure burst erasure correcting (DO-SBE) codes that provide perfect security and recover a burst of erasures of a limited length with minimum possible delay. Our explicit constructions of DO-SBE block codes achieve maximum secrecy rate. We also consider a model of a burst erasure wiretap channel for the streaming setup, where in any sliding window of a given size, in a stream of encoded source packets, the eavesdropper is able to observe packets in an interval of a given size. For that model we obtain an information theoretic upper bound on the secrecy rate for delay optimal streaming codes. We show that our block codes can be used for construction of delay optimal burst erasure correcting streaming codes which provide perfect security and meet the upper bound for a certain class of code parameters.

Ahlswede and Dueck introduced identification via channels as a new paradigm in information theory. They showed that the number of messages that can reliably be identified over a noisy channel grows doubly exponentially with the block length. In this paper, we also consider identification, but we assume that messages are stored on a database such that they can be identified. In addition, the legitimate users have access to the output of a source. This source allows us to store messages securely. It is also used to increase the number of messages that can be stored securely on the database and identified reliably. We define a protocol for secure storage for identification such that the number of stored messages that can be identified grows doubly exponentially with the number of symbols read from the source and the number of storage cells available, respectively. We also consider the privacy leakage of the protocols used for identification. So, it makes sense to consider two sources. We assume one source is public, whereas the other source is available only to the legitimate users. The public source is used to increase the number of messages that can be identified, while the second source is used to guarantee secrecy. Using the public source does not increase the privacy leakage. So, we can possibly achieve a higher number of messages that can be identified, while the privacy leakage does not increase using two sources. As a by-product, we also get new results on common randomness generation.

In next-generation connectivity systems, which rely on robust and low-latency information exchange, there exists communication tasks in which the Ahlswede/Dueck identification scheme is much more efficient than Shannon's transmission scheme. We concentrate on the arbitrarily varying wiretap channel (AVWC) that models jamming attacks. We provide a coding scheme for secure identification and determine the secrecy capacity of the AVWC. Furthermore, we analyze important properties of this capacity function, e.g., continuity and super-additivity. These properties are important for the design of robust secure communication design and for the optimization of the medium access control.

In this paper, a new model for arbitrarily varying classical-quantum channels is proposed. In this model, a jammer has side information. The communication scenario in which a jammer can select only classical inputs as a jamming sequence is considered in the first part of the paper. This situation corresponds to the standard model of arbitrarily varying classical-quantum channels. Two scenarios are considered. In the first scenario, the jammer knows the channel input, while in the second scenario the jammer knows both the channel input and the message. The transmitter and receiver share a secret random key with a vanishing key rate. The capacity for both average and maximum error criteria for both scenarios is determined in this paper. A strong converse is also proved. It is shown that all these corresponding capacities are equal, which means that additionally revealing the message to the jammer does not change the capacity. The communication scenario with a fully quantum jammer is considered in the second part of the paper. A single letter characterization for the capacity with secret random key as assistance for both average and maximum error criteria is derived in the paper.

We study the identification capacity of classical-quantum channels (“cq-channels”) under channel uncertainty and privacy constraints. To be precise, we first consider compound memoryless cq-channels and determine their identification capacity; then we add an eavesdropper by considering compound memoryless wiretap cqq-channels, and determine their secret identification capacity. In the first case (without privacy), we find the identification capacity always equal to the transmission capacity. In the second case, we find a dichotomy: either the secrecy capacity (also known as private capacity) of the channel is zero, and then the secrecy identification capacity is also zero, or the secrecy capacity is positive and then the secrecy identification capacity equals the transmission capacity of the main channel without the wiretapper. We perform the same analysis for the case of arbitrarily varying wiretap cqq-channels (cqq-AVWC) with analogous findings, and make several observations regarding the continuity and super-additivity of the identification capacity in the latter case.

In many different applications, it is important to determine the Hilbert transform of a given function. However, it is generally impossible to calculate it in closed form. Therefore Hilbert transform approximations are used. This paper studies the convergence and divergence behavior of general classes of such approximation methods. These classes are characterized by two very natural axioms and they include basically all known traditional numerical algorithms. The convergence of these methods is investigated on a family of signal spaces of continuous functions with finite energy. These spaces are parametrized by a number which measures the energy concentration in the low frequency components of the signal. It is shown that stable methods only exist on signal spaces with a sufficient energy concentration and this paper gives some explicit examples of convergent methods. On all other spaces in the family of signal spaces, every sampling-based Hilbert transform approximation shows a blowup behavior of its peak value, i.e., on these spaces, every sampling-based Hilbert transform approximation diverges.

Large peak to average power ratios (PAPRs) are problematic for communication systems. One possible approach to control the PAPR is the tone reservation method. We analyze the tone reservation method for general complete orthonormal systems, and consider two solvability concepts: strong solvability and weak solvability. Strong solvability requires a rather strong control of the peak value of the transmit signal by the energy of the information signal, and thus might be to restrictive for practical applications. Therefore, the concept of weak solvability was introduced, which only requires the boundedness of the transmit signal. In this paper we prove that weak solvability and strong solvability are equivalent for arbitrary complete orthonormal systems.

In this paper we study the tone reservation technique for the reduction of the peak to average power ratio (PAPR) in code division multiple access (CDMA) systems that employ the Walsh functions. In the tone reservation method, the available carriers are partitioned into two sets, the information set, which carries the information, and the compensation set, which is used to reduce the PAPR. Central questions are: What is the best possible reduction of the PAPR? What is the optimal information set that achieves this reduction, and how can it be found? What is the general structure of the information set? So far, the answers were unknown. In this paper we completely solve these questions for CDMA systems that employ the Walsh functions. Interestingly, using the first N Rademacher functions is optimal under all sets of size N.

Approximating the transfer function of stable causal linear systems by a basis expansion is a common task in signal- and system theory. This paper characterizes a scale of signal spaces, containing stable causal transfer functions, with a very simple basis (the Fourier basis) but which is not computable. Thus it is not possible to determine the coefficients of this basis expansion on any digital computer such that the approximation converges to the desired function. Since the Fourier basis is not computable, the second part of the paper investigates whether there exist better bases. To this end, the notion of a computational basis is introduced and it is shown that there exists no computational basis in these spaces. The paper characterizes also subspaces on which computational bases do exist.

Our work is based on a recently introduced mathematical theory of deep convolutional neural networks (DCNNs). It was shown that DCNN s are stable with respect to deformations of bandlimited input functions. In the present paper, we generalize this result: We prove deformation stability on Sobolev spaces. Further, we show a weak form of deformation stability for the whole input space L2(Rd). The basic components of DCNNs are semi-discrete frames. For practical applications, a concrete choice is necessary. Therefore, we conclude our work by suggesting a construction method for semi-discrete frames based on bounded uniform partitions of unity (BUPUs) and give a specific example that uses B-splines.

We investigate secure communication over a channel that undergoes two different classes of attacks at the same time: passive eavesdropping and active jamming. This scenario is perfectly modeled by the concept of arbitrarily varying wiretap channels (AVWCs). We derive a full characterization of the secrecy capacity of AVWCs under list decoding. We show that the list secrecy capacity is either equivalent to the correlated random secrecy capacity or zero depending on the order of symmetrizability of the legitimate AVC. Differently from correlated random codes, our coding scheme does not assume any restrictions on the communication between the eavesdropper and the jammer.

In this paper we propose a new model for arbitrarily varying classical-quantum channels. In this model a jammer has side information. We consider two scenarios. In the first scenario the jammer knows the channel input, while in the second scenario the jammer knows both the channel input and the message. The transmitter and receiver share a secret random key with a vanishing key rate. We determine the capacity for both average and maximum error criteria. We prove that additionally revealing the message to the jammer does not change the capacity.

We consider a model of communication via a fully quantum jammer channel with quantum jammer, quantum sender and quantum receiver, which we dub quantum arbitrarily varying channel (QAVC). Restricting to finite dimensional user and jammer systems, we show, using permutation symmetry and a de Finetti reduction, how the random coding capacity (classical and quantum) of the QAVC is reduced to the capacity of a naturally associated compound channel, which is obtained by restricting the jammer to i.i.d. input states. Furthermore, we demonstrate that the shared randomness required is at most logarithmic in the block length, via a quantum version of the “elimination of of correlation” using a random matrix tail bound. This implies a dichotomy theorem: either the classical capacity of the QAVC is zero, and then also the quantum capacity is zero, or each capacity equals its random coding variant.

We study the identification capacity of classical-quantum channels (“cq-channels”), under channel uncertainty and privacy constraints. To be precise, we consider first compound memoryless cq-channels and determine their identification capacity; then we add an eavesdropper, considering compound memoryless wiretap cqq-channels, and determine their secret identification capacity. In the first case (without privacy), we find the identification capacity always equal to the transmission capacity. In the second case, we find a dichotomy: either the secrecy capacity (also known as private capacity) of the channel is zero, and then also the secrecy identification capacity is zero, or the secrecy capacity is positive and then the secrecy identification capacity equals the transmission capacity of the main channel without the wiretapper. We perform the same analysis for the case of arbitrarily varying wiretap cqq-channels (cqq-AVWC), with analogous findings, and make several observations regarding the continuity and super-additivity of the identification capacity in the latter case.

In this paper we analyze the tone reservation method to reduce the peak to average power ratio (PAPR) in orthogonal frequency division multiplexing (OFDM) systems. We consider the case of a reduced compensation set, where only the positive carrier frequencies are used, and fully characterize the information sets for which the PAPR problem is solvable. It turns out that the reduction of the compensation set does not affect the solvability of the PAPR problem, however, the optimal constant are worse in general.

It was recently shown that on a large class of important Sobolev-like Banach spaces there exist no linear methods which are able to approximate the Hilbert transform from samples of the given function. This implies that there exists no linear algorithm for calculating the Hilbert transform which can be implemented on a digital computer and which converges for all functions from the corresponding Banach spaces. The present paper develops a much more general framework which includes also non-linear approximation methods. Algorithms within this framework have to satisfy only an axiom which guarantees the computability of the algorithm on a digital computer based on given samples of the function. Then the paper investigates whether there exists an algorithm within this general framework which converges to the Hilbert transform for all functions in the Sobolev-like Banach spaces. It is shown that non-linear methods give actually no improvement over linear methods.

The problem of identification is considered, in which it is of interest for the receiver to decide only whether a certain message has been sent or not, and the identification-feedback (IDF) capacity of channels with feedback is studied. The IDF capacity is shown to be discontinuous and super-additive for both deterministic and randomized encoding. For the deterministic IDF capacity the phenomenon of super-activation occurs, which is the strongest form of super-additivity. For the randomized IDF capacity, super-activation is not possible. These findings imply that the IDF capacity is not Turing computable.

We study the high-dimensional identification systems under the presence of statistical uncertainties. The task is to design mappings for enrollment and identification purposes. The identification mapping compresses users' information then stores the index in the corresponding position in a database. The identification mapping combines the information in the database and the observation which originates randomly from an enrolled user to produce an estimate of the underlying user index. We study two scenarios. Users' data are generated from the same unknown distribution while the observation channel is also subjected to uncertainty. Each user's data are generated iid from the distribution corresponding to its own state, while the observation channel is known. We provide an achievable compression-identification trade-off for the first and second settings considering both discrete and continuous cases. In the discrete scenario, the described regions are also the correspondingly complete characterizations.

We determine the secrecy capacities of AVQCs (arbitrarily varying quantum channels). Both secrecy capacity with average error probability and with maximal error probability are derived. Both derivations are based on one common code construction. The code we construct fulfills a stringent secrecy requirement, which is called the strong code concept. We determine when the secrecy capacity is a continuous function of the system parameters and completely characterize its discontinuity points both for average error criterion and for maximal error criterion. Furthermore, we prove the phenomenon “super-activation” for secrecy capacities of AVQCs, i.e., two quantum channels both with zero secrecy capacity, which, if used together, allow secure transmission with positive capacity. We also discuss the relations between the entanglement distillation capacity, the entanglement generating capacity, and the strong subspace transmission capacity for AVQCs.

A post-detection receive diversity scheme for reliable communication in vehicular scenarios under arbitrarily varying interference is presented. An approach to system implementation based on a distributed antenna system is outlined. The Shannon capacities of end-to-end communication chains involving different state-of-the-art combining schemes are compared to each other in two different situations: First without interference and second with arbitrarily varying interference. It is proven that the majority vote and maximum-ratio combiners fail for many scenarios with arbitrarily varying interference. Further, numerical studies are provided that allow for comparison of majority vote, maximum-ratio and maximum-likelihood combining when the number of receive antennas in a single-input-multiple-output communication system increases.

We determine the identification capacity of compound channels in the presence of a wiretapper. It turns out that the secure identification capacity formula fulfills a dichotomy theorem: It is positive and equals the identification capacity of the channel if its message transmission secrecy capacity is positive. Otherwise, the secure identification capacity is zero. Thus, we show in the case that the secure identification capacity is greater than zero we do not pay a price for secure identification, i.e., the secure identification capacity is equal to the identification capacity. This is in strong contrast to the transmission capacity of the compound wiretap channel. We then use this characterization to investigate the analytic behavior of the secure identification capacity. In particular, it is practically relevant to investigate its continuity behavior as a function of the channels. We completely characterize this continuity behavior. We analyze the (dis-) continuity and (super-) additivity of the capacities. In 1998, N. Alon gave a conjecture about maximal violation for the additivity of capacity functions in graphs. We show that this maximal violation as well holds for the secure identification capacity of compound wiretap channels. This is the first example of a capacity function exhibiting this behavior.

In secret-key generation using a compound source, the actual statistics of the source are unknown to the participants. It is assumed rather that the actual source belongs to a set (compound set) which is known to the participants. The secret-key generation protocol should guarantee in this case reliability and security of the generated secret-key simultaneously for all elements of the compound set. In this paper, secret-key generation based on a three-party compound source is studied in which an eavesdropper's side information is also taken into account and strong secrecy is guaranteed. At the same time, the public communication rate constraint between the legitimate users is part of the secret-key generation protocol. In this setting, the achievable secret-key rates for finite compound sources are first reformulated as a region of secret-key rate versus communication rate constraint pairs. It is shown that this region is in general convex, even if the compound set is infinite. Based on this, the secret-key capacity results are extended to be valid for arbitrary (possibly infinite) compound sources with a finite set of marginals. In this case, the secret-key capacity is completely characterized as a function of the forward communication rate parameter between the legitimate users.

High peak values of transmission signals in wireless communication systems lead to wasteful energy consumption and degradation of several transmission performances. We continue the theoretical contributions made by Boche and Farell toward the understanding of peak value reduction, using the strategy known as tone reservation for orthogonal transmission schemes. There it was shown that for orthogonal frequency-division multiplexing (OFDM) systems, the combinatorial object called arithmetic progression plays an important role in setting limitations for the applicability of the tone reservation method. In this paper, we show that the combinatorial object introduced as perfect Walsh sum (PWS) plays a similar role for code-division multiple access (CDMA) systems as arithmetic progression for OFDM systems. By specific construction, we show that for a chosen numbers m and n, all subsets I of the set [N] of the first N = 2nnatural numbers, which has the density in [N] larger than a given δ ∈ (0, 1), i.e., |I| / N ≥ δ, and which is sufficiently large enough, in the sense that |I| ≥ 2(2/δ)2m-1, contains a PWS of size 2m. By means of this result, and motivated by the previously mentioned connection between arithmetic progression and PWS, we show results for the PWS which are analogous to the famous Szemerédi theorem on arithmetic progressions, ConlonGower's theorem on probabilistic construction of “sparse” sets containing an arithmetic progression, and even a solution of an analogon to the Erdos' conjecture on arithmetic progressions. Those results give in particular an insight into the asymptotic limitations of tone reservation method for the CDMA systems. Besides, we show that a subset I of [N] is a PWS if and only if the embedding inequality of the subspace of L1([0, 1]), containing linear combinations of Walsh functions indexed by elements of I, holds with the minimum possible embedding constant √|I|. The corresponding approach based in particular by the fact that the PWSs are the only Walsh sums having unit L1-norm, proven in this paper. By means of that results, we show that the minimum possible threshold constant for which the tone reservation method is applicable yields √|I| if and only if the information set I is a PWS.

The question of reliability in self-coordinating vehicular networks is discussed. Most state-of-the-art approaches have no central entity controlling channel access, so there may be arbitrary interference from other parties. Thus, a suitable channel model is the Arbitrarily Varying Channel (AVC). Employing multiple antennas on a receiver to make use of spatial diversity is a promising approach to combat interference. An important question then is, how many antennas are needed to harvest the maximum gain. For Binary Symmetric AVCs (AVBSC) and an identical state-constrained jammer already the deployment of three, uncorrelated receive antennas avoids symmetrizability and thus ensures positive capacity. Furthermore, the deterministic capacity of the identical state-constrained composite AVBSC is continuous and can be super-activated, a phenomenon which hitherto, was deemed impossible for classical communication without secrecy constraints. Subsuming, receive antenna diversity is an enabler for reliable communication over communication channels with arbitrarily varying interference.

In this paper we analyze the convergence behavior of a sampling based system approximation process, where the time variable is in the argument of the signal and not in the argument of the bandlimited impulse response. We consider the Paley-Wiener space PWπ2of bandlimited signals with finite energy and stable linear time-invariant (LTI) systems, and show that there are signals and systems such that the approximation process diverges in the L2-norm, i.e., the norm of the signal space. We prove that the sets of signals and systems creating divergence are jointly spaceable, i.e., there exists an infinite dimensional closed subspace of PWπ2and an infinite dimensional closed subspace of the space of all stable LTI systems, such that the approximation process diverges for any non-zero pair of signal and system from these subspaces.

It is known that there exist signals in Paley-Wiener space PWπ1of bandlimited signals with absolutely integrable Fourier transform, for which the peak value of the Shannon sampling series diverges unboundedly. In this paper we analyze the structure of the set of signals which lead to strong divergence. Strong divergence is closely linked to the existence of adaptive methods. We prove that there exists an infinite dimensional closed subspace of PW1π1, all signals of which, except the zero signal, lead to strong divergence of the peak value of the Shannon sampling series.

High peak values of transmission signals in wireless communication systems lead to wasteful energy consumption and degradation of several transmission performances. We continue the theoretical contributions made by B. and Farell [1, 2] towards the understanding of peak value reduction, using the strategy known as tone reservation for orthogonal transmission schemes. There it was shown that for OFDM systems, the combinatorial object called arithmetic progression plays an important role in setting limitations for the applicability of the tone reservation method. In this work, we consider ourselves with the performance of the tone reservation in the probabilistic asymptotic setting. We show in particular that for a sufficiently large number N of carriers, choosing each element of that set independently with arbitrary small probability, yields in turn a set of carriers, for which the PAPR reduction problem is not solvable with certain explicitly given threshold constants with probability 1 as N goes to infinity.

For secret-key generation by using a compound source, the actual statistics of the source are unknown to the participants. It is assumed that the probability distribution of the source belongs to a set which is known to the participants. The secret-key generation protocol should guarantee in this case the reliability and security of the generated secret-key simultaneously for all possible source statistics which belong to this set. At the same time, the communication rate between the legitimate users should not exceed a given communication rate parameter. In this work, this problem is studied for the case where the set of source states is arbitrary (possibly infinite) and the set of marginals (transmitter's states) is finite. The secret-key capacity is completely characterized as a function of the forward communication rate parameter between the legitimate users.

We analyze arbitrarily varying classical-quantum wiretap channels. These channels are subject to two attacks at the same time: one passive (eavesdropping), and one active (jamming). We progress on previous works [5] and [6] by introducing a reduced class of allowed codes that fulfills a more stringent secrecy requirement than earlier definitions. In addition, we prove that non-symmetrizability of the legal link is sufficient for equality of the deterministic and the common randomness assisted secrecy capacities. At last, we focus on analytic properties of both secrecy capacities: We completely characterize their discontinuity points, and their super-activation properties.

We determine the identification capacity of compound channels with and without wiretapper. It turned out, that the secure capacity formula fulfill a dichotomy theorem. It is positive if its secure capacity is positive and equals the transmission capacity of the channel. Otherwise the capacity is zero. We analyze the (dis-)continuity and (super-)additivity of the capacities, which we determined. Alon gave in [6] a conjecture about maximal violation for the additivity for capacity functions. We show that this maximal violation holds for the secure identification capacity. This is the first example of a capacity function, which has this behavior.

In this paper we analyze the peak-to-average power ratio (PAPR) reduction by tone reservation for orthogonal frequency division multiplexing (OFDM) schemes. In addition to the strong solvability of the PAPR reduction problem, where the PAPR has to be bounded by some constant, we consider a weaker form of solvability, where only the boundedness of the peak value of the signal is required. We show that for OFDM both forms of solvability are equivalent. Further, we show that in the case where the PAPR problem is not solvable, the set of input signals that lead to an unbounded OFDM signal is a residual set. As a consequence, if the upper density of the carriers, used for information transmission, is positive, the set of input signals that lead to a bounded OFDM signal is a meager set.

The Hilbert transform plays an important role in many different applications. Especially in the area of detection and estimation it is closely related to the calculation of the spectral factorization. Generally, it is not possible to calculate the Hilbert transform in closed form. Therefore approximation methods are applied. This paper studies the stability of a general class of approximation algorithms for the Hilbert transform which contains all traditional numerical integration methods. To this end, the paper introduces a scale of signal spaces with finite energy in which a factor (log n)βmeasures the concentration of the signal energy in its Fourier coefficients cn. It will be shown that if the energy concentration is too weak, i.e. if 0 ≤ β ≤ 1, then every approximation method diverges. Conversely, if the energy concentration is sufficiently good, i.e. if β > 1, convergent approximation methods do exist and we give a natural characterization of all convergent methods.

The arbitrarily varying channel (AVC) models communication over a channel that varies in an arbitrary and unknown manner from channel use to channel use. This paper considers the AVC under list decoding and studies the corresponding list capacity. In particular, the list capacity function is shown to be discontinuous and the corresponding discontinuity points are characterized for all possible list sizes. For orthogonal AVCs it is then shown that the list capacity is super-additive, implying that joint encoding and decoding for two orthogonal AVCs can yield a larger list capacity than independent processing of both channels. This discrepancy is shown to be arbitrary large.

The high peak value of the transmission signal of wireless communication systems lead to wasteful energy consumption and degradation of several transmission performances. We continue the theoretical contributions made in [1], [2] towards the understanding of tone reservation method for orthogonal transmission schemes. There it was shown that the combinatorial object called arithmetic progression plays an important role in setting limitations for the applicability of the tone reservation method for OFDM system. In this work, we introduce the combinatorial object called perfect Walsh sum (PWS), playing a similar role for CDMA systems as arithmetic progression for OFDM systems. We show that for a given m, n ϵ N and δ ϵ (0, 1), every subset I of the set [N] of the first N=2nnumbers, which fulfills |I|/N ≥ δ and |I| ≥ 2(2/δ)2m - 1, contains a PWS of size 2m. Consequences of the latter are results analogous to the famous Szemerédi Theorem on arithmetic progressions, Conlon-Gower's Theorem on probabilistic construction of “sparse” sets containing an arithmetic progression, and even a solution of Erdos' conjecture on arithmetic progressions. Those results give in particular an insight into the asymptotic behaviour of tone reservation method for CDMA systems.

Fractional repetition (FR) codes is a class of codes which were recently introduced for distributed storage systems. These codes are intended for exact uncoded repair of node failures, by downloading symbols from a suitable subset of surviving nodes. The repair procedure in FR codes is table based, unlike the regenerating codes, where the repair of a failed node is possible using arbitrary subset of a given size from surviving nodes. The advantage of this relaxation is that it allows to achieve low complexity in repair process, while these codes have minimum repair bandwidth like minimum bandwidth regenerating (MBR) codes. In this paper we give new and simple constructions for universally good FR codes based on partially ordered sets. These codes allow for efficient uncoded repair and the resulting designs are scalable and easy to implement. In particular, they allow to store larger files as compared to MBR codes. Furthermore, the constructions can be extended to FR codes for heterogeneous storage systems.

The delay-limited capacity (DLC) is introduced as a criterion for performance evaluation for future vehicular connectivity concepts with special focus on delay-critical message transmission. Upcoming connectivity standards rely on fail-safe operation and secure information exchange. For this reason, asymptotic performance measures like the ergodic capacity are not suited for system assessment as they do not guarantee that a data packet is transmitted successfully in a finite time frame. By utilizing the DLC for end-to-end analysis of a connectivity system, a future-proof method for performance evaluation in a city scenario is presented. A measurement campaign in a vehicular connectivity environment is provided for different antenna configurations. The effect of correlation on the DLC is analyzed theoretically and based on measurements by comparing a co-located vehicular multiple-input-multiple-output (MIMO) configuration with a side mirror MIMO antenna system.

In the classical secret-key generation model, common randomness is generated by two terminals based on the observation of correlated components of a common source, while keeping it secret from a non-legitimate observer. It is assumed that the statistics of the source are known to all participants. In this paper, the secret-key generation based on a compound source is studied where the realization of the source statistic is unknown. The protocol should guarantee the security and reliability of the generated secret-key, simultaneously for all possible realizations of the compound source. A single-letter lower-bound of the secret-key capacity for a finite compound source is derived as a function of the public communication rate constraint. A multi-letter capacity formula is further computed for a finite compound source for the case in which the public communication is unconstrained. Finally, a single-letter capacity formula is derived for a degraded compound source with an arbitrary (possibly infinite) set of source states and a finite set of marginal states.

The approximation of stable linear time-invariant (LTI) systems is studied for the Paley-Wiener space PWπ1of bandlimited functions with absolutely integrable Fourier transform. For pointwise sampling, it is known that there exist stable LTI systems and functions such that the approximation process diverges, regardless of the oversampling factor. Recently, it was shown that the divergence can be overcome by using more general measurement functionals that are based on a complete orthonormal system. However, this approach requires the approximation process to have an increased bandwidth. In this paper, a two channel approximation process is presented that is uniformly convergent for all stable LTI systems and all functions in PWπ1. An advantage of the two channel approach compared with the one channel approach is the reduction of the approximation bandwidth, which can be exactly the same as the input function bandwidth.

Many important non-adaptive approximation methods are know to diverge for almost all functions from certain Banach space X. One can show that a corresponding adaptive method will improve this behavior in the sense that it converges to the desired result for almost all functions in X. However, even though an adaptive method tries to find an optimal approximation for any given function, the search horizon (i.e. the search set) has to be finite in practical applications. This paper shows that an adaptive method with finite search horizon either converges for all f ϵ X or it diverges for almost all f ϵ X. As an example, we show that there exists no realizable adaptive method which can calculate the Hilbert transform of a continuous function f based on samples of f.

In this work, we show by means of the technique inspired by the Banach-Steinhaus Thm., that typically the Fourier transform of an integrable signal decays arbitrarily slowly toward the infinity, and has an arbitrary weak worst continuity/smoothness behaviour. However, the corresponding characterization can only be given weakly by means of the limit superior. Those statements gives therefore a tightening of the famous Riemann-Lebesgue's Lemma. Furthermore, we give a construction of functions, whose Fourier transform decays slowly than an arbitrary given decay rate. Inspired by that, we are also able to give an alternative proof of the strong divergence of the Shannon sampling series [1] for signals in the Paley-Wiener space PW(ωg)1, band-limited to an arbitrary ωgϵ ℝ+. The corresponding construction of signals is stronger than the existent one given by Boche and Farell, and gives a new insight into the divergence phenomenon of the Shannon sampling series.

We determine the secrecy capacities under common randomness assisted coding of arbitrarily varying classical-quantum wiretap channels. Furthermore, we determine the secrecy capacity of a mixed channel model which is compound from the sender to the legal receiver and varies arbitrarily from the sender to the eavesdropper. As an application we examine when the secrecy capacity is a continuous function of the system parameters and show that resources, i.e., having access to a perfect copy of the outcome of a random experiment, are helpful for channel stability.

We study an analog of the well-known Gel'fand Pinsker Channel which uses quantum states for transmission of data. We consider the case where both the sender's inputs to the channel and the channel states are elements of a finite set (cq-channel with state information at the sender). While the receiver has no information about the channel states, we distinguish between two cases at the sender: he either gets causal or non-causal channel state information. We give a single-letter description of the capacity in the first case and present two different regularized expressions of the capacity for the second. It turns out that the change from causal to non-causal channel state information at the encoder causes the complexity of numerical computation of the capacity formula to change from simple to seemingly difficult. Still, even in the difficult non-causal case we draw nontrivial conclusions, for example regarding continuity of the capacity with respect to changes in the system parameters.

We consider the task of entanglement assisted message transmission under presence of a compound memoryless quantum channel. In this model, the completely positive and trace preserving map governing the channel statistics is, instead of being perfectly known, only revealed as member of a certain set of channels. Therefore, coding schemes have to be used which are simultaneously reliable for each member of this set. Utilizing universal codes for classical-quantum channels, we introduce optimal universal coding schemes for entanglement assisted message transmission of compound quantum channels. The resulting coding theorem together with a corresponding converse statement leads us to a single-letter expression for the entanglement assisted message transmission capacity of compound quantum channels.

Knowing whether a reconstruction process, for example the Shannon sampling series, is strongly divergent in terms of the lim or only weakly divergent in terms of the lim sup is important, because strong divergence is linked to the non-existence of adaptive reconstruction processes. For non-adaptive reconstruction processes the existence is answered by the Banach-Steinhaus theory. However, the analysis of adaptive reconstruction processes is more difficult and not covered by the former theory. In this paper we consider the Paley-Wiener space PWπ1of bandlimited signals with absolutely integrable Fourier transform and analyze the structure of the set of signals for which the peak value of the Shannon sampling series is strongly divergent. We show that this set is lineable, i.e., that there exists an infinite dimensional subspace, all signals of which, except the zero signal, lead to strong divergence. Consequently, for all signals from this subspace, adaptivity in the number of samples that are used in the Shannon sampling series does not create a convergent reconstruction process.

The question of additivity of the capacity of a channel goes back to Shannon who asked this for the zero error capacity function. Despite the common sense that the capacity is usually additive, there is surprisingly little known for non-trivial channels. This paper addresses this question for the arbitrarily varying wiretap channel (AVWC) which models secure communication in the presence of arbitrarily varying channel (AVC) conditions. For orthogonal AVWCs it has been shown that the non-additivity phenomenon of super-activation occurs; that is, there are orthogonal AVWCs, each having zero secrecy capacity, which allow for transmission with positive secrecy rate if they are used together. It is shown that for such orthogonal AVWCs super-activation is generic in the sense that whenever super-activation is possible, it is possible for all AVWCs in a certain neighborhood as well. Moreover, it is shown that the issue of super-activation and the continuity of the secrecy capacity solely depend on the legitimate link. Accordingly, the single-user AVC is studied and it is shown that in this case, super-activation for non-secure message transmission is not possible, making it a unique feature of secure communication over AVWCs. However, the capacity for message transmission of the single-user AVC is shown to be super-additive including a complete characterization.

In this paper, the problem of securely computing a function over the binary modulo-2 adder multiple-access wiretap channel is considered. The problem involves a legitimate receiver that wishes to reliably and efficiently compute a function of distributed binary sources while an eavesdropper has to be kept ignorant of them. In order to characterize the corresponding fundamental limit, the notion of secrecy computation-capacity is introduced. Although determining the secrecy computation-capacity is challenging for arbitrary functions, it surprisingly turns out that if the function perfectly matches the algebraic structure of the channel and the joint source distribution fulfills certain conditions, the secrecy computation-capacity equals the computation capacity, which is the supremum of all achievable computation rates without secrecy constraints. Unlike the case of securely transmitting messages, no additional randomness is needed at the encoders nor does the legitimate receiver need any advantage over the eavesdropper. The results therefore show that the problem of securely computing a function over a multiple-access wiretap channel may significantly differ from the one of securely communicating messages.

In this paper we consider a wiretap channel II with an active eavesdropper. Aggarwal et al (2009) were the first who studied the Ozarow-Wyner's binary wiretap channel II in the presence of an active eavesdropper. They derived achievable secrecy rates for two modification models where the eavesdropper can erase/replace the bits he observes. The existence of better achievable rates remains an open problem. Here we study a model with a less powerful eavesdropper. The eavesdropper is able now to observe any interval of μ symbol positions and erase the symbols in any interval of l positions of a transmitted codeword. We present an explicit construction of nested linear codes that achieve maximum secrecy rate for the finite length coding regime, with perfect secrecy and zero-error decoding, for any admissible code parameters.

In this paper, secure communication over a broadcast channel with multiple legitimate receivers and an external eavesdropper is investigated. Two different secrecy measures are considered. The first criterion is a conservative one known as joint secrecy, where the mutual leakage of all confidential messages must be small. The second criterion is a less conservative constraint known as individual secrecy, where the individual leakage of each confidential message must be small. At first, we consider the degraded multi-receiver wiretap broadcast channel and manage to establish the individual secrecy capacity region. Our encoding scheme applies a careful combination of the standard techniques of wiretap random coding and Shannon's one time pad encoding, where the confidential messages of the weak receivers are used as secret keys for the stronger ones. The validity of this technique is due to the properties of the degraded broadcast channel and the secrecy requirements of the individual secrecy criterion. Our result indicates that the individual secrecy capacity region is in fact larger than the joint one established in earlier literature. The established capacity region is then used to derive the individual secrecy capacity regions of the Gaussian single-input single-output and degraded Gaussian multiple-input multiple-output multi-receiver wiretap broadcast channels. Furthermore, we present an achievable rate region for the general two-receiver wiretap broadcast channel under both the joint and the individual secrecy criterion. Comparing these two rate regions suggests that even for the general case, the individual secrecy criterion might be able to provide a larger rate region compared with the joint one.

We define the common randomness-assisted capacity of an arbitrarily varying wiretap channel (AVWC) when the eavesdropper is kept ignorant about the common randomness. We prove a multi-letter capacity formula for this model. We prove that, if enough common randomness is used, the capacity formula can be given a single-shot form again. We then consider the opposite extremal case, where no common randomness is available, and derive the capacity. It is known that the capacity of the system can be discontinuous under these circumstances. We prove here that it is still stable in the sense that it is continuous around its positivity points. We further prove that discontinuities can only arise if the legal link is symmetrizable and characterize the points where it is positive. These results shed new light on the design principles of communication systems with embedded security features. At last, we investigate the effect of super-activation of the message transmission capacity of AVWCs under the average error criterion. We give a complete characterization of those AVWCs that may be super-activated. The effect is thereby also related to the (conjectured) super-activation of the common randomness assisted capacity of AVWCs with an eavesdropper that gets to know the common randomness. Super-activation is based on the idea of wasting a few bits of non-secret messages in order to enable provably secret transmission of a large bulk of data, a concept that may prove to be of further importance in the design of communication systems. In this paper, we provide further insight into this phenomenon by providing a class of codes that is capacity achieving and does not convey any information to the eavesdropper.

We give a complete characterization of the correlated random coding secrecy capacity of arbitrarily varying wiretap channels (AVWCs). We apply two alternative strong secrecy criteria, which both lead to the same multi-letter formula. The difference of these criteria lies in the treatment of correlated randomness; they coincide in the case of uncorrelated codes. On the basis of the derived formula, we show that the correlated random coding secrecy capacity is continuous as a function of the AVWC, in contrast to the discontinuous uncorrelated coding secrecy capacity. In the proof of the secrecy capacity formula for correlated random codes, we apply an auxiliary channel, which is compound from the sender to the intended receiver and arbitrarily varying from the sender to the eavesdropper.

Strategic users in a wireless network cannot be assumed to follow the network algorithms blindly. Moreover, some of these users aim to use their knowledge about network algorithms to maliciously gain more resources and also to create interference to other users. We consider a scenario, in which the network and legitimate users gather probabilistic information about the presence of malicious users by observing the network over a long time period. The network (mechanism designer) and legitimate users modify their actions according to this Bayesian information. We consider Bayesian mechanisms, both pricing schemes and auctions, and obtain the Bayesian Nash Equilibrium (BNE) points. The BNE points provide conditions under which, the uncertainty about user's nature (type) is better for regular (legitimate) users. To derive these conditions, we compare the Bayesian case to the complete information case. We obtain the optimal prices and allocations, which counter the malicious users. We also provide detection methods based on machine learning algorithms for the detection of malicious users, by observing the prices and rate allocations. In addition, we provide detection using regression learning by observing the anomalies in the utility functions of malicious users from prices, which is implemented along with the pricing mechanism itself. For the designer and the regular users, in a complementary fashion, the results of the detections provide a better estimate of the statistics of malicious users to implement the pricing mechanisms. We have also proposed a truthful Bayesian mechanism in the presence of malicious users. The numerical studies for malicious user detection are carried out with the model proposed in the paper as well as using real Botnet dataset.

Many divergence results for sampling series are in terms of the limit superior and not the limit. This leaves the possibility of a convergent subsequence. If there exists a convergent subsequence, adaptive signal processing techniques can be used. In this paper we study sampling-based signal reconstruction and system approximation processes for the space PWπ1of bandlimited signals with absolutely integrable Fourier transform. For all analyzed examples, which include the peak value of the Shannon and the conjugated Shannon sampling series, we prove strong divergence, i.e., divergence for all subsequences. Hence, adaptive signal processing techniques do not help in these cases. We further analyze whether an adaptive choice of the reconstruction functions in the oversampling case can improve the behavior.

The approximation of linear time-invariant (LTI) systems by sampling series is an important topic in signal processing. However, the convergence of the approximation series is not guaranteed: there exist stable LTI systems and bandlimited input signals such that the approximation series diverges, regardless of the oversampling factor and the sampling pattern. Recently, it has been shown that this divergence can be overcome by using measurement functionals instead of pointwise sampling. However, the bandwidth of the approximation series needs to be strictly larger than the signal bandwidth. In this paper we derive a two channel system approximation approach based on measurement functionals that converges for all stable LTI systems and all signals in the Paley-Wiener space PWπ1. Thanks to the two channel structure it is possible to achieve an approximation bandwidth that is equal to the signal bandwidth.

This paper considers the problem of recovering a k-sparse, N-dimensional complex signal from Fourier magnitude measurements. It proposes a Fourier optics setup such that signal recovery up to a global phase factor is possible with very high probability whenever M ≳ 4k log2(N/k) random Fourier intensity measurements are available. The proposed algorithm is comprised of two stages: An algebraic phase retrieval stage and a compressive sensing step subsequent to it. Simulation results are provided to demonstrate the applicability of the algorithm for noiseless and noisy scenarios.

The performance of a secure communication system such as the wiretap channel is usually characterized by its secrecy capacity. In this paper, the issue of whether or not the secrecy capacity is a continuous function of the system parameters is examined. In particular, this is done for channel uncertainty modeled via compound channels and arbitrarily varying channels, in which the legitimate users know only that the true channel realization is from a pre-specified uncertainty set. In the former model, this realization remains constant for the entire duration of transmission, while in the latter the realization varies from channel use to channel use in an unknown and arbitrary manner. The secrecy capacity of the compound wiretap channel is shown to be robust in the sense that it is a continuous function of the uncertainty set. Thus, small variations in the uncertainty set lead to small variations in secrecy capacity. However, the secrecy capacity of the arbitrarily varying wiretap channel is shown to be discontinuous in the uncertainty set meaning that small variations can lead to dramatic losses in capacity.

When there are strategic and malicious users in a wireless network, the resource allocation is complicated due to the information limitation about the nature of users and network parameters. Bayesian games are appropriate tools to analyze the network resource allocation with heterogeneous users. We consider a scenario with arbitrary number of malicious users in the network, in which individual users gather probabilistic information about the density of malicious users. Users and the base station observe the network over a long time period and modify their actions accordingly. The power allocation in wireless networks which we consider in this paper, is subject to Quality of Service (QoS) requirements. We consider Bayesian pricing mechanisms where the prices are modified using the Bayesian information about types of the users to satisfy the QoS requirements. We also give detection methods based on regression learning algorithms which are used for forming the probability of a user being malicious. The utilities of the users are formed by observing the power strategies of the users and the anomalies are detected. We obtain numerically, the Bayesian Nash Equilibrium (BNE) points of the Bayesian games. We also evaluate the effect of incomplete information on the satisfaction of the QoS requirements of the users in the mechanisms. These mechanisms are with prices which were originally developed for networks with complete information.

In this work, a recently proposed analog transmission scheme is considered, which harnesses interference for reliably and efficiently computing real-valued functions over a wireless channel. To better understand the corresponding trade-off between the conflicting demands of reliability and efficiency, in this paper we choose an information theoretic perspective by analyzing the scheme within the framework of computation coding. Towards this end, we first adapt the standard notions of a computation code and an achievable computation rate to our specific needs and then provide rate expressions for some simple but insightful examples. It turns out that the achievable computation rates not only depend on the function to be computed but also on the desired accuracy and the number of concurrently active transmitters.

We study secure communication over a degraded wiretap broadcast channel with multiple receivers and an eavesdropper. We consider two different secrecy measures: the traditional joint secrecy where the mutual information leakage of all messages must be small; and individual secrecy where the sum of the information leakage of each individual message must be small. At first, we investigate the joint secrecy criterion, where we present the capacity region established before and provide a simpler converse proof. We then consider the individual secrecy criterion and establish its capacity region, by combining the techniques of wiretap random coding and Shannon's one time pad principle. Our results indicate that the individual secrecy capacity region is bigger than the joint one. Further, we show that the established capacity regions are valid for any degraded wiretap broadcast channel, regardless of the degradedness order of the eavesdropper. Finally, we extend our results to Gaussian channels.

We study the arbitrarily varying wiretap channel (AVWC) under average error criterion when external common randomness (CR) can be used between the legitimate parties. We consider three scenarios: In the first one the CR is known to the eavesdropper, in the second it is not known to her and in the third there is no CR available. For the second scenario, we prove a complete coding theorem. For the third scenario it is known that the capacity function is discontinuous. We prove that it is nonetheless stable in the sense of being continuous around its positivity points. We characterize the points of discontinuity in terms of continuous functions. We then give a complete characterization of those pairs of AVWCs whose capacity can be super-activated in the unassisted third case - in terms of the capacity function describing the first case.

We give a complete characterization of the secrecy capacity of arbitrarily varying wiretap channels (AVWCs) with correlated random coding under a strong secrecy criterion where the eavesdropper may also know the correlated randomness. We obtain that the correlated random coding secrecy capacity is continuous as a function of the AVWC. We show that the deterministic coding secrecy capacity of the AVWC either equals 0 or the correlated random coding secrecy capacity. For the case that only a weak secrecy criterion is applied, a complete characterization of the corresponding secrecy capacity for deterministic codes is possible. In the proof of the secrecy capacity formula for correlated random codes, we apply an auxiliary channel which is compound from the sender to the intended receiver and varies arbitrarily from the sender to the eavesdropper. We discuss the relation between the usual mutual information secrecy criterion and a criterion formulated in terms of total variation distance, and investigate the robustness of the AVWC model.

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.

Information theoretic approaches to security have been examined as a promising complement to current cryptographic techniques. Such information theoretic approaches establish reliable communication and data confidentiality directly at the physical layer of a communication network by taking the properties of the noisy channel into account leading to unconditional security regardless of the computational capabilities of eavesdroppers. The provision of accurate channel state information is a major challenge particularly in wireless communication systems, especially information about the channels to eavesdroppers. In addition, there might be malevolent adversaries who jam or influence the channel of the legitimate users. This paper surveys different models for secure communication under channel uncertainty and adversarial attacks and reviews the corresponding secrecy capacity results, which characterize the maximum rate at which information can be sent to legitimate receivers while being kept perfectly security from eavesdroppers.

The wiretap channel models secure communication between two users in the presence of an eavesdropper who must be kept ignorant of transmitted messages. The performance of such a system is usually characterized by its secrecy capacity which determines the maximum transmission rate of secure communication. In this paper, the issue of whether or not the secrecy capacity is a continuous function of the system parameters is examined. In particular, this is done for channel uncertainty modeled via compound channels and arbitrarily varying channels, in which the legitimate users know only that the true channel realization is from a prespecified uncertainty set. In the former model, this realization remains constant for the entire duration of transmission, while in the latter the realization varies from channel use to channel use in an unknown and arbitrary manner. These models not only capture the case of channel uncertainty, but are also suitable for modeling scenarios in which a malicious adversary jams or otherwise influences the legitimate transmission. The secrecy capacity of the compound wiretap channel is shown to be robust in the sense that it is a continuous function of the uncertainty set. Thus, small variations in the uncertainty set lead to small variations in secrecy capacity. On the other hand, the deterministic secrecy capacity of the arbitrarily varying wiretap channel is shown to be discontinuous in the uncertainty set meaning that small variations can lead to dramatic losses in capacity.

In this paper, a clustered wireless sensor network is considered that is modeled as a set of coupled Gaussian multiple-access channels. The objective of the network is not to reconstruct individual sensor readings at designated fusion centers but rather to reliably compute some functions thereof. Our particular attention is on real-valued functions that can be represented as a post-processed sum of pre-processed sensor readings. Such functions are called nomographic functions and their special structure permits the utilization of the interference property of the Gaussian multiple-access channel to reliably compute many linear and nonlinear functions at significantly higher rates than those achievable with standard schemes that combat interference. Motivated by this observation, a computation scheme is proposed that combines a suitable data pre- and post-processing strategy with a nested lattice code designed to protect the sum of pre-processed sensor readings against the channel noise. After analyzing its computation rate performance, it is shown that at the cost of a reduced rate, the scheme can be extended to compute every continuous function of the sensor readings in a finite succession of steps, where in each step a different nomographic function is computed. This demonstrates the fundamental role of nomographic representations.

The approximation of linear time-invariant (LTI) systems by sampling series is an important topic in signal processing. However, the convergence of the approximation process is not guaranteed. In this paper we prove that for every sampling pattern that is a complete interpolating sequence there exists a universal stable LTI system such that for every oversampling factor there exists a bandlimited input signal such that the approximation process, which is used to approximate the output signal of the LTI system, diverges. This result shows a fundamental limit for the digital sampling-based implementation of systems.

The approximation of linear time-invariant (LTI) systems by sampling series is an important topic in signal processing. Recently, it was conjectured [1] and proved [2] that, for every sampling pattern that is a complete interpolating sequence, there exists a universal stable LTI system such that for every oversampling factor there exists a bandlimited input signal such that the approximation process, which is used to approximate the output signal of the LTI system, diverges. This instability of the approximation process shows a fundamental limit of sampling-based signals processing. However, as is shown in this paper, by using more general measurement functionals this divergence can be overcome.

This paper considers the problem of signal recovery from magnitude measurements for signals in modulation invariant spaces. It proposes a measurement setup such that almost every signal in such a signal space can be reconstructed from its amplitude measurements up to a global constant phase and with a sampling rate of four times the rate of innovation of the signal space. The applicability of the proposed scheme under noise measurements is demonstrated by computer simulations.

The compound broadcast channel with confidential messages is studied, where the transmitter sends a common message to two receivers and, at the same time, a confidential message to one receiver which has to be kept secret from the other one. It is only known to the transmitter and receivers that the actual channel realization is fixed and from a pre-specified set of channels. The information theoretic criterion of strong secrecy is analyzed in detail and generalized in such a way that it completely captures the behavior and the abilities of the non-legitimate receiver. Its impact on the decoding performance of the non-legitimate receiver is characterized as well. In particular, it is shown that regardless of the computational capabilities and the applied decoding strategy of the non-legitimate receiver, his decoding error always tends to one. This gives a valuable signal processing implication of the generalized secrecy criterion and identifies desirable properties of an optimal code design.

The use of secret keys in broadcast channels with receiver side information is studied. The particular scenario is analyzed where a transmitter wants to send two confidential messages to two receivers, while keeping an external eavesdropper ignorant. Each receiver has one of the confidential messages as side information available for decoding. In addition to that, the transmitter shares independent secret keys of arbitrary rates with both receivers. The secret keys can be used in different ways: They can act as one-time pads to encrypt the confidential messages or they can be used as randomization resources for wiretap coding. Both approaches are discussed and an achievable rate region based on superposition coding is established for the one-time pad approach. For the wiretap coding approach, the secrecy capacity for degraded channels is derived. In the optimal coding scheme, the available secret keys are used as the randomization part of the wiretap code to keep the eavesdropper ignorant. In establishing the capacity region, a new upper bound on the sum-rate is derived. This bound shows that in an optimal coding scheme, in the degraded case, the total equivocation-rate of the (opposite) secret-keys at the legitimate receivers must equal the equivocation-rate of the secret-keys at the eavesdropper, when informed about the messages.

Research activities reveal a trend from an exclusive to a shared use of certain frequency bands. Then, uncoordinated interference will be unavoidable resulting in a channel that may vary in an arbitrary and unknown manner from channel use to channel use. This is the arbitrarily varying channel (AVC), for which it has been shown that the classical deterministic approaches with pre-specified encoder and decoder fail if the AVC is symmetrizable. This necessitates more sophisticated strategies such as common randomness (CR) assisted strategies or list decoding which are capable to resolve the ambiguity induced by symmetrizable AVCs. Here, we study the arbitrarily varying multiple access channel (AVMAC) with conferencing encoders, which is motivated by cooperating base stations or access points in future communication systems. The capacity region of the AVMAC with conferencing encoders is established and it is shown that list decoding allows for reliable communication also for symmetrizable AVMACs. The list capacity region equals the CR-assisted capacity region for large enough list size. Finally, for fixed probability of decoding error the amount of resources, i.e., CR or list size, is shown to be finite.

Strategic users in a wireless network cannot be assumed to follow the network algorithms blindly. Moreover, some of these users could be controlled by powerful Botnets, which aim to use their knowledge about network algorithms to maliciously gain more resources and also to create interference to other users. We consider a scenario; in which a mechanism designer and legitimate users together, in a wireless network, gather probabilistic information about the presence of malicious users and modify their actions accordingly. The probabilistic information is gathered by observing the network over a long time period. We study Bayesian mechanisms, both pricing schemes and auctions, and obtain the Nash Equilibrium (NE) points of the underlying Bayesian games. The NE points provide conditions indicating when it is better for users to to hide or reveal their nature (types). The prices and allocations in the mechanisms are later modified using the Bayesian information about the type of the users. The numerical studies show the NE points and illustrate the results.

The paradigm shift from an exclusive to a shared use of frequencies comes along with the necessity of new concepts since interference will be ubiquitous. Resulting channels may vary in an arbitrary and unknown manner from channel use to channel use. This is the arbitrarily varying channel (AVC). Here, coordination resources such as common randomness or correlated sources have been shown to be important for reliable communication; especially for symmetrizable AVCs where deterministic approaches with pre-specified encoder and decoder fail. Here, we study the arbitrarily varying bidirectional broadcast channel (AVBBC), which is motivated by the broadcast phase of bidirectional relaying. Here, a relay establishes a bidirectional communication between two nodes while sharing resources with other coexisting networks. The question is asked how much coordination is needed for reliable communication. The capacity region of the AVBBC is established and it is shown that for a transmission of block length n no more than O(log n) outputs of the correlated source suffices to achieve the same as with the much stronger resource of common randomness. Such weak coordination resources of correlated sources can easily be realized by broadcasting a signal (e.g. via satellite) observed by all users only as correlated versions.

We establish the Ahlswede Dichotomy for arbitrarily varying classical-quantum wiretap channels, i.e., either the deterministic secrecy capacity of an arbitrarily varying classical-quantum wiretap channel is zero, or it equals its randomness assisted secrecy capacity. We analyze the secrecy capacity of arbitrarily varying classical-quantum wiretap channels when the sender and the receiver use various resources. It turns out that having randomness, common randomness, and correlation as resources are very helpful for achieving a positive deterministic secrecy capacity of arbitrarily varying classical-quantum wiretap channels. We prove the phenomenon “super-activation” for arbitrarily varying classical-quantum wiretap channels, i.e., two arbitrarily varying classical-quantum wiretap channels, both with zero deterministic secrecy capacity, if used together allow perfect secure transmission.

We introduce one-way LOCC protocols for quantum state merging for compound sources, which have asymptotically optimal entanglement as well as classical communication resource costs. For the arbitrarily varying quantum source (AVQS) model, we determine the one-way entanglement distillation capacity, where we utilize the robustification and elimination techniques, well-known from classical as well as quantum channel coding under assumption of arbitrarily varying noise. Investigating quantum state merging for AVQS, we demonstrate by example, that the usual robustification procedure leads to suboptimal resource costs in this case.

We prove coding theorems for two scenarios of cooperating encoders for the multiple access channel with two classical inputs and one quantum output. In the first scenario (ccq-MAC with common message), the two senders each have their private messages, but would also like to transmit common messages. In the second scenario (ccq-MAC with conferencing encoders), each sender has its own set of messages, but they are allowed to use a limited amount of noiseless classical communication amongst each other prior to encoding their messages. This conferencing protocol may depend on each individual message they intend to send. The two scenarios are related to each other not only in spirit - the existence of a capacity-achieving construction scheme for codes for the ccq-MAC with common messages is used for proving the existence of another such scheme for the ccq-MAC with conferencing encoders.

We give an explicit example that answers the question whether the transmission of messages over arbitrarily varying quantum channels can benefit from distribution of randomness between the legitimate sender and receiver in the affirmative.

The wiretap channel models secure communication in the presence of an eavesdropper who must be kept ignorant of transmitted messages. In this paper, the arbitrarily varying wiretap channel (AVWC), in which the channel may vary in an unknown and arbitrary manner from channel use to channel use, is considered. For arbitrarily varying channels (AVCs) the capacity might differ depending on whether deterministic or common randomness (CR) assisted codes are used. The AVWC has been studied for both coding strategies and the relation between the corresponding secrecy capacities has been established. However, a characterization of the CR-assisted secrecy capacity itself or even a general CR-assisted achievable secrecy rate remain open in general for weak and strong secrecy. Here, the secrecy measure of high decoding error at the eavesdropper is considered, where the eavesdropper is further assumed to know channel states and to adapt its decoding strategy accordingly. For this secrecy measure a general CR-assisted achievable secrecy rate is established. The relation between secrecy capacities for different secrecy measures is discussed: The weak and strong secrecy capacities are smaller than or equal to the one for high decoding error. It is conjectured that this relation can be strict for certain channels.

We study the transmission of a common message and three confidential messages over a broadcast channel with two legitimate receivers and an eavesdropper. Each legitimate receiver is interested in decoding two of the three confidential messages, while having the third one as side information. In order to measure the ignorance of the eavesdropper about the confidential messages, we investigate two different secrecy criteria: joint secrecy and individual secrecy. For both criteria, we provide a general achievable rate region. We establish both the joint and individual secrecy capacity if the two legitimate receivers are less noisy than the eavesdropper. We further investigate the scenario where the eavesdropper is less noisy than the two legitimate receivers. It is known that the joint secrecy constraints can not be fulfilled under this scenario, however, we manage to establish a non vanishing capacity region for the individual secrecy case.

In this paper, we consider a multihop wireless network, where Femto Base Stations (FBSs) act as relay nodes, and are incentivized to carry traffic from a Macro Base Station (MBS) to Macro Users (MUs).We first examine the the global problem of jointly optimal allocation of traffic flow and transmission power in the multihop wireless network. We then examine a game in which selfish and strategic relays submit charging functions to the source and choose transmission powers over a MAC channel from the relays to the user. Relay charging functions are considered which yield efficient allocation at the Nash Equilibrium (NE) of the game. We observe that for efficiency, relays should be taxed for the interference it creates to other relays. We also observe that inefficient equilibria occur when the charging function is a function only of the traffic flow rate through the relay. Numerical studies demonstrate the variation of inefficiency with network structure.

We develop the noncooperative game with individual pricing for the general multiple access channel (MAC) system without successive interference cancellation (SIC). Each user allocates its own power by optimizing the individual utility function with clever price adaptation. We show that by the proposed prices, the best response (BR) power allocation of each user converges rapidly. The individual prices are proposed such that the Shannon rate-based quality-of-service (QoS) requirement of each user is achieved at the unique Nash equilibrium (NE) point. We analyse different behavior types of the users, especially the malicious behavior and the resulting NE power allocation and achievable rates of all the users with malicious users. We illustrate the convergence of the BR dynamic and the Price of Malice (PoM) by numerical simulations.

The broadcast channel with confidential messages (BCC) consists of one transmitter and two receivers, where the transmitter sends a common message to both receivers and, at the same time, a confidential message to one receiver which has to be kept secret from the other one. In this paper, this communication scenario is studied for compound channels, where it is only known to the transmitter and receivers that the actual channel realization is fixed and from a prespecified set of channels. The information theoretic criterion of strong secrecy is analyzed in detail and its impact on the decoding performance of the non-legitimate receiver is characterized. In particular, it is shown that regardless of the computational capabilities and the applied decoding strategy of the non-legitimate receiver, his decoding error always tends to one. This gives a valuable signal processing implication of the strong secrecy criterion and identifies desirable properties of an optimal code design. Further, an achievable strong secrecy rate region is derived and a multiletter outer bound is given. Both together yield a multiletter expression of the strong secrecy capacity region of the compound BCC.

In this paper, the discrete memoryless arbitrarily varying broadcast channel (AVBC) with receiver side information is studied and its random code and deterministic code capacity regions are derived for the average error criterion. In addition, it is analyzed for deterministic list codes and it is shown that the corresponding list capacity region displays a behavior, which is similar to Ahlswede's famous dichotomy result for the single-user arbitrarily varying channel: it either equals the random code capacity region or otherwise has an empty interior. This is characterized in terms of list sizes at the receivers and an appropriate concept of symmetrizability for the AVBC with receiver side information. The scenario studied here is motivated by the broadcast phase of bidirectional relaying, where a half-duplex relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol. The relay decodes the messages both nodes have sent in the initial multiple access phase and broadcasts a re-encoded composition of them in the succeeding broadcast phase. Then, the broadcast phase corresponds to the AVBC with receiver side information, which differs from the classical broadcast channel, since both receivers can exploit their own messages from the previous phase as side information for decoding.

Recently, a new constructive formula for the calculation of the Hilbert transform of bounded bandlimited signals was found. In this paper we use that formula to analyze the properties of the Hilbert transform. We further present a Fefferman-Stein-type decomposition theorem for bandlimited signals in BMO(R), i.e., bandlimited signals of bounded mean oscillation. Based on this decomposition we characterize the range of the Hilbert transform and derive properties of general bandlimited signals in BMO(R). We show the boundedness of bandpass signals in BMO(R) and the boundedness of the derivative of bandlimited signals in BMO(R). We further find the maximum growth of the Hilbert transform of bounded bandlimited signals.

The wiretap channel models the communication scenario where two legitimate users want to communicate in such a way that an external wiretapper is kept ignorant. In this paper, the wiretap channel with side information is studied, where the wiretapper has additional side information about the transmitted message available for post-processing. The secrecy of the message is modeled by the decoding performance of the wiretapper. It is required for the wiretapper to have worst behavior of decoding performance regardless of the decoding strategy that is used. The secrecy capacity is derived and shown to be equal to the one of the classical wiretap channel without side information available at the wiretapper. Further, the corresponding optimal transceiver design is characterized.

In this paper, a wireless sensor network is considered in which the objective is not to communicate individual sensor readings over a Gaussian multiple-access channel to a fusion center but rather to reliably compute some nomographic function thereof. Nomographic functions are exactly those multivariate functions that can be represented as a post-processed sum of pre-processed sensor readings. This special structure permits the utilization of the interference property of the Gaussian multiple-access channel for computing some nomographic functions at significantly higher rates than those achievable with traditional schemes. In this paper, a corresponding coding scheme is presented that protects the sum of pre-processed sensor readings against the channel noise by letting each node use the same nested lattice code.

This paper provides a quantitative notion of the sparsity for infinite dimensional atomic spaces, which play an important role in many signal processing applications. This notion of sparsity is defined as the ratio of the number of redundant samples (not necessary to recover any signal in the atomic space) to the number of all available samples of a particular canonical sampling system. It is shown that the so defined sparsity can be expressed in terms of the support of the spectral density of the sequence which generates the atomic space.

The wiretap channel models the communication scenario where two legitimate users want to communicate in such a way that an external wiretapper is kept ignorant. In this paper the wiretap channel with side information is studied, where the wiretapper has additional side information about the transmitted message available for decoding. The corresponding secrecy capacity is derived and shown to be equal to the one of the classical wiretap channel without side information available at the wiretapper. Further, the capacity-achieving code structure is analyzed and properties are identified. Finally, channel uncertainty is taken into account and the results are extended to the compound wiretap channel with side information.

As our main result we show that, in order to achieve the randomness assisted message - and entanglement transmission capacities of a finite arbitrarily varying quantum channel it is not necessary that sender and receiver share (asymptotically perfect) common randomness. Rather, it is sufficient that they each have access to an unlimited amount of uses of one part of a correlated bipartite source. This access might be restricted to an arbitrary small (nonzero) fraction per channel use, without changing the main result. We investigate the notion of common randomness. It turns out that this is a very costly resource - generically, it cannot be obtained just by local processing of a bipartite source. This result underlines the importance of our main result. Also, the asymptotic equivalence of the maximal- and average error criterion for classical message transmission over finite arbitrarily varying quantum channels is proven. At last, we prove a simplified symmetrizability condition for finite arbitrarily varying quantum channels.

Availability of channel state information, especially to non-legitimate users, is one major challenge for secure communication in wireless systems. For arbitrarily varying channels (AVC), coordination resources such as common randomness have been shown to be important for reliable communication; especially for symmetrizable AVCs. In this paper, the arbitrarily varying wiretap channel (AVWC) with active wiretapper is studied. Such an wiretapper may or may not exploit his knowledge about the coordination resources to control the channel conditions. Secrecy capacity results are derived for different forms of coordination resources including common randomness and correlated sources. Finally, it is demonstrated how two orthogonal AVWCs, each with zero secrecy capacity, i.e., useless for secure transmission, can be super-activated to a useful channel allowing for secure communication at non-zero secrecy rates.

If the senders and the receiver of an Arbitrarily Varying Multiple-Access Channel (AV-MAC) have access to the outputs of discrete correlated memoryless sources, the same rate region is achievable as if common randomness were available. This reduces the necessary amount of cooperation in an AV-MAC considerably. Moreover, to transmit blocklength-n words, no more than order log n source outputs are required.

High signal peak values are one of the fundamental obstacles to greater efficiency in wireless communications systems. There exist many techniques to reduce signal peak values; however, there have been few theoretical studies of the trade-off between reducing peak values and the resulting cost in other resources. Here we address the trade-off between peak reduction and information rates for two standard systems, OFDM and DS-CDMA, when implementing tone reservation. In particular, we show that when a peak threshold is strictly enforced regardless of the number of carriers, the information rate must tend to zero. We discuss aspects that these two systems share in common, as well as point out a fundamental way in which they differ.

The wiretap channel models the communication scenario where two legitimate users want to communicate in such a way that a wiretapper is kept ignorant. In this paper, the wiretap channel with side information is studied, where the wiretapper has additional side information available. This side information allows the wiretapper to restrict the transmitted message to a certain subset of messages before further postprocessing. Two different criteria are employed to model the secrecy of the confidential message: the information theoretic criterion of strong secrecy and a signal-processing-inspired criterion based on the decoding performance of the wiretapper. For the latter, the wiretapper is required to have the worst decoding performance regardless of the specific decoding strategy that is used. It is shown that both criteria are equivalent in terms of secrecy capacity. Furthermore, the secrecy capacity equals the one of the classical wiretap channel without side information available at the wiretapper. In addition, the corresponding capacity-achieving code structure and optimal transceiver design are characterized and properties are identified. Finally, extensions to channel uncertainty and multiple wiretappers are discussed.

The classical wiretap channel models secure communication in the presence of a nonlegitimate wiretapper who has to be kept ignorant. Traditionally, the wiretapper is passive in the sense that he only tries to eavesdrop the communication using his received channel output. In this paper, more powerful active wiretappers are studied. In addition to eavesdropping, these wiretappers are able to influence the communication conditions of all users by controlling the corresponding channel states. Since legitimate transmitters and receivers do not know the actual channel realization or the wiretapper's strategy of influencing the channel states, they are confronted with arbitrarily varying channel (AVC) conditions. The corresponding secure communication scenario is, therefore, given by the arbitrarily varying wiretap channel (AVWC). In the context of AVCs, common randomness (CR) has been shown to be an important resource for establishing reliable communication, in particular, if the AVC is symmetrizable. But availability of CR also affects the strategy space of an active wiretapper as he may or may not exploit the common randomness for selecting the channel states. Several secrecy capacity results are derived for the AVWC. In particular, the CR-assisted secrecy capacity of the AVWC with an active wiretapper exploiting CR is established and analyzed in detail. Finally, it is demonstrated for active wiretappers how two orthogonal AVWCs, each useless for transmission of secure messages, can be super-activated to a useful channel allowing for secure communication at nonzero secrecy rates. To the best of our knowledge, this is not possible for passive wiretappers and, further, provides the first example of such super-activation, which has been expected to appear only in the area of quantum communication. Such knowledge is particularly important as it provides valuable insights for the design and the medium access control of future wireless communication systems.

To increase the spectral efficiency of future wireless networks, it is important to wisely integrate multiple services at the physical layer. Here the efficient integration of confidential services in the three-node bidirectional relay channel is studied. A relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol, which is also known as two-way relaying. In the broadcast phase, the relay transmits not only the two bidirectional messages it received in the previous multiple access phase, but also an additional confidential message to one node while keeping the other node completely ignorant of it. The concept of strong information theoretic secrecy is used to ensure that the nonlegitimate node cannot decode the confidential message no matter what its computational resources are. Moreover, this implies that the average decoding error at the nonlegitimate node goes exponentially fast to one for any decoding strategy it may use. This results in the study of the bidirectional broadcast channel with confidential messages for which the strong secrecy capacity region is established. Furthermore, it is shown that the efficient integration of confidential messages with strong secrecy extends to such scenarios, where the relay further transmits an additional common message to both nodes.

We derive the capacity region of arbitrarily varying multiple-access channels (AV-MACs) with conferencing encoders for both deterministic and random coding. For a complete description, it is sufficient that one conferencing capacity is positive. We obtain a dichotomy: either the channel's deterministic capacity region is zero or it equals the 2-D random coding region. We determine exactly when either case holds. We also discuss the benefits of conferencing. We give the example of an AV-MAC which does not achieve any nonzero rate pair without encoder cooperation, but the 2-D random coding capacity region if conferencing is possible. Unlike compound multiple-access channels, arbitrarily varying multiple-access channels may exhibit a discontinuous increase of the capacity region when conferencing in at least one direction is enabled.

It is well known that Max-Weight type scheduling algorithms are throughput optimal since they achieve the maximum throughput while maintaining the network stability. However, the majority of existing works employing Max-Weight algorithm require the complete channel state information (CSI) at the scheduler without taking into account the associated overhead. In this work, we design a Scheduling and Selective Feedback algorithm (SSF) taking into account the overhead due to acquisition of CSI. SSF algorithm collects CSI from only those users with sufficiently good channel quality so that it always schedules the user with the highest queue backlog and channel rate product at every slot. We characterize the achievable rate region of SSF algorithm by showing that SSF supports 1 + ϵ fraction of the rate region when CSI from all users are collected. We also show that the value of ϵ depends on the expected number of users which do not send back their CSI to the base station. For homogenous and heterogeneous channel conditions, we determine the minimum number of users that must be present in the network so that the rate region is expanded, i.e., ϵ > 0. We also demonstrate numerically in a realistic simulation setting that this rate region can be achieved by collecting CSI from only less than 50% of all users in a CDMA based cellular network utilizing high data rate (HDR) protocol.

The Hilbert transform is an important operator in signal processing, e.g., the definition of the “analytical signal” uses the Hilbert transform. In this paper we analyze the Hilbert transform for bounded bandlimited signals in B∞π. Although the common integral representation of the Hilbert transform may diverge for certain signals in B∞π, it is possible to define the Hilbert transform meaningfully for bounded signals. We employ a definition that is based on the H1-BMO(ℝ) duality. The problem of this abstract definition is that there exists no constructive procedure to calculate the Hilbert transform. However, for the subspace of bounded bandlimited signals, we can give an explicit formula for the calculation of the Hilbert transform. Further, we show that the Hilbert transform of a bounded bandlimited signal is still bandlimited but not necessarily bounded.

Recently, it has been shown that the superposition property of wireless multiple-access channels can be exploited to compute functions in sensor networks much more efficiently. By using appropriate pre- and post-processing functions operating on real sensor readings and the superimposed signal received by a fusion center, every function of the measurements is in principle computable by means of the wireless channel in which the pre-processing functions, and therefore the transmitting nodes, do not depend on the function of interest. In this paper we extend these general considerations by examining how robust this kind of universality is against variations in network topology due to nodes that drop out of the network or due to new nodes that connect to the network.

Given a U-invariant sampling scheme on an arbitrary Hilbert space ℋ. This paper characterizes atomic subspaces A of ℋ such that every signal x ∈ A can be reconstructed from its samples acquired with this sampling scheme. If signal recovery is possible a linear filter is derived which reconstructs the signal from the samples.

We derive a rate region which is achievable by the Wiretap MAC with Common Message under the strong secrecy criterion. We follow Devetak's approach to establishing strong secrecy. Using the concentration of the normed sum of bounded i.i.d. random variables around its mean, it is possible to show the existence of a code where the channel outputs at the eavesdropper are almost independent of the messages. The encoders may use a certain amount of common randomness. We give the example of a channel where the availability of common randomness is necessary for secret transmission.

In this paper the compound broadcast channel with confidential messages is studied, where it is only known to the transmitter and receivers that the actual channel realization is fixed and from a pre-specified set of channels. An achievable rate region for the strong secrecy criterion is derived. Further, a multi-letter outer bound is given, which establishes, together with the achievable rate region, a multi-letter expression of the strong secrecy capacity region.

In this work the arbitrarily varying wiretap channel AVWC under the average error criterion and the strong secrecy criterion is studied. We show that in the case of a non-symmetrisable channel to the legitimate receiver the deterministic code secrecy capacity equals the random code secrecy capacity and thus we establish a result for the AVWC similar to that of Ahlswede's dichotomy for ordinary AVCs. We derive a lower bound on the random code secrecy capacity in the case of a best channel to the eavesdropper. We further prove upper bounds on the deterministic code secrecy capacity, which in special cases results in explicit expressions of the secrecy capacity.

It is well known that Max-Weight scheduling provides queue stability whenever this is possible. However, Max-Weight scheduling requires the complete channel state information (CSI) to make the best transmission decision at every time slot. The common assumption in this line of research assumes that the network controller has full CSI at every decision time without taking into account the overhead associated with channel probing. In practice, however, acquiring CSI is not cost-free and requires certain amount of resources. In this work, we design a Scheduling and Dynamic Feedback algorithm, named SDF, by considering the overhead of obtaining the channel state information. We first establish a bound on the achievable rate region of SDF algorithm by proving that SDF supports 1+ ϵ fraction of of the full rate region (the rate region when all users are probed) where ϵ only depends on the expected number of users which are not probed. Then, for homogenous channel, we show that when the number of users in the network is greater than 3, ϵ >;0, i.e., we guarantee to expand the rate region. We also demonstrate numerically in a realistic simulation setting that this rate region can be achieved by probing only less than 50% of all channels in a CDMA based cellular network utilizing high data rate protocol under normal channel conditions.

In this work, the bidirectional broadcast channel (BBC) with confidential messages is studied. The problem is motivated by the concept of bidirectional relaying in a three-node network, where a half-duplex relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol and thereby transmits additional confidential information to one of them in the broadcast phase. The corresponding confidential message is transmitted at a certain secrecy level which characterizes the amount of information that can be kept secret from the non-legitimate node. The capacity-equivocation and secrecy capacity regions of the BBC with confidential messages are established where the latter characterizes the communication scenario with perfect secrecy, which means that the confidential information is completely hidden from the non-legitimate node. Thereby, it is shown that the optimal processing exploits ideas and concepts of the BBC with common messages and of the classical broadcast channel with confidential messages.

In order to increase spectral efficiency, it is becoming more and more important that next generation wireless networks wisely integrate multiple services such as transmissions of private, common, and confidential messages at the physical layer. This is referred to as physical layer service integration, and in this paper is being studied for bidirectional relay networks. Here, a relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol. This is also known as two-way relaying. In the broadcast phase, the relay efficiently integrates additional common and confidential services at the physical layer, which then requires the study of the bidirectional broadcast channel (BBC) with common and confidential messages. The entire secrecy capacity regions for discrete memoryless and MIMO Gaussian channels are established. These results further unify previous partial results such as the BBC with common messages or the classical broadcast channel with common and confidential messages, where the relay node provides only some of the services.

In this paper we analyze the reconstruction of bandlimited signals from their sine wave crossings by a sampling type reconstruction process. The reconstruction process is highly adapted to the signal which shall be reconstructed, because the reconstruction functions and the sampling points are implicitly generated by the signal. We show that the reconstruction process is uniformly convergent for all signals in the Paley-Wiener spaces VWπP, 1π1.

We consider spatio-temporal Tomlinson Harashima Precoding where the feedforward filter is located at the transmitter and an additional scalar gain is employed as receive filter. In contrast to other works, we allow channel, feedforward, and feedbackward filters to have one-sided but infinite impulse responses. The optimal filters with respect to a minimum mean square error criterion are derived. We elaborate several interesting properties of our solution and discuss a fast implementation with only quadratic complexity in the latency time.

We consider the design of linear precoding filters with respect to the minimum mean square error (MMSE) criterion for systems that employ an additional scalar gain next to a fixed receive filter. The precoding filter and the scalar gain are to be jointly optimized. Currently, only the finite impulse response (FIR) solution to this problem is known. The goal of this paper is to derive the infinite impulse response (IIR) MMSE precoder both with and without causality constraint, i.e., finite and infinite latency time, respectively. We discuss the role of the scalar gain and its relationship to automatic gain control (AGC). We also show that causal precoding requires that the joint first arrival delay of channel and receive filter is not larger than the latency time, and that the IIR-MMSE precoder enjoys the same advantages over the FIR-MMSE precoder as the IIR-MMSE equalizer does over the FIR-MMSE equalizer, viz.: improved performance and no need for latency time optimization.

We present several results that show, according to several criteria, that the large peaks that occur in OFDM are common to all orthonormal systems that are uniformly bounded. In particular, worst case peak-to-average values are always at least the square-root of the number of signals, and the expected peak value of a signal always increases logarithmically with the number of signals. The same growth also occurs for single-user signals with the appropriate normalization. Further, we investigate peak-to-average power properties of the prolate spheroidal wave functions and the Walsh functions, which are used in DS-CDMA.

We present a method for automatically optimized selection and composition of algorithm components for iterative MIMO-OFDM receivers. Complexity is measured as clock cycles of the target processor cores (suitable for software defined radio based implementation). A receiver description language is used to specify the design space, and to enable enumeration of the design space using graph algorithms. Performance prediction of a composition of candidate algorithms uses a recently published method from stochastic convergence analysis of iterative processing. We illustrate the method in an example scenario, where the optimized receivers show both an extended operational SNR range compared to the standard receiver architecture, as well as significantly reduced complexity compared to iterative processing according to round-robin iteration scheduling using the same algorithm components.

We consider quantum state merging under uncertainty of the state held by the merging parties. More precisely we determine the optimal entanglement rate of a merging process when the state is unknown up to membership in a certain set of states. We find that merging is possible at the lowest rate allowed by the individual states.

We characterize the capacity region of the arbitrarily varying multiple-access channel with conferencing encoders. This channel exhibits a dichotomy: either it is useless or its capacity region equals the region achievable with random coding. We determine exactly when either case holds. This model can be used to analyze downlink networks with cooperating base stations suffering from exterior interference.

Recent research developments show that the concept of bidirectional relaying significantly improves the performance in wireless networks. This applies to three-node networks, where a half-duplex relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol. In this work we consider the scenario when in the broadcast phase the relay transmits additional confidential information to one node, which should be kept as secret as possible from the other, non-intended node. This is the bidirectional broadcast channel with confidential messages for which we derive the capacity-equivocation region and the secrecy capacity region. The latter characterizes the communication scenario with perfect secrecy, where the confidential message is completely hidden from the non-legitimated node.

We derive a lower bound on the secrecy capacity of the compound wiretap channel with channel state information at the transmitter which matches the general upper bound on the secrecy capacity of general compound wiretap channels given by Liang et al. and thus establishing a full coding theorem in this case. We achieve this with a quite strong secrecy criterion and with a decoder that is robust against the effect of randomisation in the encoding. This relieves us from the need of decoding the randomisation parameter which is in general not possible within this model. Moreover we prove a lower bound and a multi-letter converse to the secrecy capacity of the compound wiretap channel without channel state information.

In this work, we study the bidirectional broadcast channel with common and confidential messages and establish the capacity-equivocation and secrecy capacity regions. This problem is motivated by the concept of bidirectional relaying in a three-node network, where a relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol and thereby efficiently integrates additional common and confidential services.

For joint MIMO-OFDMA link adaptation and scheduling, channel quality feedback needs to be quantized, sparse and irregular. For flexible scheduling, prediction of the quantized channel at the base-station is needed. We propose measurement of 3D channel correlation parameters by the terminals and signalling back to the base station, which enables prediction of the quantized channel by multi-dimensional Wiener filtering. The scheme is shown to improve adaptive choice of transmission parameters and to avoid mis-adaptation due to control lag. Different schemes of correlation feedback signalling are discussed in terms of (time-variant) expected throughput.

We provide a combinatorial characterization of interference coupling in wireless systems, with the intent of obtaining a better insight into interference coordination and management. We introduce two bipartite graphs, namely the power graph and interference graph. We utilize these graphs and global dependency matrix containing only binary (0 and 1) entries to capture the effects of interference coupling in communication systems. We show that the irreducibility of the global dependency matrix G is related to the connectivity of the power graph and the irreducibility of the matrix GGTis related to the connectivity of the interference graph. We prove that for strictly positive and strictly log-convex interference functions, the irreducibility of the matrices G and GGTare necessary and sufficient conditions for the considered utility sets to be strictly convex. In this case there exists a unique optimizer for the problem of maximizing the product of utilities. We show that an interference balancing function is strictly log-convex, if and only if matrices G and GGTare irreducible. We provide a simple yet comprehensive combinatorial characterization of interference coupled systems which abstracts away certain complexities of the physical layer.

Many solutions and concepts in resource allocation and game theory rely on the assumption of a convex utility set. In this paper, we show that the less restrictive assumption of a logarithmic “hidden” convexity is sometimes sufficient. We consider the problems of Nash bargaining and proportional fairness, which are closely related. We extend the Nash bargaining framework to a broader family of log-convex sets. We then focus on the set of feasible signal-to-interference-plus-noise ratios (SINRs), for the cases of individual power constraints and a sum power constraint. Under the assumption of log-convex interference functions, we show how Pareto optimality of boundary points depends on the interference coupling between the users. Finally, we provide necessary and sufficient conditions for strict log-convexity of the feasible SINR region.

The goal of this paper is to provide a rigorous information-theoretic analysis of subnetworks of interference networks. We prove two coding theorems for the compound multiple-access channel (MAC) with an arbitrary number of channel states. The channel state information at the transmitters is such that each transmitter has a finite partition of the set of states and knows which element of the partition the actual state belongs to. The receiver may have arbitrary channel state information. The first coding theorem is for the case that both transmitters have a common message and that each has an additional private message. The second coding theorem is for the case where rate-constrained, but noiseless transmitter cooperation is possible. This cooperation may be used to exchange information about channel state information as well as the messages to be transmitted. The cooperation protocol used here generalizes Willems' conferencing. We show how this models base station cooperation in modern wireless cellular networks used for interference coordination and capacity enhancement. In particular, the coding theorem for the cooperative case shows how much cooperation is necessary in order to achieve maximal capacity in the network considered.

Pareto optimality is an important property in game theory and mechanism design, which can be utilized to design resource allocation strategies in wireless systems. We analyze the structure of the boundary points of certain utility sets based on interference functions. We particularly investigate the cases with no power constraints, with individual power constraints, and with a total power constraint. We display the dependency between Pareto optimality and interference coupling in wireless systems. An axiomatic framework of interference functions and a global dependency matrix is used to characterize interference coupling in wireless systems. The relationship between interference-balancing functions and Pareto optimality of the boundary points is elucidated. Among other results, it is shown that the boundary points of utility sets with individual power constraints and with strictly monotonic interference functions are Pareto-optimal if and only if the corresponding restricted global dependency matrix is irreducible. The obtained results provide certain insight when suitable algorithms can be designed for network utility maximization.

In this work, the MIMO Gaussian bidirectional broadcast channel (BBC) with common messages is studied. The problem is motivated by the concept of bidirectional relaying in a three-node network, where a half-duplex relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol and thereby adds an own multicast message to the communication. The capacity region of the broadcast phase is derived and the corresponding transmit covariance matrix optimization problem is analyzed in detail. Thereby, it is shown that the transmit covariance optimization problem is strongly connected to the corresponding one of the MIMO Gaussian BBC without common messages. In particular, this knowledge can be exploited to transfer results such as optimal transmit strategies from one scenario to the other one.

In this work, we study the MIMO Gaussian bidirectional broadcast channel (BBC) with common message and characterize the capacity region. Moreover, we show that the transmit covariance matrix optimization problem has the same structure as the corresponding optimization problem of the BBC without common message which leads to the comfortable position to transfer results from one scenario to the other. This problem is motivated by the concept of bidirectional relaying in a three-node network, where a half-duplex relay node establishes a bidirectional communication between two other nodes and thereby adds an own multicast message to the communication.

In this paper we analyze band-pass type systems that operate on bounded bandlimited signals. For a very general class of band-pass type systems, we prove that there exists no linear realization of the systems in this class. Since ideal band-pass type systems are included in this class, it follows that there exists no linear realization of ideal band-pass type systems. This result is obtained under very general assumptions. For example, we do not assume the systems to be time-invariance. Finally, it is shown that a non-linear realization of band-pass type systems is possible.

The paper characterizes the class of all concave resource allocation problems in interference coupled wireless systems. An axiomatic framework for interference functions proposed by Yates in 1995 is used to model interference coupling in our paper. The paper shows that there exists no transformation, which ensures concavity for all linear interference functions for all functions of SINR. The paper then characterizes the largest class of utility functions under a certain requirement, such that the corresponding class of utility functions functions, which are a function of SINR in the s-domain are concave. The paper shows that such a class of utility functions is a restricted class due to a requirement, which ensures concavity. Furthermore, the paper shows that the largest class of interference functions, which ensures concavity for resource allocation problems are the log-convex interference functions. These results differ from the convex case, where we are interested in minimizing utility functions of inverse SINR.

In this paper we analyze the convergence behavior of convolution-type system representations for the Paley-Wiener space PWπ1. We completely characterize all stable linear time-invariant (LTI) systems for which we have convergence in the distributional sense by giving a necessary and sufficient condition for convergence. Furthermore, we prove that there are stable LTI systems and signals in PWπ1for which the convolution integral and the convolution sum diverge even in a distributional sense. In signal processing, distributions are often used to show convergence. Surprisingly, here we are in a situation where distributions cannot be used to justify convergence.

Realizable DFEs are DFEs with stable and causal IIR filters and finite decision delay. Computational complexity of current algorithms to compute them usually grows cubically with the decision delay. In this paper, we show how complexity can be reduced to quadratic. We compare two approaches, the so-called polynomial approach and a novel state-space approach using inner-outer factorization. In both cases finite linear equation systems with structure lie at the heart of the realizable DFE. Displacement structure theory allows to solve them efficiently.

We derive a sufficient condition for a square FIR MIMO system to have a causal and stable IIR inverse. The condition requires that the spectral norm of the normalized channel impulse response (i.e., the first tap is the identity matrix) is below a certain bound. Intuitively, this means that the system has a strong first tap. This condition often is easier to check than the usual minimum-phaseness, where the roots of the systems determinant have to be computed. Simple approximations of the bound are found. Furthermore, we also give a negative result: the Wiener Filter, which approximates the inverse under low noise conditions, nevertheless always is non-causal. We apply our results to two inversion problems with causality and stability constraint. These problems arise in oversampled noise-shaping subband coding and residual interference cancellation in precoded systems, respectively.

The concept of bidirectional relaying is a key technique to improve the performance in wireless networks such as sensor, ad-hoc, and even cellular systems. It applies to three-node networks, where a relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol. We assume that the communication is disturbed by unknown varying interference and analyze the impact of the degree of coordination. We show that the unknown variation of the interference has a dramatic impact on the communication. For traditional interference coordination it can lead to channels which completely prohibit any reliable communication. Anyhow, by allowing a relay-to-receivers coordination, communication can also be established in such situations where the traditional approach fails.

This paper investigates the possibility of having convex formulations of optimization problems for interference coupled wireless systems. An axiomatic framework for interference functions proposed by Yates in 1995 is used to model interference coupling in our paper. The paper shows, that under certain very natural assumptions -- the exponential mapping is the unique transformation (up to a constant), for ``convexification'' of resource allocation problems for linear interference functions. The paper shows that it is sufficient to check for the joint convexity of the sum of weighted utility functions of inverse signal-to-interference (plus noise)-ratio, if we would like the resulting resource allocation problem to be convex. The paper characterizes the largest class of interference functions, which allow a convex formulation of a problem for interference coupled wireless systems. It extends previous literature on log--convex interference functions and provides boundaries on the class of problems in wireless systems, which are jointly convex and hence can be efficiently solved at least from a numerical perspective.

This paper studies the properties of Nash equilibrium for noncooperative games in interference coupled wireless systems, where it serves as an incentive-compatible solution concept and an operating point. A broad class of noncooperative power control games played among the users of the wireless system is defined based on a general interference function framework, which models the interference coupling through a set of axioms. Both cases of coupling with and without self-interference are considered. The special properties of the underlying interference functions as well as relevant sufficient conditions are investigated to establish the existence and uniqueness of a Nash equilibrium solution. These properties play an important role in developing incentive-compatible distributed algorithms for a variety of wireless networks with interference coupling.

The concept of bidirectional relaying shows the potential to improve the performance in wireless networks such as sensor, ad-hoc, and even cellular systems. It applies to three-node networks, where a relay node establishes a bidirectional communication between two other nodes. In the first phase of a decode-and-forward protocol, the two nodes transmit their messages to a relay node, which decodes them. In the succeeding bidirectional broadcast phase, the relay broadcasts a re-encoded composition of them so that both nodes can decode the other's message using their own message as side information. We assume that the transmission is affected by unknown varying channels. Unfortunately, the unknown variation of the channel can lead to channels which completely prohibit any reliable communication. In this work, we analyze the bidirectional broadcast phase under list decoding and show that this decoding technique can improve the performance significantly in the sense that it allows to transmit reliably in scenarios where usual decoding schemes fail.

This paper investigates the properties of social choice functions that represent resource allocation strategies in interference coupled wireless systems. The allocated resources can be physical layer parameters such as power vectors or antenna weights. Strategy proofness and efficiency of social choice functions are used to capture the respective properties of resource allocation strategy outcomes being non-manipulable and Pareto optimal. In addition, this paper introduces and investigates the concepts of (strict) intuitive fairness and non-participation in interference coupled systems. The analysis indicates certain inherent limitations when designing strategy proof and efficient resource allocation strategies, if the intuitive fairness and non-participation are imposed. These restrictions are investigated in an analytical social choice function framework for interference coupled wireless systems. Among other results, it is shown that a strategy proof and efficient resource allocation strategy for interference coupled wireless systems cannot simultaneously satisfy continuity and the frequently encountered property of non-participation.

We derive a regularized formula for the common randomness assisted entanglement transmission capacity of finite arbitrarily varying quantum channels (AVQC's). For finite AVQC's with positive capacity for classical message transmission we show, by derandomization through classical forward communication, that the random capacity for entanglement transmission equals the deterministic capacity for entanglement transmission. This is a quantum version of the famous Ahlswede dichotomy. In the infinite case, we derive a similar result for certain classes of AVQC's. At last, we give two possible definitions of symmetrizability of an AVQC.

We consider the performance of tone reservation for reduction of the Peak-to-Average Power Ratio (PAPR) in OFDM signals. Tone reservation is unique among methods for reducing PAPR because it does not affect information bearing coefficients and involves no additional coordination of transmitter and receiver. It is shown that if the OFDM system always satisfies a given peak-to-average power ratio constraint, then the efficiency of the system, defined as the ratio of the number of tones used for information to the entire number of tones used, must converge to zero as the total number of tones increases.

We characterize the capacity region of the compound Discrete Memoryless Multiple Access Channel, where both transmitters have an additional common message. The channel state information is as follows: for each transmitter, there is a finite partition of the set of channels. Each transmitter knows which element of his partition the channel actually used belongs to. The capacity region is not affected by the amount of channel state information at the receiver, which may be arbitrary.

The concept of bidirectional relaying is a key technique to improve the performance in future wireless networks. It applies to three-node networks, where a relay node establishes a bidirectional communication between two other nodes using a decode-and-forward protocol. It divides the whole communication into two phases, namely the multiple access and bidirectional broadcast phase. Here, we concentrate on the second phase, which is also known as the bidirectional broadcast channel, and assume that the transmission is affected by arbitrarily varying channels. We impose constraints on the permissible input and state sequences and derive the capacity regions for random and deterministic coding.

The paper revisits the problem of proportional fairness in interference coupled wireless systems. It models interference coupling in wireless systems based on an interference function framework through a set of axioms (introduced by Yates in 1995). It utilizes the collective choice function to represent resource allocation strategies and an axiomatic framework to emulate certain desirable properties of resource allocation strategies. We introduce the axiom of equal priority in the power domain (and in the interference domain) and motivate it as interference coordination fairness. We consider this as an anonymity among the users, from the perspective of a central controller, e.g. a base station or an operator. We show that the proportional fair resource allocation strategy is anonymous to the identity of the users at the signal processing layer. Such an anonymity is relevant to obtain interference coordination fairness in iterative resource allocation strategies frequently encountered in wireless systems.

Bidirectional relaying is a promising approach to improve the performance in wireless networks such as sensor, ad-hoc, and even cellular systems. Bidirectional relaying applies to three-node networks, where a relay establishes a bidirectional communication between two other nodes using a decode-and-forward protocol. First, the two nodes transmit their messages to the relay which decodes them. Then, the relay broadcasts a reencoded message in such a way that both nodes can decode their intended message using their own message as side information. We consider uncertainty in the channel state information (CSI) and assume that all nodes only know that the channel over which the transmission takes place is from a pre-specified set of channels. In this work, we concentrate on the second phase, which is called the compound bidirectional broadcast channel. We present a robust coding strategy which enables reliable communication under channel uncertainty and show that this strategy actually achieves the compound capacity. Further, we analyze scenarios where either the receivers or the transmitter have perfect CSI. We show that CSI at the receivers does not affect the maximal achievable rates, while CSI at the transmitter improves the capacity region. A numerical example and a game-theoretic interpretation complete this work.

The process of quantization generates a loss of information, and, thus, the original signal cannot be reconstructed exactly from the quantized samples in general. However, it is desirable to keep the error as small as possible. In this paper, the quantization error is quantified in terms of several distortion measures. All these measures employ the difference between the original signal and the reconstructed signal, which is obtained by bandlimited interpolation of the quantized samples. We assume that the signals are bandlimited and that the samples are taken at Nyquist rate. It is shown that for signals in the Paley-Wiener spacePW¿1, the supremum of the reconstructed signal, and, hence, the quantization error cannot be bounded in the sense that there exists a bounded subset ofPW¿1on which both quantities can increase unboundedly. This unexpected behavior is due to the nonlinearity of the quantization operator and the slow decay of the sinc function. The nonlinearity is essential for this behavior because every linear operator that fulfills a certain property of the quantization operator would otherwise have to be bounded. Furthermore, it is proven that for a fixed signal the possible quantization error increases as the quantization step size tends to zero. The treatment of the quantization error in this paper is completely deterministic.

The convergence behavior of a convolution representation of stable linear time-invariant (LTI) systems operating on the Zakai class of bandlimited signals is analyzed. It is shown that there are signals in the Zakai class for which the convolution integral diverges if the system is the Hilbert transform or the ideal low-pass filter with bandwidth less than or equal to the signal bandwidth. Moreover, using a previously obtained result of Habib, it is proved that the class of stable LTI systems that map the Zakai class into itself does not include the Hilbert transform and the ideal low-pass filter with bandwidth less than or equal to the signal bandwidth. Finally, it is shown that the concept of the analytical signal, which is used in communications, is problematic for the signal spaceZπ, because the operator for its computation is unbounded and discontinuous.

In this paper, the convergence behavior of the symmetric and the nonsymmetric Shannon sampling series is analyzed for bandlimited continuous-time wide-sense stationary stochastic processes that have absolutely continuous spectral measure. It is shown that the nonsymmetric sampling series converges in the mean-square sense uniformly on compact subsets of the real axis if and only if the power spectral density of the process fulfills a certain integrability condition. Moreover, if this condition is not fulfilled, then the pointwise mean-square approximation error of the nonsymmetric sampling series and the supremum of the mean-square approximation error over the real axis of the symmetric sampling series both diverge. This shows that there is a significant difference between the convergence behavior of the symmetric and the nonsymmetric sampling series.

Power management and energy-aware communications systems have become increasingly important in mobile computing as well as mobile communications. In future wireless communication systems, the energy efficiency of terminals and base stations has to be improved significantly. Therefore, we propose a new utility function, which is the difference of the capacity and a weighted power cost term. The generally used individual power constraint is removed. Next, the utility region for single-antenna and multi-antenna multiple access channels is characterized. We show using basic principles that the single-input single-output (SISO) multiple-access channel (MAC) utility region is convex and provide a closed form expression for its Pareto boundary. We need the Pareto boundary to compute efficient operating points. Furthermore, the extension to multiple antenna channels is indicated by an iterative algorithm for weighted sum utility maximization in multiple-input single-output (MISO) and multiple-input multiple-output (MIMO) MAC. All discussed results are illustrated by numerical simulations.

In interference coupled wireless systems, where it is not possible to "orthogonalize" all the users in the system, we characterize the impact of interference coupling on the convexity of certain utility functions and problems. We introduce a general class of competitive user utility functions and natural competitive user utility functions. We further introduce the signal-to-interference based utility functions, which are based on physical layer parameters in wireless systems. We prove the conditions, which when satisfied result in a competitive user utility function being a signal-to-interference ratio based utility function. We further show that there exists no natural competitive user utility function, which is convex or concave. Furthermore, we show that a sum of weighted combination of natural competitive user utility functions is not convex or concave. Such functions are commonly encountered in wireless communication systems, e.g. rate or MMSE as a function of signal-to-interference ratio. We show that such rate maximization or MMSE minimization problems are not convex programs under our specified conditions.

In classical non-iterative MIMO detection a soft-output MIMO detector computes likelihoods of the transmit bits being 1 or 0, given the received symbol vector. In iterative MIMO detection-decoding, detection performance is improved by exploiting apriori information about bit probabilities from the decoder. Transmit bits are viewed as random variables and the optimum detector performs Bayesian updating of transmit bit probabilities to compute the aposteriori probabilities (APP). We show that with growing apriori knowledge APP and max-log-APP MIMO detector performance increases up to the performance of maximum ratio combining (MRC) for SIMO transmission of BPSK modulation, when transmitting with the same energy per symbol. This is an upper bound for detector performance in iterative detection-decoding (turbo MIMO receiver).

In this work we study optimal coding strategies for bidirectional relaying under the condition of arbitrarily varying channels. We consider a three-node network where a relay node establishes a bidirectional communication between two nodes using a spectrally efficient decode-and-forward protocol. In the first phase the two nodes transmit their messages to the relay node, which decodes them. In the succeeding bidirectional broadcast phase the relay node broadcasts an optimal re-encoded composition of them so that both nodes can decode the intended message using their own message as side information. We assume that the whole communication is affected by channels which vary in an unknown and arbitrary manner during the transmission so that all nodes have only imperfect channel state information. For both phases of the bidirectional relaying protocol we present robust coding strategies, which mitigate the uncertainty in channel state information so that reliable communication can be guaranteed. Further, we characterize the corresponding capacity regions for random and deterministic coding strategies.

In this paper we analyze the local and global convergence behavior of sampling series with non-equidistant sampling points for the Paley-Wiener space PWpi1and sampling patterns that are made of the zeros of sine-type functions. It is proven that the sampling series are locally uniformly convergent if no oversampling is used and globally uniformly convergent if oversampling is used. Furthermore, we show that oversampling is indeed necessary for global uniform convergence, because for every sampling pattern there exists a signal such that the peak value of the approximation error grows arbitrarily large if no oversampling is used. Finally, we use these findings to obtain similar results for the mean-square convergence behavior of sampling series for bandlimited wide-sense stationary stochastic processes.

In this paper we analyze the structure of certain power-constrained utility sets, based on the axiomatic framework of log-convex interference functions. Log-convex interference functions contain convex and linear interference functions as a special case. We analyze the boundary of the set. It is shown how Pareto optimality of boundary points depends on the interference coupling between the users. Finally, we investigate feasible sets of signal-to-interference-plus-noise ratios for individual power constraints and a sum power constraint. We show certain properties that are desirable, e.g. in the context of cooperative game theory.

We consider realizable linear and decision feedback equalization (DFE) of frequency selective multiple-input multiple-output (MIMO) channels in the presence of cochannel interference (CCI). Equalizers that are optimal in the minimum mean square error (MMSE) sense are derived with and without zero forcing (ZF) constraint. It is shown that all problems can be reduced to H2optimal deconvolution, for which a novel algorithm is presented.

The paper addresses the problem of interference modeling for wireless networks. Two axiomatic frameworks are known from the literature: (1) standard interference functions introduced by Yates in [JSAC 1995], and (2) general interference functions proposed by the authors in their previous work. In this paper, both frameworks are analyzed and compared. It is shown that (1) is contained in the more general framework (2). This means that certain structure results, which were recently derived for (2) can also be applied to (1). A focus of this paper is on convexity and concavity properties, which are important because they often lead to interesting algorithmic opportunities. The results provide a bridge between both frameworks, which have been studied separately in the past.

Power management and energy-awareness has become popular in mobile computing as well as mobile communications. In future wireless communication systems, the energy efficiency of terminals and base stations has to be improved. Therefore, we propose a new utility function which is the difference of the capacity and a weighted power cost term. Next, the utility region for single-antenna and multi-antenna multiple access channels is characterized. We show that the SISO MAC utility region is convex and provide a closed form expression for the Pareto boundary. We need the Pareto boundary to compute efficient operating points. Furthermore, an iterative algorithm is developed for weighted sum utility maximization in MISO and MIMO MAC. All results are illustrated in discussed by numerical simulations.

In this work the transmit covariance matrix optimization problem for the MIMO Gaussian bidirectional broadcast channel is studied. A half-duplex relay node establishes bidirectional communication between two nodes using a decode-and-forward protocol. In the initial multiple access phase both nodes transmit their messages to the relay node. In the succeeding phase the relay broadcasts an optimal re-encoded message so that both nodes can decode the other's message using their own message as side information. We show that if the channels are orthogonal then there exist equivalent transmit strategies with different ranks. The study of special cases reveals some of the difficult structure of the optimal solution. In particular a closed form procedure for the case of full rank transmission for invertible channels is derived. Moreover, for parallel channels the optimal solution is completely characterized and discussed.

We consider the broadcast phase of a spectrally efficient two-phase decode-and-forward protocol which is used by a relay node to establish a bidirectional communication between two nodes. In the first phase the two nodes transmit their message to the relay node which decodes the messages. In the succeeding phase the relay node broadcasts a re-encoded composition of them. We consider imperfect channel knowledge and assume that all nodes merely know that the channel used for the transmission belongs to a set of channels. This is called compound bidirectional broadcast channel. We derive a universal strategy which achieves capacity and show that perfect channel state information (CSI) at the receivers does not lead to an increased capacity region. Otherwise, perfect CSI at the transmitter can advantageously be used to enlarge the capacity region. Finally, we give a game-theoretic interpretation as a game against nature.

We determine the optimal achievable rate at which entanglement can be reliably transmitted when the memoryless channel used during transmission is unknown both to sender and receiver. To be more precise, we assume that both of them only know that the channel belongs to a given set of channels. Thus, they have to use encoding and decoding schemes that work well for the whole set.

We consider a downlink wireless system with a multi-antenna base station (BS) and single-antenna users. The error in the channel knowledge at the BS is assumed to have Gaussian distribution. Power allocation strategies are designed in order to satisfy the users' quality-of-service targets with certain probabilities. Conservative solutions of the problems are found by applying the Vysochanskii–Petunin inequality in combination with the theory of interference functions. Significant performance improvements are obtained comparing with methods based on the worst-case optimization.

Interference in multiuser systems is often characterized by a non-negative and irreducible coupling matrix. The maximum eigenvalue (Perron root) of the weighted coupling matrix provides a single measure for the joint achievability of certain signal-to-interference ratios (SIR). In this paper, we address the more general case where the users are coupled by concave interference functions. This corresponds to a system with adaptive receive strategies which minimize the interference received by each user. A necessary and sufficient condition for feasibility is obtained by minimizing the Perron root over the set of possible receive strategies. This type of problem is directly related to the problem of (weighted) max-min-SIR balancing. This paper provides an analytical framework and an iterative algorithm that converges monotonically to a global optimum. We also study an alternative approach based on a fixed point iteration. This iteration is shown to converge to the global optimum if the SIR targets lie on the boundary of the region.

In this work the transmit covariance matrix optimization problem for the discrete memoryless MIMO Gaussian bidirectional broadcast channel is studied. A half-duplex relay node establishes bidirectional communication between two nodes using a decode-and-forward protocol. In the initial multiple access phase both nodes transmit their messages to the relay node. In the succeeding phase the relay broadcasts an optimal re-encoded message so that both nodes can decode the other's message using their own message as side information. The capacity region of the bidirectional broadcast channel is completely characterized by a weighted rate sum maximization problem, which can be solved by a simple iterative fixed point algorithm. If an efficient transmit covariance matrix is invariant with respect to the joint subspace spanned by the channels, then different combinations of the part transmitted on the orthogonal subspaces result in equivalent transmit strategies with different ranks. A closed-form procedure to obtain the optimal transmit covariance is derived for the case where the rank of the channels is equal to the number of antennas at the relay node and a full-rank transmission is optimal. It shows the complicated structure of the optimal eigenspace, which depends on the weights and the mean transmit power constraint. For parallel channels the optimal solution is completely characterized and discussed, which also solves the optimal power allocation problem for a single-antenna OFDM system.

In this letter we propose a power allocation iteration which optimizes the weighted aggregate performance of a single-hop network. We show that the proposed iteration is a competitive alternative to conventional gradient iterations in terms of convergence and computational effort.

We determine the capacity of compound classical-quantum channels. As a consequence, we obtain the capacity formula for the averaged classical-quantum channels. The capacity result for compound channels demonstrates, as in the classical setting, the existence of reliable universal classical-quantum codes in scenarios where the onlya prioriinformation about the channel used for the transmission of information is that it belongs to a given set of memoryless classical-quantum channels. Our approach is based on a universal classical approximation of the quantum relative entropy which in turn relies on a universal hypothesis testing result.

Common methods for the calculation of the spectral factorization rely on an approximation of the given spectral density by a polynomial and a subsequent factorization of this polynomial. It is known that the regularity of the stochastic sequence determines the achievable approximation rate of its spectrum. However, since the approximative polynomial should be factorized, it has to be positive. It is shown that this restriction on the approximation polynomial implies a limitation on the approximation rate for linear methods whereas for nonlinear methods the optimal approximation rate can still be achieved. This has also consequences for the rate of convergence of the spectral factor, which is investigated in the second part. There, a lower and an upper bound for the error in the spectral factor is derived, which shows the dependency on the approximation degree and on the regularity of the stochastic sequence. Finally, if the spectral density is given only on a finite set of sampling points, no linear approximation method exists such that the error in the spectral factor can be controlled by the approximation degree.

Collective choice functions and an axiomatic framework will be used to characterize the structure of solutions of resource allocation problems on feasible utility sets. Feasible utility sets will be characterized as level sets of general interference functions. General fairness constraints will be introduced and solution outcomes satisfying the properties of efficiency, robustness and fairness will be analyzed. A new type of sets, basic bargaining sets will be defined and if the properties of the solution outcome are known on these sets then we know it's properties for all feasible utility regions.

For comprehensive convex compact positive utility sets, the Nash bargaining solution (NBS) is obtained by maximizing a product of utilities, a strategy which is also known as "proportional fairness". However, the standard assumption of convexity may not be fulfilled. This is especially true for wireless communication systems, where interference and adaptive techniques can lead to complicated non-convex utility sets (e.g. the 2-user SIR region with linear receivers). In this paper, we show that the Nash bargaining framework can be extended to certain non-convex utility sets, whose logarithmic transformation is strictly convex comprehensive. As application examples, we consider feasible sets of signal-to-interference ratios (SIR), based on axiomatic log-convex interference functions. The resulting SIR region is known to be log-convex. However, strict log-convexity and compactness is required here. We derive conditions under which this is fulfilled. In this case, there is a single-valued Nash bargaining solution, which is equivalent to the proportionally fair operating point. The results are shown for a total power constraint, as well as for individual power constraints.

It is well-known that the downlink beamforming problem of minimizing the total transmit power under users' signal-to-interference- plus-noise ratio (SINR) constraints can be reformulated as a conic quadratic optimization problem and efficiently solved, if the transmitter is provided with the perfect information about the channel. In this work, we study the robust counterpart of the latter, convex problem. By robustness it is meant that the base station knows only uncertainty regions where the exact channels lie, and that it is supposed to satisfy the conic quadratic constraints for all channels that belong to these regions. We provide a direct optimal solution for this problem, based on the ellipsoid method from convex optimization theory. By exploiting the structure of the problem, we define also a virtual robust mean square error optimization problem, that can be solved by semidefinite programming methods in a much more efficient manner, and which presents (at least) a tight conservative approximation of the main problem.

Cooperative transmission with multiple base stations is a way to overcome the interference limitation of conventional cellular system. We investigate the problem of linear transceiver design for such a network Multiple-Input-Multiple- Output (MIMO) system with per-base-station power constraints. Four design goals are considered: minimizing the total sum-MSE subject to per-base-station power constraints; minimizing the total transmit power subject to a total sum-MSE target and per-base-station power constraints; minimizing the maximum weighted user-MSE subject to per-base-station power constraints; minimizing the total transmit power subject to a set of user-MSE targets and per-base-station power constraints. For these problems, we derive globally optimal transmitters by reformulating the problems as convex Second Order Cone Programs (SOCPs). We also propose iterative algorithms for joint transmitter/receiver optimization. The joint transceiver optimization exploits that for the optimal transmitter, the receivers can be updated as linear MMSE filters. We prove that the proposed algorithms converge to local optima due to the non-convexity of the problems.

The problem of transceiver optimization in multiuser multiple-input multiple-output downlink wireless systems is considered. The base station is assumed to possess only estimated, erroneous values of channel coefficients. The exact channels lie in uncertainty regions, specified by the Frobenius norms of the error matrices. An iterative optimization of the transmit and receive filters is performed with the goal of minimizing the total transmit power, while satisfying the users' mean square error (MSE) targets for all channels from the uncertainty regions. Each iteration consists of two steps that can be equivalently rewritten as semidefinite programs with efficient numerical solutions. It is shown that the whole algorithm converges. The proposed framework can be applied for solving robust counterparts of several related MSE-optimization problems. The modifications of the proposed algorithms for accommodating box-like disturbances are analyzed, as well.

In this paper we extend recent coding results by Datta and Dorlas on classical capacity of averaged quantum channels with finitely many memoryless branches to arbitrary number of branches. Only assumption in our approach is that the channel satisfies some weak measurability properties. Our approach to the direct coding theorem is based on our previous work on compound classical-quantum channels. The weak converse requires an alternative characterization of the essential infimum and the remaining proof proceeds via application of Holevo’s bound and Fano’s inequality.

We analyze sampling representations for translation invariant, linear and bounded systems, operating on band-limited signals. First, we characterize suitable kernels for reconstruction processes with and without oversampling. Then, we investigate the convergence behavior of general approximation processes, operating only on the samples and not on the whole continuous-time signal, for translation invariant, linear and bounded systems and signals in the Paley-Wiener space PWpi1. Recently, Habib analyzed similar questions for a larger space of functions, namely the Zakai class, but for a considerably smaller class of systems, not including the Hilbert transformation and the ideal low-pass filter. We show that for important systems there exists no approximation process that is uniformly convergent for all functions in PWpi1. Surprisingly, oversampling and the design of special kernels does not improve the convergence behavior in this case. Furthermore, a simple criterion is given for checking whether a certain approximation process is convergent for a given system or not.

We consider transmission over a wireless multiple antenna communication system operating in a Rayleigh flat fading environment with no channel state information at the receiver and the transmitter. We show that, subject to the average power constraint, the support of the capacity achieving input distribution is bounded. Moreover, we show by a simple example concerning the identity theorem (or uniqueness theorem) from the complex analysis in several variables that some of the existing results in the field are not rigorous.

This paper addresses the problem of incorporating QoS support into the traditional utility-based power control problem. We present a novel problem formulation, prove relevant properties of an optimal power allocation and propose a decentralized recursive algorithm with global convergence.

We consider the broadcast phase of a three-node network, where a relay node establishes a bidirectional communication between two nodes using a spectrally efficient two-phase decode-and-forward protocol. In the first phase the two nodes transmit their messages to the relay node. Then the relay node decodes the messages and broadcasts a re-encoded composition of them in the second phase. We consider Gaussian MIMO channels and determine the capacity region for the second phase which we call the Gaussian MIMO bidirectional broadcast channel.

We determine the capacity of compound classicalquantum channels. The capacity result for compound channels demonstrates, as in the classical setting, the existence of reliable universal classical-quantum codes in scenarios where the only a priori information about the channel used for the transmission of information is that it belongs to a given set of memoryless classical-quantum channels. Our approach is based on the universal classical approximation of the quantum relative entropy which in turn relies on the universal hypothesis testing results.

Since the discovery of Shannonpsilas sampling theorem, signal and system representation has become an intense research topic. One task of system theory is to find efficient representations of signals and systems. In this paper time domain representations of stable linear time-invariant systems are analyzed. Although a frequency domain representation of such systems is always possible, the time domain representation is problematic. It is shown that the convolution integral diverges for certain systems and functions. Furthermore, we characterize the systems for which a time domain representation is possible by giving necessary and sufficient conditions for pointwise and uniform convergence.

We consider a three-node network, where a relay node establishes a bidirectional communication between two nodes using a two-phase decode-and-forward protocol. In the first phase the two nodes transmit their messages to the relay node which decodes them. Then the relay broadcasts the information to both nodes in the succeeding phase which we call the bidirectional broadcast channel. In this work we first consider both phases separately and compare existing strategies especially for the second phase. We determine the capacity region of the bidirectional broadcast channel and discuss the impact of multiple antennas and the correlation between the channels on the capacity region. We show how the available spectral resources can be shared between the two phases and compare achievable rate regions for the whole bidirectional communication. Finally, we indicate how the bidirectional relay communication and the knowledge about the corresponding rate region can be advantageously used in cellular systems or cross-layer designs.

An iterative algorithm for the multiuser fair scheduling problem of adaptive OFDMA systems is presented. It uses iterative local search with k-opt switches in the combinatorial solution space. The algorithm can be used with different scheduling criteria like proportional fairness and max-min fairness, both for constant and adaptive allocation of power to subcarriers/resource blocks. The algorithm is applied to a simplified model of 3GPP LTE and its properties are simulatively investigated in the constant power and the adaptive power case.

The feasible log-SIR region is defined as a set of all signal-to-interference ratios (SIR) expressed in logarithmic scale that can be supported in a wireless network by means of power control and with all users being active concurrently. Recently, the feasible log-SIR region was shown to be a convex set, which is a key ingredient in the development of some power control strategies for wireless systems. In this paper, under the assumption of a noiseless channel, we strengthen these results by proving a necessary and sufficient condition for the feasible log-SIR region to be a strictly convex set. The strict convexity property is of interest since it is closely related to the problem of the existence and uniqueness of a so-called log-SIR fair power vector.

In this work, we study a cross-layer design of a spectrally efficient bidirectional relay communication in a three- node network using superposition encoding at the relay node. On the physical layer, a half-duplex relay node decodes-and- forwards the messages of two nodes in a two-phase protocol with optimal time-division. On the data link layer, we assume ergodic arrival processes at node 1 and 2 which have queues with infinite buffer length. At the beginning of each time-slot a centralized controller chooses the service rate pair which achieves the weighted rate sum maximum of the instantaneous achievable rate region for the block-fading channel state of the next time-slot with weights equal to the current buffer levels. To this end, the controller adjusts the time-division and relay power distribution. The policy is throughput optimal since the stability region is equal to the bidirectional ergodic rate region. This is because whenever the mean queue length is large, a negative drift of a quadratic Lyapunov function on the buffer levels can be proved.

In this paper, we consider ergodic causal classical-quantum channels (cq-channels) which additionally have a decaying input memory. In the first part, we develop some structural properties of ergodic cq-channels and provide equivalent conditions for ergodicity. In the second part, we prove the coding theorem with weak converse for causal ergodic cq-channels with decaying input memory. Our proof is based on the possibility to introduce a joint input–output state for the cq-channels and an application of the Shannon–McMillan theorem for ergodic quantum states. In the last part of the paper, it is shown how this result implies a coding theorem for the classical capacity of a class of causal ergodic quantum channels.

This correspondence studies the calculation of the Hilbert transform of continuous functions f with continuous conjugate f from a finite set of sampling points. It shows that there exists no linear operator which approximates f arbitrary well in the uniform norm from a finite number of sampling points for all possible continuous function f with continuous conjugate f. However for smooth functions such linear approximation operators exist and sufficient conditions on the smoothness of the functions are presented. The correspondence also examines the robustness of the calculation of the Hilbert transform from interpolated data and it gives explicit error bounds. It is shown that for a large class of algorithms the error grows at least proportional to the logarithm of the number of sampling points.

This paper provides a theoretical framework for the analysis of interference-coupled multiuser systems. The fundamental behavior of such a system is modeled by interference functions, defined by axioms ldquononnegativity, rdquoscale-invariance,rdquo and ldquomonotonicity.rdquo It is shown that every interference function has an interpretation as the optimum of a min-max problem, where the optimization is over a closed comprehensive positive coefficient set. This provides new insight into the structure of general interference functions and its elementary building blocks. Conversely, it is shown that every closed comprehensive positive set can be expressed as a level set of an interference function. This shows a close connection between the analysis of interference functions and multiuser performance regions, which are typically closed comprehensive. The generality of this framework allows for a wide range of potential applications. As an example, we analyze the problem of interference balancing.

The behavior of certain interference-coupled multiuser systems can be modeled by means of logarithmically convex (log-convex) interference functions. In this paper, we show fundamental properties of this framework. A key observation is that any log-convex interference function can be expressed as an optimum over elementary log-convex interference functions. The results also contribute to a better understanding of certain quality-of-service (QoS) tradeoff regions, which can be expressed as sublevel sets of log-convex interference functions. We analyze the structure of the QoS region and provide conditions for the achievability of boundary points. The proposed framework of log-convex interference functions generalizes the classical linear interference model, which is closely connected with the theory of irreducible nonnegative matrices (Perron-Frobenius theory). We discuss some possible applications in robust communication, cooperative game theory, and max-min fairness.

In a three-node network bidirectional communication between two nodes can be enabled by a half-duplex relay node with a decode-and-forward protocol. In the first phase, the messages of two nodes are transmitted to the relay node. In the second phase a re-encoded composition is broadcasted by the relay node. In this work the capacity region of the broadcast phase in terms of the maximal probability of error is determined. It is characterized by the mutual informations of the separate channels coupled by the common input.

Efficient design of online power allocation policies relies strongly on convex-analytic and optimization-theoretic properties of the optimization problem on hand. In this context we study the optimization of power allocation in cellular networks with so-called best-effort traffic. Our results exhibit a specific role of link QoS parameters, for which the dependence on the corresponding link SINR is log-convex. In such case the region of achievable QoS vectors is shown to be convex, the considered problem is globally solvable and can be easily transformed into a favorable convex form.

We consider the problem of relay selection in a network with N relay nodes. A half-duplex relay node enables bidirectional communication between two nodes with a spectrally efficient two-phase protocol. In the first phase both nodes transmit their messages to a relay node, which decodes the messages and broadcasts a composition using superposition encoding in the succeeding phase. The probability that the achievable rate region of one relay node contains all other rate regions decreases with the number of relay nodes N. Therefore, we propose a relay selection criterion that decides according to the weighted rate sum for any bidirectional rate pair on the boundary of the achievable rate region individually. If we allow time-sharing between the usage of different relay nodes, we can enlarge the achievable rate region. In an iid Rayleigh fading scenario relay selection realizes multi-user diversity so that the sum-rate of any rate pair on the boundary of the ergodic rate region asymptotically grows with Theta(log(log(/V))).

In this work we consider the achievable rates of a joint resource allocation for a three-node network where a half-duplex relay node enables bidirectional communication between nodes 1 and 2 and thereby adds an own multicast message to the communication. In the multiple access phase nodes 1 and 2 transmit their message to the relay node, which decodes the messages and forwards them in the succeeding broadcast phase. Therefore, the relay node encodes the multicast and bidirectional messages using the superposition encoding strategy. We do not allow cooperation between the encoders of nodes 1 and 2, but since both nodes know a priori its own bidirectional message, both nodes can cancel the interference caused by their own message before decoding the unknown messages. It shows that for both nodes it is always optimal to decode the relay message first. Furthermore, the total sum-rate maximum is determined by the sum-rate optimum of the bidirectional broadcast phase. From the closed form solutions of the combinatorial problems we can characterize the bidirectional rate pairs where the total sum-rate remains constant. In the end the obtained results are discussed and illustrated by means of some working examples. The joint resource allocation improves the overall spectral efficiency and enables new trade-offs between the routing tasks.

This paper studies the approximation of continuous functions in subsets of all causal and stable transfer functions. Such approximations play a central roll in filter design, filter bank analysis, and in sampling, since any filtering can be considered as a kind of approximation in a space defined by the filters. The present paper studies in particular the consequences resulting from the causality and stability constrain imposed on the filter process. It is shown that there exists no linear approximation method which is also causal and stable. Only if either the causality or the stability constrain is left out, a linear approximation method may exist.

We address the problem of interference coupling and achievability of SIR targets in a multiuser system. Interference is modeled by an axiomatic framework, with log-convex interference functions. There are efficient algorithms which perform optimization over the boundary of the SIR region, but they typically require that the boundary is achievable. We show that achievability is closely linked to the interference coupling in the system. This effect is already known from power control theory, where achievability is commonly ensured by assuming an irreducible coupling matrix. In this paper, we consider a more general interference model which is based on an axiomatic framework. In order to describe the interference coupling in the system, the concept of a dependency matrix is introduced. It is shown that the achievability of the boundary only depends on the combinatorial structure of this matrix. Necessary and sufficient conditions are derived.

We study the transmit strategies in a MIMO bidirectional relaying scenario with individual power constraints. In two phases a half-duplex relay node decodes-and-forwards the signals of two nodes. Each node has multiple antennas. We deduce the transmit strategy in the first phase from the general Gaussian MIMO-MAC. Since each node knows a priori the interference of its own message in the second phase interference-free reception is achieved. Therefore, the optimal relay transmit strategy is given by two point-to-point water-filling solutions which are coupled by the relay power distribution. In the large SNR, the sum of any bidirectional rate tuple on the boundary of the rate region is asymptotically proportional with the minimum spatial degree of both MIMO channels.

This paper investigates the problem of transceiver design with individual rate constraints for multiuser MIMO systems. We focus on linear processing with two design goals: one is to maximize the minimum rate per user under a total power constraint, and the other is to minimize the total transmit power while maintaining certain rate requirements. The optimization is carried out in an alternating manner in both virtual uplink and downlink channels. Each iteration contains the optimization of uplink power allocation, and uplink and downlink MMSE receive filters. The uplink power control to balance the rates or to achieve the rate requirements is taken by optimizing the product of MSEs, which can be formulated as a geometric programming (GP) problem. Additionally, this alternating optimization approach is suitable for the case with successive interference cancellation (SIC) in the uplink and interference pre-compensation (IPC) in the downlink as well. With a fixed precoding ordering, this provides new sub-optimal solutions to the above problems.

We address the problem of maximizing the minimum signal-to-interference ratio (SIR) in a multiuser system. In the context of resource allocation, this is referred to as max-min fairness. Moreover, the balanced SIR margin is an indicator for feasibility, so the problem also plays a fundamental role for the characterization of the SIR achievable region and related regions. In this paper, we propose an iterative solution for max-min SIR balancing under the assumption of convex interference functions. It is proven that the proposed iteration always finds the unique global optimum. Similar results in the beamforming context [1] differ in two respects: Firstly, a much more general interference model is used. Secondly, the results a found by using a different analytical approach, which allows to show convergence directly, without the need of compactness arguments. This way, uniqueness of the optimum can be shown. Finally, we show that Yates' fixed-point iteration [2], which is successfully used in a different context, does generally not converge to the max-min optimum, unless an additional scaling is introduced.

We propose a unifying framework for max-min fairness in orthogonal networks and networks with interference. First, a universal formulation of the max-min fairness problem for orthogonal networks and networks with interference is presented. This shows that orthogonal networks and networks with interference can be universally described by a graph, induced by time sharing of resources and interference coupling, respectively. As a consequence, a unifying graph-related characterization of performance achieved under max-min fairness is obtained.

In this contribution we describe some structural properties of ergodic classical-quantum channels and provide several equivalent conditions of ergodicity of such channels. In the second part we sketch the coding theorem with the weak converse for ergodic input-memoryless causal classical-quantum channels. Full proofs and several extensions of the results described here are contained in a accompanying paper.

In this paper we discuss the interplay between discrete-time and continuous-time signals and the question, whether certain properties of the signal in one domain carry over to the other domain. The Shannon sampling series and the more general Valiron interpolation series are the appropriate means to obtain the continuous-time, bandlimited signal out of its samples, i.e., the discrete-time signal. Furthermore, we investigate the symmetric sampling series and the behavior of the non-symmetric sampling series, which follows from the properties of the projection operator. It is well known, that the space of discrete-time signals with finite energy and the space of continuous- time, bandlimited signals with finite energy are isomorphic. Thus, discrete-time and continuous-time, bandlimited signals with finite energy can be used interchangeably. This interchangeability is not restricted to finite energy signals. It is valid for a considerably larger class, but not for the space of bounded signals: Even if the discrete-time signal is bounded, the corresponding bandlimited interpolation can be unbounded. For the proof we explicitly state such a bounded discrete-time signal. Furthermore, we show not only that the Shannon sampling series diverges for this signal, but also that there is no bounded, bandlimited interpolation at all.

Common methods for the calculation of the spectral factorization rely on an approximation of the given spectral density by a trigonometric polynomial and a subsequent spectral factorization of this polynomial. Since the approximative polynomial should be factorized, the approximation method must be positive. The first part of this paper studies such approximation methods and deduces limitation on the approximation rate for linear methods which arise from the required positivity. The second part states a lower and an upper bound on the error in the spectral factor induced by the approximation of the spectral density. They show the dependency of the error on the regularity of the stochastic process and on the approximative degree.

This paper provides a theoretical framework for the analysis of interference-coupled multiuser systems. Interference is characterized by a set of axioms defining some fundamental properties. The generality of this approach allows for a wide range of potential applications, including adaptive receive strategies and worst-case designs. One main result is to show that every interference function has a max-min and a min-max representation over parameter-dependent elementary interference functions. The analysis of these elementary components provides new insight into the structure of general interference functions. In particular, every interference function can be interpreted as an optimum over a closed set with certain monotonicity properties. Under certain conditions this can be interpreted as an optimization of a network utility/cost over a multiuser QoS region. So the analysis of interference functions is closely connected with the analysis of multiuser QoS regions. The proposed framework provides a better general understanding of cross-layer optimization and resource allocation in the presence of interference.