The classic teacher-student model in machine learning posits that a strong teacher supervises a weak student to improve the student's capabilities. We instead consider the inverted situation, where a weak teacher supervises a strong student with imperfect pseudolabels. This paradigm was recently brought forth by \citet{burns2023weak} and termed \emph{weak-to-strong generalization}. We theoretically investigate weak-to-strong generalization for binary and multilabel classification in a stylized overparameterized spiked covariance model with Gaussian covariates where the weak teacher's pseudolabels are asymptotically like random guessing. Under these assumptions, we provably identify two asymptotic phases of the strong student's generalization after weak supervision: (1) successful generalization and (2) random guessing. Our techniques should eventually extend to weak-to-strong multiclass classification. Towards doing so, we prove a tight lower tail inequality for the maximum of correlated Gaussians, which may be of independent interest. Understanding the multilabel setting reinforces the value of using logits for weak supervision when they are available.

Cheap spaceflight has ushered in an explosive growth era for Low Earth Orbit (LEO) satellites. While this has brought us LEO satellite megaconstellations for ubiquitious highspeed data, it has also enabled a proliferation of nanosatellites (e.g. CubeSats) launched by diverse organizations. An unfortunate side-effect is harmful interference to sensitive receivers like those of radio astronomy --- no place on Earth is safe. How can we enjoy the fruits of the satellite revolution without blinding ourselves to the secrets of the universe?

Spectrum monitoring is vital for optimizing wireless spectrum usage, minimizing interference, and ensuring efficient communication systems. In large-scale monitoring systems, the issue of trust in sensor data becomes critical. Separate from the issue of malicious actors, there must be an underlying level of trust in the basic quality of a sensor's data. A sensor can be compromised by physical obstructions, improper installation, or incorrect descriptions. This paper introduces an automated approach for evaluating RF sensor quality, leveraging airplane transponder signals to assess obstructions and other known man-made signals across frequency bands to quantify obstruction severity. Our experiments demonstrate the effectiveness of these techniques in automatically calibrating sensors without supervision.

Subramanian et al. [1] introduced an asymptotic Gaussian-features model for overparameterized multiclass classification in which the number of classes, training points, and parameters all go to infinity. They provided some achievable regions where min-norm interpolating classifiers successfully asymptotically generalize as well as conjecturing the full form of the region based on a heuristic analysis. Here, we introduce a converse for such min-norm interpolating classifiers in their model which fully matches their conjectured regions. The key technical tool is a variant of the Hanson-Wright concentration inequality that applies to the sparse bilinear forms that arise.

