Secure communication in a potentially hostile environment is becoming more and more critical. The A rbitrarily V arying W iretap C hannel (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 the C ommon R andomness (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).

We consider the problem of semantic security via classical-quantum and quantum wiretap channels and use explicit constructions to transform a non-secure code into a semantically secure code, achieving capacity by means of biregular irreducible functions. Explicit parameters in finite regimes can be extracted from theorems. We also generalize the semantic security capacity theorem, which shows that a strongly secure code guarantees a semantically secure code with the same secrecy rate, to any quantum channel, including the infinite-dimensional and non-Gaussian ones.

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.

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 first prepares an entangled photon pair locally, and then transmits one of the photons 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.

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 standardisation of 5G is reaching its end, and the networks have started being deployed. Thus, 6G architecture is under study and design, to define the characteristics and the guidelines for its standardisation. In parallel, communications based on quantum-mechanical principles, named quantum communications, are under design and standardisation, leading to the so-called quantum internet. Nevertheless, these research and standardisation efforts are proceeding in parallel, without any significant interaction. Thus, it is essential to discuss an architecture and the possible protocol stack for classical-quantum communication networks, allowing for an effective integration between quantum and classical networks. The main scope of this paper is to provide a joint architecture for quantum-classical communication networks, considering the very recent advancements in the architectural design of 6G and the quantum internet, also defining guidelines and characteristics, which can be helpful for the ongoing standardisation efforts. For this purpose, the article discusses some of the existing main standardisation processes in classical communications and proposed protocol stacks for quantum communications. This aims at highlighting the potential points of connection and the differences that may imply future incompatible developments. The standardisation efforts on the quantum internet cannot overlook the experience gained and the existing standardisation, allowing the creation of frameworks in the classical communication context.

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.

Communication over a quantum broadcast channel with cooperation between the receivers is considered. The first form of cooperation addressed is classical conferencing, where Receiver 1 can send classical messages to Receiver 2. Another cooperation setting involves quantum conferencing, where Receiver 1 can teleport a quantum state to Receiver 2. When Receiver 1 is not required to recover information and its sole purpose is to help the transmission to Receiver 2, the model reduces to the quantum primitive relay channel. The quantum 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. In particular, the cutset upper bound and the decode-forward lower bound are derived for the primitive relay channel. Furthermore, we present an entanglement-formation lower bound, where a virtual channel is simulated through the conference link. At last, we show that as opposed to the multiple access channel with entangled encoders, entanglement between decoders does not increase the classical communication rates for the broadcast dual.

We consider the decision problem associated with the task of remotely estimating the state of a dynamic plant via a noisy communication channel. Given a machine-readable description of the plants and channels characteristics, does there exist an algorithm that decides whether remote state estimation is possible From an analytic point of view, this problem has been shown to involve the zero-error capacity of the communication channel. By applying results from Turing machine theory and zero-error coding, we analyze several related variants of the decision problem above. Our analysis also incorporates a weakened form of the state estimation objective, which has been shown to depend on the classical Shannon Capacity instead. In the broadest sense, our results yield a fundamental limit to the capabilities of computer-aided design tools and adaptive autonomous systems, assuming they are based on digital hardware.

Transmission of classical information over a quantum state-dependent channel is considered, when the encoder can measure channel side information (CSI) and is required to mask information on the quantum channel state from the decoder. In this quantum setting, it is essential to conceal the CSI measurement as well. A regularized formula is derived for the masking equivocation region, and a full characterization is established for a class of measurement channels.

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.

This paper shows that every simple but non-trivial continuous-time, linear time-invariant (LTI) system shows a complexity blowup if its output is simulated on a digital computer. This means that for a given LTI system, a Turing machine can compute a low-complexity input signal in polynomial-time but which yields a corresponding output signal which has high complexity in the sense that the computation time for determining an approximation up to n significant digits grows faster than any polynomial in n. A similar complexity blowup is observed for the calculation of Fourier series approximations and the Fourier transform.

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.

This column aims to increase the visibility and exposure of network-related research projects/activities around the world. The theme of this inaugural column is “6G Networks Research in Europe — Overview of Current Status and Future Directions.” While 5G technology is being deployed worldwide, research efforts in academia and industry are already shaping the vision for 6G. 6G is expected to meet the expectations that 5G cannot, deliver the next level of experience in all areas of society through hyperconnectivity, and provide services that may seem like science fiction today. In the 6G era, the human, physical, and digital worlds will merge in unison to enable rich multi-sensory experiences involving humans, machines, and the physical world. Some 6G services already stand out, including immersive extended reality, holographic communications, and virtual replicas. Achieving 6G will require major innovations in several areas, including wireless connectivity and integration of non-terrestrial networks, incorporating artificial intelligence into the very fabric of communication networks, and networked sensing. While there is still much innovation to come in 5G with new versions of the standard, 6G research is well underway around the world, including in Europe, to make 6G commercially available by 2030. The major projects underway in Europe include the following: 6G-life, Hexa-X, AI@EDGE, DAEMON, and MARSAL

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 2nlog(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.

The initial vision of cellular communications was to deliver ubiquitous voice communications to anyone anywhere. In a simplified view, 1G delivered voice services for business customers, and only 2G for consumers. Next, this also initiated the appetite for cellular data, for which 3G was designed. However, Blackberry delivered business smartphones, and 4G made smartphones a consumer device. The promise of 5G is to start the Tactile Internet, to control real and virtual objects in real-time via cellular. However, the hype around 5G is, again, focusing on business customers, in particular in the context of campus networks. Consequently, 6G must provide an infrastructure to enable remote-controlled mobile robotic solutions for everyone—the Personal Tactile Internet. Which role can information and communication theory play in this context, and what are the big challenges ahead?

We describe a method of investigating the near-term potential of quantum communication technology for communication networks from the perspective of current networks. For this, we integrate an instance of the quantum network simulator QuNetSim at the link layer into the communication network emulator ComNetsEmu. This novel augmented version of ComNetsEmu is thereby enabled to run arbitrary quantum protocols between any directly connected pair of network hosts. To give an example of the proposed method, we implement the link layer method of generating and storing entanglement while idle, to accelerate data transmission at later times using superdense coding.

Turing computability deals with the question of what is theoretically computable on a digital computer, and hence is relevant whenever digital hardware is used. In this paper we study different possibilities to define computable bandlimited signals and systems. We consider a definition that uses finite Shannon sampling series as approximating functions and another that employs computable continuous functions together with an effectively computable time concentration. We discuss the advantages and drawbacks of both definitions and analyze the connections and differences. In particular, we show that both definitions are equivalent for many practically relevant signal classes, e.g. for bandlimited signals with finite energy, but also that there are important differences, such as for the impulse responses of BIBO stable LTI systems.

This paper proves that every non-trivial, linear time-invariant (LTI) system of the first order shows a complexity blowup if it is simulated on a digital computer. This means that there exists a low-complexity input signal, which can be generated on a Turing machine in polynomial time, but such that the output signal of the LTI system has high complexity in the sense that the computation time for determining an approximation up to n significant digits grows faster than any polynomial in n. Moreover, this input signal can easily and explicitly be generated from the given system parameters by a Turing machine. It is also shown that standard techniques for simulating higher-order LTI systems with real poles show the same complexity blowup. Finally, it is shown that a similar complexity blowup occurs for the calculation of Fourier series approximations and Fourier transforms

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 1/n log M (as defined by Shannon for transmission) and 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.

This paper analyzes the problem of common randomness (CR) generation from correlated discrete sources aided by unidirectional communication over Single-Input SingleOutput (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.

This article summarizes the current status of classical communication networks and identifies some critical open research challenges that can only be solved by leveraging quantum technologies. Until now, the main goal of quantum communication networks has been security. However, quantum networks can do more than just exchange secure keys or serve the needs of quantum computers. In fact, the scientific community is still investigating the possible use cases/benefits that quantum communication networks can bring. Thus, this article aims to point out and clearly describe how quantum communication networks can enhance in-network distributed computing and reduce the overall end-to-end latency, beyond the intrinsic limits of classical technologies. Furthermore, we also explain how entanglement can reduce the communication complexity (overhead) that future classical virtualized networks will experience.

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.

Communication over a quantum broadcast channel with cooperation between the receivers is considered. The first form of cooperation addressed is classical conferencing, where receiver 1 can send classical messages to receiver 2. Another cooperation setting involves quantum conferencing, where receiver 1 can teleport a quantum state to receiver 2. When receiver 1 is not required to recover information and its sole purpose is to help the transmission to receiver 2, the model reduces to the quantum primitive relay channel. The quantum 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. In particular, the cutset upper bound and the decode-forward lower bound are derived for the primitive relay channel. Furthermore, we present an entanglement-formation lower bound, where a virtual channel is simulated through the conference link. At last, we show that as opposed to the multiple access channel with entangled encoders, entanglement between decoders does not increase the classical communication rates for the broadcast dual. Published under an exclusive license by AIP Publishing.

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.

We study the time-domain concentration of bandlimited signals form a computational point of view. To this end we employ the concept of Turing computability that exactly describes what can be theoretically computed on a digital machine. A previous definition of computability for bandlimited signals is based on the idea of effective approximation with finite Shannon sampling series. In this paper we provide a different definition that uses the time-domain concentration of the signals. For computable bandlimited signals with finite L p -norm, we prove that both definitions are equivalent. We further show that local computability together with the computability of the L p -norm imply the computability of the signal itself. This provides a simple test for computability.

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.

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.

Today, the Internet of Things (IoT) continues to evolve as a predominant technical trend. In the face of the global pandemic, many conventional IoT paradigms are, however, expected to shift in response to pressing societal challenges. For instance, we are preparing to observe substantial investments in the telemedicine and healthcare sectors as well as efficient work-from-home solutions. This accentuates the need for edge intelligence in supporting the increasingly massive IoT deployments augmented with machine learning capabilities, among many others.

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.

We consider the task of remote state estimation and stabilization of disturbed linear plants via noisy communication channels. In 2007 Matveev and Savkin established a surprising link between this problem and Shannon's theory of zero-error communication. By applying very recent results of computability of the channel reliability function and computability of the zero-error capacity of noisy channels by Boche and Deppe, we analyze if, on the set of linear time-invariant systems paired with a noisy communication channel, it is uniformly decidable by means of a Turing machine whether remote state estimation and stabilization is possible. The answer to this question largely depends on whether the plant is disturbed by random noise or not. Our analysis incorporates scenarios both with and without channel feedback, as well as a weakened form of state estimation and stabilization. In the broadest sense, our results yield a fundamental limit to the capabilities of computer-aided design and autonomous systems, assuming they are based on real-world digital computers.

We consider the task of remote state estimation and stabilization of disturbed linear plants via noisy communication channels. In 2007 Matveev and Savkin established a surprising link between this problem and Shannon's theory of zero-error communication. By applying very recent results of computability of the channel reliability function and computability of the zero-error capacity of noisy channels by Boche and Deppe, we analyze if, on the set of linear time-invariant systems paired with a noisy communication channel, it is uniformly decidable by means of a Turing machine whether remote state estimation and stabilization is possible. The answer to this question largely depends on whether the plant is disturbed by random noise or not. Our analysis incorporates scenarios both with and without channel feedback, as well as a weakened form of state estimation and stabilization. In the broadest sense, our results yield a fundamental limit to the capabilities of computer-aided design and autonomous systems, assuming they are based on real-world digital computers.

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.

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-Korner 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.

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.

The channel reliability function is an important tool that characterizes the reliable transmission of messages over communication channels. For many channels, only the upper and lower bounds of the function are known. In this paper 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 consider the R∞ function and the zero-error feedback capacity, since they play an important role in the context of the reliability function. Both the R∞ function and the zero-error feedback capacity are not Banach Mazur computable. We show that the R∞ function is additive. The zero-error feedback capacity is super-additive and we characterize its behavior.

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.

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.

Solving continuous problems on digital computers gives generally only approximations of the continuous solutions. It is therefore crucial that the error between the continuous solution and the digital approximation can effectively be controlled. This paper investigates the possibility of simulating linear, time-invariant (LTI) systems on Turing machines. It is shown that there exist elementary LTI systems for which an admissible and computable input signal results in a non-computable output signal. For these LTI systems, the paper gives sharp characterizations of input spaces such that the output is guaranteed to be computable. The second part of the paper discusses the computability of the impulse and step response of LTI systems. It is shown that the computability of the step response implies not the computability of the impulse response. Moreover, there exist impulse responses which cannot be computed from the transfer function using the inverse Laplace transform. Finally, the paper gives a stronger version of a classical non-computability result, showing that there exist admissible and computable initial values for the wave equation so that the solution cannot be computed at certain points in space and time.

Elementary building blocks for quantum repeaters based on fiber channels and memory stations are analyzed. Implementations are considered for three different physical platforms, for which suitable components are available: quantum dots, trapped atoms and ions, and color centers in diamond. The performances of basic quantum repeater links for these platforms are evaluated and compared, both for present‐day, state‐of‐the‐art experimental parameters as well as for parameters that can in principle be reached in the future. The ultimate goal is to experimentally explore regimes at intermediate distances—up to a few 100 km—in which the repeater‐assisted secret key transmission rates exceed the maximal rate achievable via direct transmission. Two different protocols are considered, one of which is better adapted to the higher source clock rate and lower memory coherence time of the quantum dot platform, while the other circumvents the need of writing photonic quantum states into the memories in a heralded, nondestructive fashion. The elementary building blocks and protocols can be connected in a modular form to construct a quantum repeater system that is potentially scalable to large distances.

The conversion of analog signals into digital signals and vice versa, performed by sampling and interpolation, respectively, is an essential operation in signal processing. When digital computers are used to compute the analog signals, it is important to effectively control the approximation error. In this paper we analyze the computability, i.e., the effective approximation of bandlimited signals in the Bernstein spaces B-pi(p),1 <= p < infinity, and of the corresponding discrete-time signals that are obtained by sampling. We show that for 1 < p < infinity, computability of the discrete-time signal implies computability of the continuous-time signal. For p = 1 this correspondence no longer holds. Further, we give a necessary and sufficient condition for computability and show that the Shannon sampling series provides a canonical approximation algorithm for p > 1. We discuss BIBO stable LTI systems and the time-domain concentration behavior of bandlimited signals as applications.

In this paper we study from an algorithmic perspective the problem of finding the peak value of a bandlimited signal. This problem plays an important role in the design and optimization of communication systems. We show that the peak value problem, i.e., computing the peak value of a bandlimited signal from its samples, can be solved algorithmically if oversampling is used. Without oversampling this is not possible. There exist bandlimited signals, for which the sequence of samples is computable, but the signal itself is not. This problem is directly related to the question whether there is a link between computability in the digital domain and the analog domain, and hence to a fundamental signal processing problem. We show that there is an asymmetry between continuous-time and discrete-time computability. Further, we study the decay behavior of computable bandlimited signals, which describes the concentration of the signals in the time domain, and, for locally computable bandlimited signals, we analyze if it is always possible to decide algorithmically whether the peak value is smaller than a given threshold.

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 have been well studied and often closed-form solutions are known. On the other hand, the case of imperfect channel information is less understood and closed-form characterizations of optimal schemes remain unknown in many cases. This paper approaches this question from a fundamental, algorithmic point of view by studying whether or not such optimal schemes can be constructed algorithmically in principle (without putting any constraints on the computational complexity of such algorithms). To this end, the concepts of compound channels and averaged channels are considered as models for channel uncertainty and block fading and it is shown that, although the compound channel and averaged channel themselves are computable channels, the corresponding capacities are 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 (i.e., capacity-achieving) signal processing and coding schemes possible. This is particularly noteworthy as such schemes must exist (since the capacity is known), but they cannot be effectively, i.e., algorithmically, constructed. Thus, there is a crucial difference between the existence of optimal schemes and their algorithmic constructability. In addition, it is shown that there is no search algorithm that can find the maximal number of messages that can be reliably transmitted for a fixed blocklength. Finally, the case of partial channel knowledge is studied in which either the transmitter or the receiver have perfect channel knowledge while the other part remains uncertain. It is shown that also in the cases of an informed encoder and informed decoder, the capacity remains non-computable in general and, accordingly, optimal signal processing and coding schemes are not effectively constructible.

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.

This paper considers the problem of approximating the spectral factor of continuous spectral densities with finite Dirichlet energy based on finitely many samples of these spectral densities. Although there exists a closed form expression for the spectral factor, this formula shows a very complicated behavior because of the non-linear dependency of the spectral factor from spectral density and because of a singular integral in this expression. Therefore approximation methods are usually applied to calculate the spectral factor.

It is shown that there exists no sampling-based method which depends continuously on the samples and which is able to approximate the spectral factor for all densities in this set. Instead, to any sampling-based approximation method there exists a large set of spectral densities so that the approximation method does not converge to the spectral factor for every spectral density in this set as the number of available sampling points is increased. The paper will also show that the same results hold for sampling-based algorithms for the calculation of the outer function in the theory of Hardy spaces. (C) 2020 Elsevier Inc. All rights reserved.

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.

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.

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 C 0 , 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 C 0 and Θ 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 C 0 or Θ. Finally, we examine Zuiddam's characterization of C 0 and Θ in terms of algorithmic computability.

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. 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 multi letter formula for the common randomness secrecy capacity is derived. Furthermore, we compare our results to the random code secrecy capacity for the cases of maximum error criterion but without non-causal side information at the jammer, maximum error criterion with non-causal side information of the messages at the jammer, and the case of average error criterion without non-causal side information at the jammer.

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.

In this paper we analyze the capacity of a general model for arbitrarily varying classical-quantum channels (AVCQCs) when the sender and the receiver use correlation as a resource. In this general model, a jammer has side information about the channel input. We determine a single letter formula for the correlation assisted capacity. As an application of our main result, we determine the correlation assisted common randomness generation capacity. In this scenario the two channel users have access to correlation as a resource,and further use an AVCQC with an informed jammer for additional discussion. The goal is to create common randomness between the two channel users. We also analyze these capacity formulas when only a small number of signals from the correlation are available. For the correlation assisted common randomness generation capacity, we show an additional interesting property: For a sufficient amount of "public communication", common randomness generation capacity is Turing computable, however without this public communication constraint, the correlation assisted common randomness generation capacity is, in general, not Turing computable. Furthermore, we show that even without knowing the capacity formula of the deterministic capacity using maximal error criterion, we can show that it is impossible to evaluate the performance algorithmically on any current or future digital computer.

Congestion game is a widely used model for modern networked applications. A central issue in such applications is that the selfish behavior of the participants may result in resource overloading and negative externalities for the system participants. In this work, we propose a pricing mechanism that guarantees the sub-linear increase of the time-cumulative violation of the resource load constraints. The feature of our method is that it is resource-centric in the sense that it depends on the congestion state of the resources and not on specific characteristics of the system participants. This feature makes our mechanism scalable, flexible, and privacy-preserving. Moreover, we show by numerical simulations that our pricing mechanism has no significant effect on the agents' welfare in contrast to the improvement of the capacity violation.

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.

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.

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.

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.

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.

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.

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.

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.

Wireless communication systems are inherently vulnerable to intentional jamming. In this paper, two classes of such jammers are considered: those with partial and full knowledge. While the first class accounts for those jammers that know the encoding and decoding function, the latter accounts for those that are further aware of the actual transmitted message. Of particular interest are so-called denial-of-service (DoS) attacks in which the jammer is able to completely disrupt any transmission. Accordingly, it is of crucial interest for the legitimate users to detect such adversarial DoS attacks. This paper develops a detection framework based on Turing machines. Turing machines have no limitations on computational complexity and computing capacity and storage and can simulate any given algorithm. For both scenarios of a jammer with partial and full knowledge, it is shown that there exists no Turing machine which can decide whether or not a DoS attack is possible for a given channel and the corresponding decision problem is undecidable. On the other hand, it is shown for both scenarios that it is possible to algorithmically characterize those channels for which a DoS attack is not possible. This means that it is possible to detect those scenarios in which the jammer is not able to disrupt the communication. For all other channels, the Turing machine does not stop and runs forever making this decision problem semidecidable. Finally, it is shown that additional coordination resources such as common randomness make the communication robust against such attacks.

This paper considers the compound channel where the actual channel realization is unknown. It is only known that it comes from a given uncertainty set and that it remains constant throughout the entire duration of transmission. The capacity has been established providing a complete characterization and a simple formula for the computation of the maximal transmission rate. This is no longer the case for the ε-capacity of a compound channel, which characterizes the maximum transmission rate when a non-vanishing average error ε is tolerated. In this case, the compound channel is known to have no strong converse under the average error criterion and, therewith, the ε-capacity may be larger than the capacity for a vanishing error. As the capacity of compound channels is unknown, Ahlswede raised the question of whether or not there exists a (simple) recursive formula for it. This paper approaches this question from a fundamental, algorithmic point of view by studying whether or not such formulas can be found algorithmically in principle (without putting any constraints on the computational complexity of the algorithms). To this end, it is shown that there exists no algorithm or Turing machine that takes the compound channel and error as inputs and computes the corresponding ε-capacity. Accordingly, there is also no recursive formula for the ε-capacity providing a negative answer to Ahlswede's initial question. The developed framework is subsequently applied to the question of the existence of a strong converse, the existence of an optimal second order coding rate, and whether or not the pessimistic and optimistic definitions of the ε-capacity coincide. Cast as decision problems, it is shown that these questions are undecidable and therewith impossible to be answered algorithmically.

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 the 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.

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 the 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.

Medium access control and in particular resource allocation is one of the most important tasks when designing wireless communication systems as it determines the overall performance of a system. For the particular allocation of the available resources it is of crucial importance to know whether or not a channel supports a certain quality-of-service (QoS) requirement. This paper develops a decision framework based on Turing machines and studies the algorithmic decidability of whether or not a QoS requirement is met. Turing machines have no limitations on computational complexity, computing capacity, and storage. They can simulate any given algorithm and therewith characterize the fundamental performance limits for today's digital computers. In this paper, secure communication and identification systems are considered both under channel uncertainty and adversarial attacks. While for perfect channel state information, the question is decidable since the corresponding capacity function is computable, it is shown that the corresponding questions become semidecidable in the case of channel uncertainty and adversarial attacks. This means there exist Turing machines that stop and output the correct answer if and only if a channel supports the given QoS requirement. Interestingly, the opposite question of whether a channel capacity is below a certain threshold is not semidecidable.

This paper determines the solvability complexity index (SCI) and a corresponding tower of algorithms for the computational problem of calculating the Hilbert transform of a continuous function with finite energy from its samples. It is shown that the SCI of these algorithms is equal to 2 and that the SCI is independent on whether the calculation is done by linear or by general (i.e. linear and/or non-linear) algorithms.

In this paper we study the Fourier transform and the possibility to determine the binary expansion of the values of the Fourier transform in the Zermelo-Fraenkel set theory with the axiom of choice included (ZFC). We construct a computable absolutely integrable bandlimited function with continuous Fourier transform such that ZFC (if arithmetically sound) cannot determine a single binary digit of the binary expansion of the Fourier transform at zero. This result implies that ZFC cannot determine for every precision goal a rational number that approximates the Fourier transform at zero. Further, we discuss connections to Turing computability.

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.

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 quantify 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.

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.

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.

The Fourier transform is an important operation in signal processing. However, its exact computation on digital computers can be problematic. In this paper we consider the computability of the Fourier transform and the discrete-time Fourier transform (DTFT). We construct a computable bandlimited absolutely integrable signal that has a continuous Fourier transform, which is, however, not Turing computable. Further, we also construct a computable sequence such that the DTFT is not Turing computable. Turing computability models what is theoretically implementable on a digital computer. Hence, our result shows that the Fourier transform of certain signals cannot be computed on digital hardware of any kind, including CPUs, FPGAs, and DSPs. This also implies that there is no symmetry between the time and frequency domain with respect to computability. Therefore, numerical approaches which employ the frequency domain representation of a signal (like calculating the convolution by performing a multiplication in the frequency domain) can be problematic. Interestingly, an idealized analog machine can compute the Fourier transform. However, it is unclear whether and how this theoretical superiority of the analog machine can be translated into practice. Further, we show that it is not possible to find an algorithm that can always decide for a given signal whether the Fourier transform is computable or not.

This paper investigates the possibility of approximating the spectral factor of continuous spectral densities with finite Dirichlet energy based on finitely many samples of the spectral densities. It will be shown that there exists no sampling-based method which depends continuously on the samples and which is able to approximate the spectral factor arbitrarily well for all continuous densities of finite energy. Instead, to any sampling-based approximation method there exists a large set of spectral densities so that the approximation method does not converge to the spectral factor for every spectral density in this set as the number of available sampling points is increased. Finally, the paper discusses shortly some consequences of these results. Namely, it mentions implications on the inner-outer factorization, it discusses algorithms which are based on a rational approximation of the spectral density, and it considers the Turing computability of the spectral factor.

The tone reservation method can be used to reduce the peak to average power ratio (PAPR) in orthogonal frequency division multiplexing (OFDM) transmission systems. In this paper, the tone reservation method is analyzed for OFDM with a restricted carrier set, where only the positive carrier frequencies are used. Performing a fully analytical analysis, we give a complete characterization of the information sets for which the PAPR problem is solvable. To derive our main result, we connect the PAPR problem with a geometric functional analytic property of certain spaces. Furthermore, we present applications of our theory that give guidelines for choosing the information carriers in the finite setting and discuss a probabilistic approach for selecting the carriers. In addition, it is shown that if there exists an information sequence for which the PAPR problem is not solvable, then the set of information sequences for which the PAPR problem is not solvable is a residual set.

This paper studies the possibility of approximating functions in the space of all uniformly convergent symmetric and non-symmetric Fourier series from finitely many samples of the given function. It is shown that no matter what approximation method is chosen, there always exists a residual subset such that the approximation method diverges for all functions from this subset. This general result implies that there exists no method to effectively calculate the Fourier series expansion on a digital computer for all functions from the space of uniformly convergent Fourier series. In particular, there exists no Turing computable approximation method in these spaces. (C) 2019 Elsevier Inc. All rights reserved.

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.

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 L 2 , 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.

This paper presents the recent progress in studying the algorithmic computability of capacity expressions of secure communication systems. Several communication scenarios are discussed and reviewed including the classical wiretap channel, the wiretap channel with an active jammer, and the problem of secret key generation.

We consider the compound memoryless quantum multiple-access channel (QMAC) with two sending terminals. In this model, the transmission is governed by the memoryless extensions of a completely positive and trace preserving map which can be any element of a prescribed set of possible maps. We study a communication scenario, where one of the senders aims for transmission of classical messages, while the other sender sends quantum information. Combining powerful universal random coding results for classical and quantum information transmission over point-to-point channels, we establish universal codes for the mentioned two-sender task. Conversely, we prove that the two-dimensional rate region achievable with these codes is optimal. In consequence, we obtain a multi-letter characterization of the capacity region of each compound QMAC for the considered transmission task.

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.

We determine the secrecy capacities of arbitrarily varying quantum channels (AVQCs). Both secrecy capacities 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. As an application of our result for secret message transmission over AVQCs, 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 “superactivation” for secrecy capacities of arbitrarily varying quantum channels, i.e., two quantum channels both with zero secrecy capacity, which, if used together, allow secure transmission with positive capacity. We give therewith an answer to the question “When is the secrecy capacity a continuous function of the system parameters?,” which has been listed as an open problem in quantum information problem page of the Institut für Theoretische Physik (ITP) Hannover. We also discuss the relations between the entanglement distillation capacity, the entanglement generating capacity, and the strong subspace transmission capacity for AVQCs. Ahlswede et al. made in 2013 the conjecture that the entanglement generating capacity of an AVQC is equal to its entanglement generating capacity under shared randomness assisted quantum coding. We demonstrate that the validity of this conjecture implies that the entanglement generating capacity, the entanglement distillation capacity, and the strong subspace transmission capacity of an AVQC are continuous functions of the system parameters. Consequently, under the premise of this conjecture, the secrecy capacities of an AVQC differ significantly from the general quantum capacities.

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.

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.

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.

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.

We derive universal codes for simultaneous transmission of classical messages and entanglement through quantum channels, possibly under the attack of a malignant third party. These codes are robust to different kinds of channel uncertainties. To construct such universal codes, we invoke and generalize the properties of random codes for classical and quantum message transmission through quantum channels. 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. In addition, we give dichotomy statements in which we characterize the capacity of arbitrarily varying quantum channels for simultaneous transmission of classical messages and entanglement. These include cases where the malignant jammer present in the arbitrarily varying channel model is classical (chooses channel states of the product form) and fully quantum (is capable of general attacks not necessarily of the product form).

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.