We study the asymptotic generalization of an overparameterized linear model for multiclass classification under the Gaussian covariates bi-level model introduced in Subramanian et al. (NeurIPS'22), where the number of data points, features, and classes all grow together. We fully resolve the conjecture posed in Subramanian et al. '22, matching the predicted regimes for which the model does and does not generalize. Furthermore, our new lower bounds are akin to an information-theoretic strong converse: they establish that the misclassification rate goes to 0 or 1 asymptotically. One surprising consequence of our tight results is that the min-norm interpolating classifier can be asymptotically suboptimal relative to noninterpolating classifiers in the regime where the min-norm interpolating regressor is known to be optimal. The key to our tight analysis is a new variant of the Hanson-Wright inequality which is broadly useful for multiclass problems with sparse labels. As an application, we show that the same type of analysis can be used to analyze the related multi-label classification problem under the same bi-level ensemble.

Via an overparameterized linear model with Gaussian features, we provide conditions for good generalization for multiclass classification of minimum-norm interpolating solutions in an asymptotic setting where both the number of underlying features and the number of classes scale with the number of training points. The survival/contamination analysis framework for understanding the behavior of overparameterized learning problems is adapted to this setting, revealing that multiclass classification qualitatively behaves like binary classification in that, as long as there are not too many classes (made precise in the paper), it is possible to generalize well even in settings where regression tasks would not generalize. Besides various technical challenges, it turns out that the key difference from the binary classification setting is that there are relatively fewer training examples of each class in the multiclass setting as the number of classes increases, making the multiclass problem ``harder'' than the binary one.

We compare classification and regression tasks in an overparameterized linear model with Gaussian features. On the one hand, we show that with sufficient overparameterization all training points are support vectors: solutions obtained by least-squares minimum-norm interpolation, typically used for regression, are identical to those produced by the hard-margin support vector machine (SVM) that minimizes the hinge loss, typically used for training classifiers. On the other hand, we show that there exist regimes where these interpolating solutions generalize well when evaluated by the 0-1 test loss function, but do not generalize if evaluated by the square loss function, i.e. they approach the null risk. Our results demonstrate the very different roles and properties of loss functions used at the training phase (optimization) and the testing phase (generalization).

Ultra-reliable, low-latency communication (URLLC) is being developed to support critical control applications over wireless networks. Exploiting spatial diversity through relays is a promising technique for achieving the stringent requirements of URLLC, but coordinating relays reliably and with low overhead is a challenge. Adaptive relay selection techniques have been proposed as a way to simplify implementation while still achieving the requirements of URLLC. Identifying good relays with low overhead and high confidence is critical for such adaptive relay selection techniques.Channel dynamics must be taken into account by adaptive relay selection algorithms because channel quality may degrade in the time it takes to estimate the relay's channel and schedule a transmission. Spatial channel dynamics are well studied in many settings such as RADAR and the fast-fading wireless channels, but less so in the URLLC context where rare events neglected in other models may be important. In this work, we perform measurements to validate channel models in the slow fading regime of interest. We compare measurements to Jakes's model and discuss the appropriateness of Jakes's model for URLLC relay selection. This is further applied to demonstrate that easily implementable relay selection techniques perform well in practical settings.Polynomial interpolation and neural-net-based algorithms were evaluated as channel prediction algorithms. These techniques perform orders of magnitude better than relay selection on average (nominal) SNR.

Many first-year undergraduate students do not have sufficient breadth of technical knowledge about subjects in Electrical Engineering (EE) and Computer Science (CS) to make informed choices toward their education. By the time students are exposed to subjects they may be interested in, the cost of switching areas of focus may be too high. With undergraduate enrollment in CS more than doubling in the past decade, many institutions lack adequate staff and infrastructure to address students' needs. To help newly enrolled students make better decisions with limited departmental resources, we present a first-semester, low-overhead survey course that covers a wide variety of topics. The class has been offered for five consecutive semesters by upper-class undergraduate volunteers with minimal faculty involvement. We report the format, content, and student feedback for the course. Our results suggest that such a class can provide new students with valuable guidance and better prepare them for an education in CS and EE.

Data-driven optimization of transmitters and receivers can reveal new modulation and detection schemes and enable physical-layer communication over unknown channels. Previous work has shown that practical implementations of this approach require a feedback signal from the receiver to the transmitter. In this paper, we study the impact of quantized feedback on data-driven learning of physical-layer communication. A novel quantization method is proposed, which exploits the specific properties of the feedback signal and is suitable for non-stationary signal distributions. The method is evaluated for linear and nonlinear channels. Simulation results show that feedback quantization does not appreciably affect the learning process and can lead to similar performance as compared to the case where unquantized feedback is used for training, even with 1-bit quantization. In addition, it is shown that learning is surprisingly robust to noisy feedback where random bit flips are applied to the quantization bits.

We introduce algorithms for online, full-information prediction that are computationally efficient and competitive with contextual tree experts of unknown complexity, in both probabilistic and adversarial settings. We incorporate a novel probabilistic framework of structural risk minimization into existing adaptive algorithms and show that we can robustly learn not only the presence of stochastic structure when it exists, but also the correct model order. When the stochastic data is actually realized from a predictor in the model class considered, we obtain regret bounds that are competitive with the regret of an optimal algorithm that possesses strong side information about both the true model order and whether the process generating the data is stochastic or adversarial. In cases where the data does not arise from any of the models, our algorithm selects models of higher order as we play more rounds. We display empirically improved \textit{overall prediction error} over other adversarially robust approaches.

A continuing mystery in understanding the empirical success of deep neural networks has been in their ability to achieve zero training error and yet generalize well, even when the training data is noisy and there are more parameters than data points. We investigate this "overparametrization" phenomena in the classical underdetermined linear regression problem, where all solutions that minimize training error interpolate the data, including noise. We give a bound on how well such interpolative solutions can generalize to fresh test data, and show that this bound generically decays to zero with the number of extra features, thus characterizing an explicit benefit of overparameterization. For appropriately sparse linear models, we provide a hybrid interpolating scheme (combining classical sparse recovery schemes with harmless noise-fitting) to achieve generalization error close to the bound on interpolative solutions.

Interactive, immersive, and other timing-critical applications demand ultra-reliable low-latency communication (URLLC). To build wireless communication systems that can support these applications, understanding the relevant characteristics of the wireless medium is paramount. Although wireless channel characteristics and dynamics have been extensively studied, it is important to revisit these concepts in the context of the strict demands of low-latency and ultra-high reliability. In this paper, we bring a modeling approach from robust control to wireless communication-the wireless channel characteristics are given a nominal model around which we allow for some quantified uncertainty. We propose certain key URLLC-relevant parameters along which the model uncertainty is to be bounded. To validate the nominal model of the spatially independent quasi-static Rayleigh fading, we take an in-depth look at the spatial and temporal correlations based on Jakes' model. We find that although the Rayleigh fading process is band-limited, the quasi-static assumption is not safe for relay selection even well within a single coherence time. We also find that under reasonable conditions, the spatial correlation of channels provide a fading distribution that is not too far off from an independent spatial fading model. In addition, we look at the impact of these channel models on cooperative communication-based systems. We find that while spatial-diversity-based techniques are necessary to combat the adverse effects of fading, time-diversity-based techniques are necessary to be robust against unmodeled errors. Robust URLLC systems need to operate with both an adequate SNR margin and a time margin through repetitions.

Feedback control actively dissipates uncertainty from a dynamical system by means of actuation. We develop a notion of “control capacity” that gives a fundamental limit (in bits) on the rate at which a controller can dissipate the uncertainty from a system, i.e., stabilize to a known fixed point. We give a computable single-letter characterization of control capacity for memoryless stationary scalar multiplicative actuation channels. Control capacity allows us to answer questions of stabilizability for scalar linear systems: a system with actuation uncertainty is stabilizable if and only if the control capacity is larger than the log of the unstable open-loop eigenvalue. For second-moment senses of stability, we recover the classic uncertainty threshold principle result. However, our definition of control capacity can quantify the stabilizability limits for any moment of stability. Our formulation parallels the notion of Shannon's communication capacity and thus yields both a strong converse and a way to compute the value of side information in control.

Ultra-reliable, low-latency wireless communication is essential to enable critical and interactive applications. The cooperative communication schemes for such ultra-reliable communication must harvest multi-user diversity to achieve their specifications. The underlying low-latency space-time codes for a large number of users (> 10) place burdens on practical implementations due to the large number of simultaneous relays they must use. To address this, we propose an adaptive relay selection technique that selects a small set of good relays, instead of using every available radio to relay. Using our simple relay-selection schemes, we can support a network with 30 nodes requiring system failure probability under 10 -9and 2ms latency with only 3 simultaneously active relays per message. In contrast, in the absence of adaptive relay selection, we must rely on 13 relays to achieve the same reliability. To arrive at such relay selection schemes, we revisit the fading dynamics of wireless channels in the context of ultra-high reliability. Contrary to what has been claimed in the literature, we find that standard Rayleigh fading processes are not bandlimited. However, these fading processes are fairly predictable on the short time scales of the regime of interest.

Recent advances in dynamic spectrum sharing have led to renewed focus on the structure of regulatory games between a primary user and a secondary user of a spectrum band. The primary user has to decide to what extent it invokes the services of the regulator, and the secondary user has to decide how to operate in the spectrum band. This paper builds on a mathematical model for light-handed regulation using “spectrum jails” to show that the order of play and amount of commitment matters. A primary that can commit to its strategy before the game is able to increase its equilibrium payoff, even when the secondary best responds to the committed strategy. We compare the ensuing Stackelberg game with the simultaneous primary-secondary game. We also introduce a new concept of partial commitment by which the primary can only commit to a range of strategies using a finite number of bits. We show explicitly that the more the primary commits to, the more it benefits, and that Stackelberg commitment can be understood as a limit of infinite “commitment bits”.

High-performance industrial automation systems rely on tens of simultaneously active sensors and actuators and have stringent communication latency and reliability requirements. Current wireless technologies, such as Wi-Fi, Bluetooth, and LTE are unable to meet these requirements, forcing the use of wired communication in industrial control systems. This paper introduces a wireless communication protocol that capitalizes on multiuser diversity and cooperative communication to achieve the ultra-reliability with a low-latency constraint. Our protocol is analyzed using the communication-theoretic delay-limitedcapacity framework and compared with baseline schemes that primarily exploit frequency diversity. For a scenario inspired by an industrial printing application with 30 nodes in the control loop, 20-B messages transmitted between pairs of nodes and a cycle time of 2 ms, an idealized protocol can achieve a cycle failure probability (probability that any packet in a cycle is not successfully delivered) lower than 10-9with nominal SNR below 5 dB in a 20-MHz wide channel.

Cooperative communication to extract multi-user diversity and network coding are two ideas for improving wireless protocols. These ideas can be exploited to design protocols for low-latency high-reliability communication for control. Given the high-performance constraints for this communication, it is critical, to understand how sensitive such protocols are to modeling assumptions. We examine the impact of channel reciprocity, quasi-static fading, and the spatial independence of channel fades in this paper. This paper uses simple models to explore the performance sensitivity to assumptions. It turns out that wireless network-coding is moderately sensitive to channel reciprocity and non-reciprocity costs about 2dB SNR. The loss of the quasi-static fading assumption has a similar cost for the network coding based protocol but has a negligible effect on the protocol that doesn't use network coding. The real sensitivity of cooperative communication protocols is to the spatial independence assumptions. Capping the amount of independence to a small number degrades performance but perhaps more surprisingly, a simple Gilbert-Elliott-inspired model shows that having a random amount of independence can also severely impact performance.

The Internet of Things (IoT) envisions simultaneous sensing and actuation of numerous wirelessly connected devices. Emerging human-in-the-loop applications demand low-latency high-reliability communication protocols, paralleling the requirements for high-performance industrial control. This paper introduces a wireless communication protocol based on network coding that in conjunction with cooperative communication techniques builds the necessary diversity to achieve the target reliability. The proposed protocol, XOR-CoW, is analyzed by using a communication theoretic delay-limited-capacity framework and compared to different realizations of previously proposed protocols without network coding. The results show that as the network size or payload increases, XOR-CoW gains advantage in minimum SNR to achieve the target latency. For a scenario inspired by an industrial printing application with 30 nodes in the control loop, total information throughput of 4.8 Mb/s, 20MHz of bandwidth and cycle time under 2 ms, the protocol can robustly achieve a system probability of error better than 10-9with a nominal SNR less than 2 dB with Rayleigh fading.

While some whitespace devices will be self-sufficient (“masters”), others will rely on help from other devices in order to access the whitespaces (“slaves”). Currently, this help is provided by a single master device. In this paper, we argue that (1) this assistance need not be provided by a single device and (2) the assisting device need not be a whitespace device. Instead, we can think of the “slave” as being helped by a whitespace device support network, i.e. a variety of devices which each supply a piece of the whitespace access puzzle. We begin by identifying the three key components of a whitespace device support network. We describe each component in detail before giving example deployments which are only possible with a support network. In one example, a smartphone plays the role of the “master” by providing the “slave” device with a location as well as a means to access the database. Finally, we remark on the advantages that this separation provides when it comes to certification. In particular, regulators can now perform unit tests to verify that each component operates correctly on its own, rather than certifying an entire device all at once.

Spectrum has traditionally been allocated for single uses and by now most of the “prime” spectrum has well-entrenched incumbent users. When a new service needs spectrum, there are two qualitatively distinct ways of making bandwidth available for it. A swath of incumbent users can be removed from a band, with the cleared band being reallocated for the new service. Alternatively, the new users can be allowed to utilize the interstitial spectrum holes (i.e. whitespaces) between incumbent users, with the requirement to protect the incumbents' QoS. But these can also be used in combination by partially clearing a band and opening up the rest for whitespace-style sharing. In this case, the ability of regulators to “repack” incumbents, e.g. alter their operating channels, can reduce the need to evict them. An open question has been how whitespaces and partial spectrum clearing interact with each other and the ability to repack incumbents. Do efficient repacks completely eliminate whitespaces? The USA FCC's upcoming incentive auction in the TV bands is the first large-scale attempt to repack a major band of spectrum in order to clear spectrum for LTE. This auction is meant to navigate the tradeoff between incumbent TV services and LTE networks. In preparation, the FCC has made a large and complex data set of repacking constraints available for the first time. We have repurposed this data and built our own repacking engine in order to study a more general version of the tradeoff between whitespaces and cleared spectrum. We conclude that (1) repacking enables clearing of significantly more spectrum than just removing incumbents; (2) the total amount of spectrum available for new uses is relatively insensitive to how incumbents are removed; (3) efficient repackings basically trade whitespace spectrum for cleared spectrum; (4) even the most efficient repackings leave plenty of whitespace - an amount that can be comparable with the amount of cleared spectrum.

The Internet of Things envisions not only sensing but also actuation of numerous wirelessly connected devices. Seamless control with humans in the loop requires latencies on the order of a millisecond with very high reliabilities, paralleling the requirements for high-performance industrial control. Today's practical wireless systems cannot meet these reliability and latency requirements, forcing the use of wired systems. This paper introduces a wireless communication protocol, dubbed “Occupy CoW,” based on cooperative communication among nodes in the network to build the diversity necessary for the target reliability. Simultaneous retransmission by many relays achieves this without significantly decreasing throughput or increasing latency. The protocol is analyzed using the communication theoretic delay-limited-capacity framework and compared to baseline schemes that primarily exploit frequency diversity. In particular, we develop a novel “diversity meter” designed to measure “effective diversity” in the non-asymptotic regime. For a scenario inspired by an industrial printing application with 30 nodes in the control loop, total information throughput of 4.8 Mb/s, and cycle time under 2 ms, the protocol can robustly achieve a system probability of error better than 10−9with nominal SNR below 5 dB.

This paper presents a notion of “control capacity” that gives a fundamental limit on the control of a system through an unreliable actuation channel. It tells us how fast we can reliably actively dissipate uncertainty in a system through that actuation channel. We give a computable single-letter characterization for scalar systems with memoryless stationary multiplicative actuation channels. The sense of control capacity is tight for answering questions of stabilizability for scalar linear systems - a system is stabilizable through an actuation channel if and only if the control capacity of that actuation channel is larger than the log of the unstable open-loop eigenvalue. For second-moment senses of stability, our result recovers the classic uncertainty-threshold principle result. However, our formulation can also deal with any other moment. The limits of higher and higher moment senses of stability correspond to a “zero-error” sense of control capacity and taking the limit to weaker-andweaker moments corresponds to a “Shannon” sense of control capacity.

We consider the problem of information embedding where the encoder modifies a white Gaussian host signal in a power-constrained manner to encode a message, and the decoder recovers both the embedded message and the modified host signal. This partially extends the recent work of Sumszyk and Steinberg to the continuous-alphabet Gaussian setting. Through a control-theoretic lens, we observe that the problem is a minimalist example of what is called the triple role of control actions. We show that a dirty-paper-coding strategy achieves the optimal rate for perfect recovery of the modified host and the message for any message rate. For imperfect recovery of the modified host, by deriving bounds on the minimum mean-square error (MMSE) in recovering the modified host signal, we show that Dirty-Paper Coding-based strategies are guaranteed to attain within a uniform constant factor of 16 of the optimal weighted sum of power required in host signal modification and the MMSE in the modified host signal reconstruction for all weights and all message rates. When specialized to the zero-rate case, our results provide the tightest known lower bounds on the asymptotic costs for the vector version of a famous open problem in decentralized control: the Witsenhausen counterexample. Numerically, this tighter bound helps us characterize the asymptotically optimal costs for the vector Witsenhausen problem to within a factor of 1.3 for all problem parameters, improving on the earlier best known bound of 2.

The Haroutunian exponent arises in the study of channel reliability functions for both block coding with feedback and fixed-delay coding without feedback. For asymmetric channels, such as the Z-channel, the Haroutunian exponent is strictly larger than the sphere-packing exponent. The spherepacking exponent is believed to be an upper bound for the reliability function in the two aforementioned communication problems, but in attempting to prove this, one gets stuck at the Haroutunian exponent because of entanglements between the channel behavior and the input distribution. In this paper, we present a characteristic of the Haroutunian exponent that differentiates it from the random coding and sphere-packing exponents. We consider the parallel channel, the repeated use of the original discrete memoryless channel independently some number of times. It is well known that the capacity of the parallel channel is L times the capacity of the original channel, and the random coding and sphere-packing exponents of the L-use parallel channel decompose into L times the exponents of the original channel. The main result of this paper is to show that the (appropriately normalized) Haroutunian exponent of the parallel channel asymptotically decomposes to the sphere-packing exponent of the original channel, as opposed to the Haroutunian exponent of the original channel. This fact is then used to prove two results. First, an upper bound for the reliability function for fixed blocklength coding with delayed feedback is proved. This upper bound converges to the sphere-packing exponent as the delay in the feedback path tends to infinity. Second, the reliability function for fixed delay coding without feedback is shown to be upper bounded by the sphere-packing exponent.

High-performance industrial control systems with tens to hundreds of sensors and actuators use wired connections between all of their components because they require low-latency, high-reliability links to maintain stability; however, the wires cause many mechanical problems that moving to wireless links would solve. No existing or proposed wireless system can achieve the latency and reliability required by the control algorithms because they are designed for either high-throughput or low-power communication between a pair or a small number of terminals. A preliminary wireless system architecture is proposed that focuses on low-latency operation through the use of reliable broadcasting, semi-fixed resource allocation, and low-rate coding. For an industrial printer application with 30 nodes in the control loop and a moderate information throughput of 4.8Mb/s, the system can achieve latencies under 2ms for SNRs above 7dB.

As in portfolio theory, we can think of the value of side-information in a control system as the change in the “growth rate” due to side-information. A scalar counterexample (motivated by carry-free deterministic models) shows the value of side-information for control does not exactly parallel the value of side-information for portfolios. Mutual-information does not seem to be a bound here. The concept is further explored through a spinning vector control system that is re-oriented at each time so that the control or observation direction is partially unknown. The value of side-information can be calculated in this setup and it behaves quite differently in a control vs. estimation context. A second example considers the problem of vector control over a (scalar) erasure channel, the dual problem to the estimation problem of intermittent Kalman Filtering. The value of information here is measured through the change in the critical packet-drop probability for the system. While non-causal side-information regarding the packet arrivals does not affect the critical probability for the estimation problem, we find that it can generically be very valuable for the control problem - it seems to change the scaling behavior for the control counterpart to what would be considered the “high SNR limit” in communication problems.

Distributed source coding is traditionally viewed in a block coding context wherein all source symbols are known in advance by the encoders. However, many modern applications to which distributed source coding ideas are applied, are better modeled as having streaming data. In a streaming setting, source symbol pairs are revealed to separate encoders in real time and need to be reconstructed at the decoder with subject to some tolerable end-to-end delay. In this paper, a causal sequential random binning encoder is introduced and paired with maximum likelihood (ML) and universal decoders. The latter uses a novel weighted empirical suffix entropy decoding rule. We derive a lower bounds on the error exponent with delay for each decoder. We also provide upper bounds for the special case of streaming with decoder side information and discuss when upper and lower bounds match. We show that both ML and universal decoders achieve the same (positive) error exponents for all rate pairs inside the Slepian-Wolf achievable rate region. The dominant error events in streaming are different from those in block-coding and result in different exponents. Because the sequential random binning scheme is also universal over delays, the resulting code eventually reconstructs every source symbol correctly with probability one.

In linear function computation, multiple source nodes communicate across a relay network to a single destination whose goal is to recover linear functions of the original source data. When the relay network is a linear deterministic network, a duality relation is established between function computation and broadcast with common messages. Using this relation, a compact sufficient condition is found describing those cases where the cut-set bound is tight. These insights are used to develop results for the case where the relay network contains Gaussian multiple-access channels. The proposed scheme decouples the physical and network layers. Using lattice codes for both source quantization and computation in the physical layer, the original Gaussian sources are converted into discrete sources and the Gaussian network into a linear deterministic network. Network codes for computing functions of discrete sources across the deterministic network are then found by applying the duality relation. The distortion for computing the sum of an arbitrary number of independent Gaussian sources over the Gaussian network is proven to be within a constant factor of the optimal performance. Furthermore, the constant factor results are extended to include asymmetric functions for the case of two sources.

We provide fundamental information-theoretic bounds on the required circuit wiring complexity and power consumption for encoding and decoding of error-correcting codes. These bounds hold for all codes and all encoding and decoding algorithms implemented within the paradigm of our VLSI model. This model essentially views computation on a 2-D VLSI circuit as a computation on a network of connected nodes. The bounds are derived based on analyzing information flow in the circuit. They are then used to show that there is a fundamental tradeoff between the transmit and encoding/decoding power, and that the total (transmit + encoding + decoding) power must diverge to infinity at least as fast as cube-root of log 1/pe, where Peis the average block-error probability. On the other hand, for bounded transmit-power schemes, the total power must diverge to infinity at least as fast as square-root of log 1/Pedue to the burden of encoding/decoding.

The generalized deterministic models recently proposed by Niesen and Maddah-Ali [1] successfully capture real-interference alignment as observed in Gaussian models. Simpler deterministic models, like ADT models [2], cannot demonstrate this phenomenon because they are limited in the set of channel gains they can model. This paper reinterprets the Niesen and Maddah-Ali models through the lens of carry-free operations. We further explore these carry-free models by considering i.i.d. unknown fading networks. In the unknown fading context, a carry-free model can be further simplified to a max-superposition model, where signals are superposed by a nonlinear max operation. Unlike in relay-networks with known fading and linear superposition, we find that decode-and-forward can perform arbitrarily better than compress-and-forward in max-superposition relay networks with unknown fading.

The idea of modeling an unknown channel using a broadcast channel was first introduced by Cover1in 1972. This paper builds on his line of thought to consider priority encoding of communication over unknown channels without feedback, using fixed-length codes and from a single-shot, individual channel perspective. A ratio-regret metric is used to understand how well we can perform with respect to the actual channel realization.

We investigate the behavior of aggregate interference generated by cognitive radios. We find that a phase change occurs in the behavior of aggregate interference as the density of the white-space devices is increased for a fixed protection radius. For a deterministic grid model, the mean of the interference behaves differently depending on whether the problem is one of ``near field'' or ``far field''. For a more realistic Poisson-placement model, we show that the shape of the distribution of interference changes from a heavy-tailed distribution to something that is approximately Gaussian. Investigating models with random fading of signal at each transmitter, we show that fading can alter the boundary of near and far fields. These phase-changes suggest that in designing rules for whitespace devices, the FCC rules may have to be sensitive to whether the situation is one of near or far field. For Poisson placement of nodes, our results also suggest that central limit theorem-style arguments might help in obtaining a conceptually and computationally improved understanding of interference aggregation.

In decentralized control, a control agent often has the possibility of `signaling,' i.e. the ability to affect the observations of other agents, enabling the agents to `talk.' Signaling has been noted to make many decentralized control problems, in particular the celebrated Witsenhausen counterexample, hard. In this paper, in order to refine the understanding of signaling, we identify two separate notions of signaling that relate to Witsenhausen's counterexample: source-simplification and the presence of an implicit communication channel. We isolate the two aspects aspect of signaling by constructing two variations on the counterexample. Studying these variations, we conclude that the source-simplification aspect plays the more significant role in the counterexample. As a demonstration of the utility of this refinement, we formulate and address finite-time-horizon versions of the counterexample and of our second variation on the counterexample. For these problems, we use the understanding developed for Witsenhausen's counterexample to obtain asymptotically-approximately- optimal strategies in some cases. Finally, we suggest a thermodynamic analogy to signaling in the counterexample paralleling a similar analogy for Kalman filtering proposed by Mitter and Newton.

In the study of error exponents, the Haroutunian exponent is encountered as an upper bound for several point-to-point communication problems over DMCs including block coding with feedback and fixed-delay coding. For symmetric channels, such as the BSC or BEC, the Haroutunian exponent is equal to the sphere-packing exponent. But for asymmetric channels, such as the Z-channel, the Haroutunian bound is strictly larger than the sphere-packing exponent. It is generally believed that the sphere-packing bound should hold for these problems, even though they are different from the problem of block coding without feedback. The fundamental difficulty in these problems is that the distribution of the input is not known during the error event, and unlike symmetric channels, there is no `universally good' input distribution like the uniform distribution. The result is that a worst-case assumption is made on the input distribution to give the Haroutunian bound, even though the resulting input distribution is useless for communication purposes. In order to make progress on this issue, we study an extended notion of fixed-delay codes called anytime codes, a class of codes that indirectly enforce the property that nontrivial communication is attempted during the error event. For this class of codes, we give a new upper bound to the error exponent that strictly improves on the Haroutunian bound for asymmetric channels. While the new exponent still does not reach sphere-packing, we show that the ratio of the two exponents approaches 1 as the rate approaches capacity for Z-channels. This fact may have an interesting consequence for the viewpoint of maximum achievable rate for a given delay and desired error probability. Additionally, the improved exponent yields a tighter bound for a notion of sufficiency of a channel for control purposes.

Can we design a communication network just like a huge linear time-invariant filter? To answer this question, we generalize the celebrated mincut-maxflow theorem to linear time-invariant networks where edges are labeled with transfer functions instead of integer capacity constraints. We prove that when the transfer functions are linear time-invariant, the fundamental design limit, mincut, is achievable by a linear time-invariant scheme regardless of the topology of the network. Whereas prior works are based on layered networks, our proof has a novel way of converting an arbitrary relay network to an equivalent acyclic single-hop relay network, which we call Network Linearization. This theorem also reveals a strong connection between network coding and linear system theory.

Optimal control strategies for decentralized control problems may involve internal communication between controllers. We think of such internal communication as implicit, since the messages being sent are endogenous to the system and not externally specified. Recently, Grover and Sahai [1] applied information-theoretic techniques to provide an approximately optimal scheme for the Witsenhausen counterexample: one of the simplest models of a decentralized control system. This paper examines a MAC-inspired extension of the Witsenhausen counterexample. Deterministic modeling techniques based on the work by Avestimehr at al. [2] feature centrally in the strategy development. This example illustrates that “Information is in the eye of the beholder”, and we find “rate gains” in the context of implicit communication. These are not observed in the original Witsenhausen counterexample.

Traditional communication theory focuses on minimizing transmit power. However, communication links are increasingly operating at shorter ranges where transmit power can be significantly smaller than the power consumed in decoding. This paper models the required decoding power and investigates the minimization of total system power from two complementary perspectives. First, an isolated point-to-point link is considered. Using new lower bounds on the complexity of message-passing decoding, lower bounds are derived on decoding power. These bounds show that 1) there is a fundamental tradeoff between transmit and decoding power; 2) unlike the implications of the traditional "waterfall" curve which focuses on transmit power, the total power must diverge to infinity as error probability goes to zero; 3) Regular LDPCs, and not their known capacity-achieving irregular counterparts, can be shown to be power order optimal in some cases; and 4) the optimizing transmit power is bounded away from the Shannon limit. Second, we consider a collection of links. When systems both generate and face interference, coding allows a system to support a higher density of transmitter-receiver pairs (assuming interference is treated as noise). However, at low densities, uncoded transmission may be more power-efficient in some cases.

The problem of finding the rate-distortion function of an arbitrarily varying source (AVS) composed of a finite number of memoryless subsources is revisited. Berger's 1971 paper “The Source Coding Game” solves this problem when the adversary is allowed only strictly causal access to the subsource realizations. The case when the adversary has access to the subsource realizations non-causally is considered. This new rate-distortion function is determined to be the maximum of the rate-distortion function over a set of independent and identically distributed (IID) random variables that can be simulated by the adversary. The results are extended to allow for partial or noisy observations of subsource realizations. The model is further explored by attempting to find the rate-distortion function when the `adversary' is actually helpful. Finally, a bound is developed on the uniform continuity of the IID rate-distortion function for finite-alphabet sources. The bound is used to give a sufficient number of distributions that need to be sampled to compute the rate-distortion function of an AVS to within a desired accuracy. The bound is also used to give a rate of convergence for the estimate of the rate-distortion function for an unknown IID source.

The purpose of this paper is to develop an information-theoretic understanding of the tradeoffs between decoder power, probability of error and decoding throughput. We start by considering the power consumed in the decoder circuit's interconnects, modeled as a lumped capacitor and resistor. After making simplifying assumptions about the decoder circuit, we use a sphere-packing technique to lower bound the decoding error probability for a given number of clock-cycles (or iterations). The analysis can be used to give lower bounds on probability of error versus total decoding power at a fixed decoding throughput.

We consider the problem of two-stage signal cancelation based on noisy observations. This problem turns out to be an extension of the Witsenhausen counterexample - a famous open problem in distributed control. Cost is imposed on the power expended by the first controller, and the residual signal after the actions of the two controllers. Along the lines of a recent approximate solution to the Witsenhausen counterexample, we provide an approximate solution to this distributed signal cancelation problem to within a constant factor. This approximation holds uniformly over all problem parameters and for all vector lengths.

The problem considered here is that of wireless information and power transfer across a noisy coupled-inductor circuit, which is a frequency-selective channel with additive white Gaussian noise. The optimal tradeoff between the achievable rate and the power transferred is characterized given the total power available. The practical utility of such systems is also discussed.

The issue of whether feedback can significantly increase reliability in the fixed-length channel code setting is further investigated. This paper considers the problem of error exponents for block codes with noiseless, delayed feedback used over discrete memoryless channels (DMCs) - including asymmetric channels with and without zeros in their transition matrix. We show that when output feedback is given to the encoder with a delay of T symbols, the error exponent is upper bounded by Esp(R - O((log T)/T )) + O((log T)/T ), where Espdenotes the sphere-packing exponent.

The utility of limited feedback for coding over an individual sequence of discrete memoryless channels is investigated. This study complements recent results showing how limited or noisy feedback can boost the reliability of communication. A strategy with fixed input distributionPis given that asymptotically achieves rates arbitrarily close to the mutual information induced byPand the state-averaged channel. When the capacity-achieving input distribution is the same over all channel states, this achieves rates at least as large as the capacity of the state-averaged channel, sometimes called the empirical capacity.

The problem of minimizing the total (transmit and decoding) energy required for communicating over a two-receiver Gaussian broadcast channel is investigated. For achieving a specified rate-tuple, joint broadcast schemes (e.g. superposition coding) require smaller transmit energy per-bit than the conceptually simpler time-division multiplexing (TDM) based schemes. However, for short distance communication, the energy expended in the decoding can be comparable to that required in the transmission. Two technical advances are introduced to understand these energy costs: (a) an improvement on the best known outer bounds on the error exponents for the Gaussian broadcast problem, and (b) a finer analysis to have these bounds hold for neighborhood sizes instead of block-lengths. Using these results, it is then shown that in some typical short and moderate distance communication scenarios, time-division multiplexing saves on the decoding energy, thereby likely requiring smaller total energy than any joint broadcasting scheme for achieving the target rate and error probabilities. Further, we observe that TDM outperforms joint schemes by larger margins when the ratio of the distances of the receivers from the transmitter is closer to 1.

Recently, we considered a vector version of Witsenhausen's counterexample and used a new lower bound to show that in that limit of infinite vector length, certain quantization-based strategies are provably within a constant factor of the optimal cost for all possible problem parameters. In this paper, finite vector lengths are considered with the vector length being viewed as an additional problem parameter. By applying the ldquosphere-packingrdquo philosophy, a lower bound to the optimal cost for this finite-length problem is derived that uses appropriate shadows of the infinite-length bounds. We also introduce lattice-based quantization strategies for any finite length. Using the new finite-length lower bound, we show that the lattice-based strategies achieve within a constant factor of the optimal cost uniformly over all possible problem parameters, including the vector length. For Witsenhausen's original problem - which corresponds to the scalar case - lattice-based strategies attain within a factor of 8 of the optimal cost. Based on observations in the scalar case and the infinite-dimensional case, we also conjecture what the optimal strategies could be for any finite vector length.

ldquoSpectrum holesrdquo represent the potential opportunities for noninterfering (safe) use of spectrum and can be considered as multidimensional regions within frequency, time, and space. The main challenge for secondary radio systems is to be able to robustly sense when they are within such a spectrum hole. To allow a unified discussion of the core issues in spectrum sensing, the ldquoweighted probability of area recoveredrdquo (WPAR) metric is introduced to measure the performance of a sensing strategy; and the ldquofear of harmful interferencerdquoFHImetric is introduced to measure its safety. These metrics explicitly consider the impact of asymmetric uncertainties (and misaligned incentives) in the system model. Furthermore, they allow a meaningful comparison of diverse approaches to spectrum sensing unlike the traditional triad of sensitivity, probability of false-alarmPFA, and probability of missed-detectionPMD. These new metrics are used to show that fading uncertainty forces the WPAR performance of single-radio sensing algorithms to be very low for small values ofFHI, even for ideal detectors. Cooperative sensing algorithms enable a much higher WPAR, but only if users are guaranteed to experience independent fading. Lastly, in-the-field calibration for wide-band (but uncertain) environment variables (e.g., interference and shadowing) can robustly guarantee safety (lowFHI) even in the face of potentially correlated users without sacrificing WPAR.

We consider the lossless encoding of two simultaneous sources. The encoder may choose to discriminate against one source and hence the error exponents for the two sources can be different. The goal of this paper is to understand the region of achievable error-exponent pairs for lossless source coding. In the fixed-block-length case, the error exponent region is completely characterized and is found to be relatively trivial. However, in the streaming context, it is shown that there exists a non-trivial trade-off between the two error exponents. Both an inner bound and an outer bound are given for that case, but they do not match. The outer bound comes from a multi-stream version of the uncertainty-focusing bound.

A green code attempts to minimize the total energy per-bit required to communicate across a noisy channel. The classical information-theoretic approach neglects the energy expended in processing the data at the encoder and the decoder and only minimizes the energy required for transmissions. Since there is no cost associated with using more degrees of freedom, the traditionally optimal strategy is to communicate at rate zero. In this work, we use our recently proposed model for the power consumed by iterative message passing. Using generalized sphere-packing bounds on the decoding power, we find lower bounds on the total energy consumed in the transmissions and the decoding, allowing for freedom in the choice of the rate. We show that contrary to the classical intuition, the rate for green codes is bounded away from zero for any given error probability. In fact, as the desired bit-error probability goes to zero, the optimizing rate for our bounds converges to 1.

In computer vision, an active vision source is a sensor that explores its environment in an active way, deciding to investigate parts of the environment in greater depth based on what it currently sees. We study the problem of determining the rate required to compress the output of an active vision source to within a desired fidelity. In order to make the problem analytically tractable, we assume that the environment is memoryless and gain insights into the distinction between compression of passive and active sources. We show that modelling of the sources is crucial by considering two extreme cases: adversarially active sources and helpful active sources. The theory of arbitrarily varying sources is useful for these purposes and we expand on it by allowing the party controlling the variation in the source to have partial or noisy observations of the environment. We give several examples showing that there is a large difference in the rate required to compress active sources that are adversarially modelled and active sources that are jointly optimized with the coding system. The results suggest that when active sources are part of a networked system where rate comes at a premium, large savings can be reaped by jointly optimizing the coding system with the computer vision system.

It is well known that the rate-distortion function for a finite alphabet IID source with distribution p, denoted R(p,D), is uniformly continuous in its arguments. We prove an explicit bound on |R(p,D) - R(q,D)| for distributions p, q in terms of the variational distance parp-qpar1. A simple and elementary proof shows that |R(p,D) - R(q,D)| = O(-parp - qpar1log parp - qpar1), with constants depending on the distortion measure. The uniform continuity of the rate-distortion function has the same behavior as the uniform continuity of entropy in the order sense. The bounds are used for several applications. First, a simple sampling algorithm is presented to compute the rate-distortion function for an arbitrarily varying source to within a given accuracy. The uniform continuity bound is used here to roughly quantify the tradeoff between complexity and accuracy. Second, we comment on the problem of approximating the rate-distortion function for an unknown IID source to within a desired precision.

Though the schemes are different, both Horstein's and Kudryashov's non-block strategies for communication with feedback over the binary-symmetric channel asymptotically achieve the identical reliability function (error exponent); a function that displays some curious features. For positive rates it is strictly larger than Burnashev's reliability function and transitions discontinuously at the channel capacity from a strictly positive value to zero. The purpose of this paper is to connect this reliability function to familiar coding contexts and to demonstrate that it provides an upper bound on the error exponents achievable in these contexts. We first show that this function gives a lower bound on the minimum probability of decoding error across codewords in a block-coding context with (or without) feedback. We then show that the same reliability function also gives an upper bound on the maximum probability of bit error in a non-block "streaming" context where noiseless feedback is available and the destination is (occasionally) allowed to declare erasures (per Forney). The basic insight underlying the bound leads to the moniker the "hallucination" bound.

For output-symmetric discrete memoryless channels (DMCs) at even moderately high rates, fixed-block-length communication systems show no improvements in their error exponents with feedback. This paper studies systems with fixed end-to-end delay and shows that feedback generally provides dramatic gains in the error exponents. A new upper bound (the uncertainty-focusing bound) is given on the probability of symbol error in a fixed-delay communication system with feedback. This bound turns out to have a form similar to Viterbi's bound used for the block error probability of convolutional codes as a function of the fixed constraint length. The uncertainty-focusing bound is shown to be asymptotically achievable with noiseless feedback for erasure channels as well as for any output-symmetric DMC that has strictly positive zero-error capacity. Furthermore, it can be achieved in a delay-universal (anytime) fashion even if the feedback itself is delayed by a small amount. Finally, it is shown that for end-to-end delay, it is generally possible at high rates to beat the sphere-packing bound for general DMCs — thereby providing a counterexample to a conjecture of Pinsker.

We consider the problem of lossy source coding under a peak distortion measure in which source symbols are revealed to the encoder in real time and need to be reconstructed by the decoder within a fixed end-to-end delay. We investigate the tradeoff between end-to-end delay and the probability of distortion violation. As in the lossless case, the delay-constrained error (distortion-violation) exponent is generally much higher than the fixed-block coding case.

Recently, Shayevitz and Feeler introduced an individual sequence formulation of channel coding under model uncertainty and an elegant coding strategy that adapts Horstein's scheme to this setting to achieve the empirical capacity of the channel. Their scheme requires both full-rate output feedback and common randomness. We present a strategy in the style of Hybrid ARQ that requires no output feedback by using common randomness and zero-rate active feedback. This strategy still asymptotically achieves the empirical capacity.

A transmitter may have non-causal knowledge of the interference signal being transmitted by another user. Recently, Tarokh and others have raised the possibility of exploiting this knowledge to increase the data rates of a cognitive radio. However, there is a difference between knowing the signal transmitted by the primary and the actual interference at our receiver since there is a wireless channel between these two points. This raises the interesting problem of finding the achievable rates for a compound Gel'fand-Pinsker channel. The problem was addressed recently in the work by Mitran et al, where the authors gave some upper and lower bounds to the achievable rates, with an emphasis on fading channels. But the upper bounds in that work are sometimes non-computable. In this work, we derive computable upper bounds on the outage capacity for a channel where the primary signal can be Rayleigh faded at our receiver.

Berger's paper 'The Source Coding Game', IEEE Trans. Inform. Theory, 1971, considers the problem of finding the rate-distortion function for an adversarial source comprised of multiple known IID sources. The adversary, called the 'switcher', was allowed only causal access to the source realizations and the rate-distortion function was obtained through the use of a type covering lemma. In this paper, the rate-distortion function of the adversarial source is described, under the assumption that the switcher has non-causal access to all source realizations. The proof utilizes the type covering lemma and simple conditional, random 'switching' rules. The rate-distortion function is once again the maximization of the R(D) function for a region of attainable IID distributions.

Cognitive Radios have been advanced as a technology for the opportunistic use of under-utilized spectrum since they are able to sense the spectrum and use frequency bands if no Primary user is detected. However, the required sensitivity is very demanding since any individual radio might face a deep fade. We propose light-weight cooperation in sensing based on hard decisions to mitigate the sensitivity requirements on individual radios. We show that the "link budget" that system designers have to reserve for fading is a significant function of the required probability of detection. Even a few cooperating users (~10-20) facing independent fades are enough to achieve practical threshold levels by drastically reducing individual detection requirements. Hard decisions perform almost as well as soft decisions in achieving these gains. Cooperative gains in a environment where shadowing is correlated, is limited by the cooperation footprint (area in which users cooperate). In essence, a few independent users are more robust than many correlated users. Unfortunately, cooperative gain is very sensitive to adversarial/failing Cognitive Radios. Radios that fail in a known way (always report the presence/absence of a Primary user) can be compensated for by censoring them. On the other hand, radios that fail in unmodeled ways or may be malicious, introduce a bound on achievable sensitivity reductions. As a rule of thumb, if we believe that 1/N users can fail in an unknown way, then the cooperation gains are limited to what is possible with N trusted users.

The traditional view of source coding with side information is in the block coding context in which all the source symbols are known in advance by the encoder. We instead consider a sequential setting in which source symbols are revealed to the encoder in real time and need to be reconstructed at the decoder within a certain fixed delay. We derive an upper bound on the reliability function with delay that considers the errors induced by atypically strange side-information. It is shown to be tight for certain "symmetric" sources in low rate regime

We show how to exploit a noisy feedback link to implement high-reliability communication. We specify a variable-length coding strategy that achieves the error exponent (in delay) of erasure decoding using any noisy feedback channel which has a positive zero-rate random coding error exponent. Building on this result, we give a second approach that, depending only on the capacity of the feedback link, achieves an error exponent up to half of the Burnashev exponent - the maximum exponent that can be achieved with a noiseless feedback link. The resulting exponent can be far larger than the exponent of erasure decoding, particularly at rates close to capacity

We consider a point to point communication system facing interference from other systems, with a particular focus on the case when this interference is undecodable. It is well known that when the interference is non-interactive, we can certainly treat it as additional noise at the receiver and thereby achieve certain rates. This paper asks whether any higher rates could be achieved by exploiting knowledge of the interferer's codebook. The main contribution of this paper is to study the converse: if the interference is undecodable, then we cannot do better than treating it as additional noise. This is proved for almost all interference codebooks when viewed under the random Gaussian codebook measure. When the interference signal is strong enough to be decodable, then codebook knowledge can be exploited at our receiver to allow higher rates to be achieved by appropriately structuring our own codebooks. Finally, we give an example of an interference codebook that cannot be completely decoded, but whose knowledge is still useful. However, this interference codebook is bad from the perspective of the interferer's own communication system. This leads us to conjecture that when the interference signal is undecodable, the only interference codebooks worth knowing are those that are not worth using from the interfering system's point of view

In channel coding, reliable communication takes place at rates below capacity at the fundamental cost of end-to-end delay. Error exponents tell us how much faster convergence is when we settle for less rate. For lossless source coding, entropy takes the place of capacity and error exponents tell us how much faster convergence is when we use more rate. While in channel coding without feedback the block error exponent is a good proxy for studying the more fundamental tradeoff with fixed end-to-end delay, it is not so in source coding. Block-coding error exponents are quite conservative (despite being tight!) when it comes to the tradeoff with delay. Nonblock codes can achieve much better performance with fixed delay and we present both the fundamental bound and how to achieve it in a delay-universal manner. The proof gives substance to Shannon's cryptic statement about how the duality between source and channel coding is like the duality between the past and the future.

In this paper, we review how Shannon's classical notion of capacity is not enough to characterize a noisy communication channel if the channel is intended to be used as part of a feedback loop to stabilize an unstable scalar linear system. While classical capacity is not enough, another sense of capacity (parametrized by reliability) called "anytime capacity" is necessary for the stabilization of an unstable process. The required rate is given by the log of the unstable system gain and the required reliability comes from the sense of stability desired. A consequence of this necessity result is a sequential generalization of the Schalkwijk-Kailath scheme for communication over the additive white Gaussian noise (AWGN) channel with feedback. In cases of sufficiently rich information patterns between the encoder and decoder, adequate anytime capacity is also shown to be sufficient for there to exist a stabilizing controller. These sufficiency results are then generalized to cases with noisy observations, delayed control actions, and without any explicit feedback between the observer and the controller. Both necessary and sufficient conditions are extended to continuous time systems as well. We close with comments discussing a hierarchy of difficulty for communication problems and how these results establish where stabilization problems sit in that hierarchy

Random binning arguments underlie many results in information theory. In this paper we introduce and analyze a novel type of causal random binning "sequential" binning. This binning is used to get streaming Slepian-Wolf codes with an "anytime" character. At the decoder, the probability of estimation error on any particular symbol goes to zero exponentially fast with delay. In the non-distributed context, we show equivalent results for fixed-rate streaming entropy coding. Because of space constraints, we present full derivations only for the latter, stating the results for the distributed problem. We give bounds on error exponents for both universal and maximum-likelihood decoders

We introduce a new problem of broadcast source coding with a discrimination requirement - there is an eavesdropping user from whom we wish to withhold the true message in an entropic sense. Binning can achieve the Slepian-Wolf rate, but at the cost of full information leakage to the eavesdropper. Our main result is a lower bound that implies that any entropically efficient broadcast scheme must be "like binning" in that it also must leak significant information to eavesdroppers

We study the reliability of sequential codes in a two-state Markov fading AWGN channel under the assumption of noiseless feedback and an average power constraint. We present a capacity achieving scheme with a doubly exponential anytime reliability function with respect to delay for every bit. The scheme is represented by a hybrid control system at the encoder in which the discrete system dynamics evolves based only on the channel state information while the continuous part of the state at the encoder reflects the evolution of the message uncertainty at the decoder. Whereas the classical Schalkwijk-Kailath scheme achieves double exponential reliability by exploiting the average nature of the power constraint to combat atypicality of the AWGN noise, our scheme also uses it to combat atypical fading realizations

For the point-to-point additive white Gaussian noise (AWGN) channel with noiseless feedback and an average power constraint, Schalkwijk and Kailath's scheme achieves a doubly-exponential decay of the probability of error. While some coding schemes for networks with noiseless feedback incorporate variations on the Schalkwijk-Kailath scheme, they do not in general achieve better than single-exponential decays in their probabilities of error everywhere in their achievable rate regions. We give a technique that can boost the reliability as high as desired of any from a large class of block coding schemes for networks with feedback. The technique relies crucially on the average nature of the power constraints. We explain and illustrate our results in the context of Ozarow's feedback strategy for the AWGN multiple-access channel

This paper describes the encoding of a scalar unstable Markov process into two parallel fixed-rate bit streams. Source coding theorems for stable Markov and Gaussian auto-regressive processes (ARMA process) under mean-squared-error distortion used in calculating a standard information-theoretic rate-distortion function.

We give a scheme for variable-delay reliable communication over a noisy discrete memoryless channel with a noisy feedback DMC being available between the receiver and the transmitter. This scheme works when the capacity of the feedback channel is greater than the capacity of the forward channel and the target rate of communication on the forward channel is less than its capacity. Rather than looking at a single block in isolation, we consider the scenario where we expect this system to carry an infinite stream of packets. We show that in the limit of nearly noiseless feedback channels, we approach the Burnashev bound on the reliability of variable-delay channel codes.

The localization problem is fundamentally important for sensor networks. We study the Cramer-Rao lower bound (CRB) for two kinds of localization based on noisy range measurements. The first is anchored localization in which we know true positions of at least 3 nodes. We show some basic invariances of the CRB in this case and derive lower and upper bounds on the CRB which can be computed using only local information. The second is anchor-free localization where no absolute positions are known. Although the Fisher information matrix is singular, we derive a CRB-like bound on the total estimation variance. Finally, for both cases we discuss how the bounds scale to large networks under different models of wireless signal propagation.