We study the Chernoff-Stein exponent of the following binary hypothesis testing problem: Associated with each hypothesis is a set of channels. A transmitter, without knowledge of the hypothesis, chooses the vector of inputs to the channel. Given the hypothesis, from the set associated with the hypothesis, an adversary chooses channels, one for each element of the input vector. Based on the channel outputs, a detector attempts to distinguish between the hypotheses. We study the Chernoff-Stein exponent for the cases where the transmitter (i) is deterministic, (ii) may privately randomize, and (iii) shares randomness with the detector that is unavailable to the adversary. It turns out that while a memoryless transmission strategy is optimal under shared randomness, it may be strictly suboptimal when the transmitter only has private randomness.

The Singleton bound provides a fundamental limit on the maximum possible size of an error-correcting code of a given length and distance. However, recent work by Zhang et. al. [IEEE Trans. Comm., Dec. 2023] showed that in the context of the wiretap multipath network when the adversary has limited knowledge about the codewords and a vanishing probability of decoding error is permitted, a rate higher than the Singleton bound is achievable. Their results, however, are confined to an ideal setting where the adversary is allowed to behave non-causally. Motivated by real-world scenarios, this work considers communication over a wiretap multipath network in the presence of a causal adversary (i.e., the adversary which is only allowed to use the observations up to the current time slot to decide the current jamming strategy) and in the presence of passive feedback from the receiver to the transmitter. We characterize both the capacity and secrecy capacity of the wiretap multipath network, either with or without passive feedback. We observe that in comparison to the non-causal and non-feedback setting, the capacity and secrecy capacity can be strictly higher for a wide variety of parameters, demonstrating the benefits of causality and feedback.

We introduce the problem of determining the identity of a byzantine user (internal adversary) in a communication system. We consider a two-user discrete memoryless multiple access channel where either user may deviate from the prescribed behaviour. Since small deviations may be indistinguishable from the effects of channel noise, it might be overly restrictive to attempt to detect all deviations. In our formulation, we only require detecting deviations which impede the decoding of the non-deviating user’s message. When neither user deviates, correct decoding is required. When one user deviates, the decoder must either output a pair of messages of which the message of the non-deviating user is correct or identify the deviating user. The users and the receiver do not share any randomness. The results include a characterization of the set of channels where communication is feasible, and an inner and outer bound on the capacity region. We also show that whenever the rate region has non-empty interior, the capacity region is same as the capacity region under randomized encoding, where each user shares independent randomness with the receiver. We also give an outer bound for this randomized coding capacity region.

We introduce the paradigm of validated decentralized learning for undirected networks with heterogeneous data and possible adversarial infiltration. We require ($a$) convergence to a global empirical loss minimizer when adversaries are absent, and$(\boldsymbol{b})$either detection of adversarial presence or convergence to an admissible consensus model in their presence. This contrasts sharply with the traditional byzantine-robustness requirement of convergence to an admissible consensus irrespective of the adversarial configuration. To this end, we propose the Valid protocol which, to the best of our knowledge, is the first to achieve a validated learning guarantee. Moreover, Valid offers an$O(1/T)$convergence rate (under pertinent regularity assumptions), and computational and communication complexities comparable to non-adversarial distributed stochastic gradient descent. Remarkably, Valid retains optimal performance metrics in adversary-free environments, sidestepping the robustness penalties observed in prior byzantine-robust methods. A distinctive aspect of our study is a heterogeneity metric based on the norms of individual agents' gradients computed at the global empirical loss minimizer. This not only provides a natural statistic for detecting significant byzantine disruptions but also allows us to prove the optimality of Valid in wide generality. Lastly, our numerical results reveal that, in the absence of adversaries, Validcon-verges faster than state-of-the-art byzantine robust algorithms, while when adversaries are present, Valid terminates with each honest agent either converging to an admissible consensus or declaring adversarial presence in the network.

We study the adversarial binary hypothesis testing problem [1] in the sequential setting. Associated with each hypothesis is a closed, convex set of distributions. Given the hypothesis, each observation is generated according to a distribution chosen (from the set associated with the hypothesis) by an adversary who has access to past observations. In the sequential setting, the number of observations the detector uses to arrive at a decision is variable; however there is a constraint on the expected number of observations used. We characterize the closure of the set of achievable pairs of error exponents.

We study communication over a Multiple Access Channel (MAC) where users can possibly be adversarial. The receiver is unaware of the identity of the adversarial users (if any). When all users are non-adversarial, we want their messages to be decoded reliably. When a user behaves adversarially, we require that the honest users’ messages be decoded reliably. An adversarial user can mount an attack by sending any input into the channel rather than following the protocol. It turns out that the 2-user MAC capacity region follows from the point-to-point Arbitrarily Varying Channel (AVC) capacity. For the 3-user MAC in which at most one user may be malicious, we characterize the capacity region for deterministic codes and randomized codes (where each user shares an independent random secret key with the receiver). These results are then generalized for the$k$-user MAC where the adversary may control all users in one out of a collection of given subsets.

We consider the problem of authenticated communication over a discrete arbitrarily varying channel where the legitimate parties are unaware of whether or not an adversary is present. When there is no adversary, the channel state always takes a default value ∅. When the adversary is present, they may choose the channel state sequence based on a non-causal noisy view of the transmitted codewords and the encoding and decoding scheme. We require that the decoder output the correct message with a high probability when there is no adversary, and either output the correct message or reject the transmission when the adversary is present. Further, we allow the transmitter to employ private randomness during encoding that is known neither to the receiver nor the adversary. Our first result proves a dichotomy property for the capacity for this problem – the capacity either equals zero or it equals the non-adversarial capacity of the channel. Next, we give a sufficient condition for the capacity for this problem to be positive even when the non-adversarial channel to the receiver is stochastically degraded with respect to the channel to the adversary. Our proofs rely on a connection to a standalone authentication problem, where the goal is to accept or reject a candidate message that is already available to the decoder. Finally, we give examples and compare our sufficient condition with other related conditions known in the literature.

We study the Chernoff-Stein exponent of the following binary hypothesis testing problem: Associated with each hypothesis is a set of channels. A transmitter, without knowledge of the hypothesis, chooses the vector of inputs to the channel. Given the hypothesis, from the set associated with the hypothesis, an adversary chooses channels, one for each element of the input vector. Based on the channel outputs, a detector attempts to distinguish between the hypotheses. We study the Chernoff-Stein exponent for the cases where the transmitter (i) is deterministic, (ii) may privately randomize, and (iii) shares randomness with the detector that is unavailable to the adversary. It turns out that while a memoryless transmission strategy is optimal under shared randomness, it may be strictly suboptimal when the transmitter only has private randomness.

We study universal compression of n i.i.d. copies of a k−variate Gaussian random vector, when the mean is an unknown vector in an Euclidean ball of ℝk, and the covariance is known. We adopt the high dimensional scaling k = Θ(n) to bring out a compression perspective on the inadmissibility of unbiased estimates of a k−variate Gaussian (when k ≥ 3), in particular focusing on the optimal unbiased Maximum Likelihood estimate. We use arguments based on the redundancy-capacity theorem to show that the redundancy of a universal compressor in this high dimensional setting must be lower bounded as Θ(n). We show that natural compression schemes based on the Maximum Likelihood estimate of the mean have suboptimal Θ(n log n) redundancy, but a scheme based on the James-Stein biased estimate of the mean incurs redundancy that is also Θ(n).

Maximum distance separable (MDS) codes are often considered to have the optimal error correction capability against malicious adversaries because they achieve the Singleton bound in terms of the rate-distance tradeoff. However, by allowing a vanishing probability of decoding error and considering an adversary with limited knowledge, it is interesting to understand whether a rate higher than the Singleton bound is achievable, and if so, what the optimal rate is. To answer these questions, we instantiate the aforementioned problem as a communication problem where the transmission medium is a wiretap multipath network that consists of multiple parallel links. A malicious adversary is able to eavesdrop on a subset of links, and also jam on a potentially overlapping subset of links. The primary objective is to ensure the communication is robust to adversarial jamming; additionally, another goal is to guarantee that the communication is information-theoretically secure with respect to the adversary. We present a complete characterization of both capacity and secrecy capacity as functions of the number of links that can be eavesdropped and/or jammed. Our achievability schemes are computationally efficient, and rely on a non-trivial combination of MDS codes and a pairwise hashing scheme.

We propose a communication model, that we call compound arbitrarily varying channels (CAVC), which unifies and generalizes compound channels and arbitrarily varying channels (AVC). A CAVC can be viewed as a noisy channel with a fixed, but unknown, compound-state and an AVC-state which may vary with every channel use. The AVC-state is controlled by an adversary who is aware of the compound-state. We study three problems in this setting: ‘communication’, ‘communication and compound-state identification’, and ‘communication or compound-state identification’. For these problems, we study conditions for feasibility and capacity under deterministic coding and random coding.

We introduce the problem of determining the identity of a byzantine user (internal adversary) in a communication system. We consider a two-user discrete memoryless multiple access channel where either user may deviate from the prescribed behaviour. Owing to the noisy nature of the channel, it may be overly restrictive to attempt to detect all deviations. In our formulation, we only require detecting deviations which impede the decoding of the non-deviating user's message. When neither user deviates, correct decoding is required. When one user deviates, the decoder must either output a pair of messages of which the message of the non-deviating user is correct or identify the deviating user. The users and the receiver do not share any randomness. The results include a characterization of the set of channels where communication is feasible, and an inner and outer bound on the capacity region.

Suppose that a transmitter Alice potentially wishes to communicate with a receiver Bob over an adversarially jammed binary channel. An active adversary James eavesdrops on their communication over a binary symmetric channel (BSC( q)), and may maliciously flip (up to) a certain fraction p of their transmitted bits based on his observations. We consider a setting where the communication must be simultaneously covert as well as reliable, i.e., James should be unable to accurately distinguish whether or not Alice is communicating, while Bob should be able to correctly recover Alice's message with high probability regardless of the adversarial jamming strategy. We show that, unlike the setting with passive adversaries, covert communication against active adversaries requires Alice and Bob to have a shared key (of length at least Ω(logn)) even when Bob has a better channel than James. We present lower and upper bounds on the information-theoretically optimal throughput as a function of the channel parameters, the desired level of covertness, and the amount of shared key available. These bounds match for a wide range of parameters of interest. We also develop a computationally efficient coding scheme (based on concatenated codes) when the amount of shared key available is Ω(√n logn), and further show that this scheme can be implemented with much less amount of shared key when the adversary is assumed to be computationally bounded.

We consider the problem of stealthy communication over a multipath network in the presence of an active adversary. The multipath network consists of multiple parallel noiseless links, and the adversary is able to eavesdrop and jam a subset of links. We consider two types of jamming- erasure jamming and overwrite jamming. We require the communication to be both stealthy and reliable, i.e., the adversary should be unable to detect whether or not meaningful communication is taking place, while the legitimate receiver should reconstruct any potential messages from the transmitter with high probability simultaneously. We provide inner and outer bounds on the stealthy capacities under both adversarial erasure and adversarial overwrite jamming.

This paper develops a concatenated coding scheme with polynomial computational complexity for covert communication over Binary Symmetric Channels (BSCs) and binary-input Discrete Memoryless Channels (DMCs). Our setting is as follows - a transmitter Alice wishes to potentially reliably transmit a message to a receiver Bob, while ensuring that the transmission taking place is covert with respect to a warden Willie (who hears Alice's transmission over another independent channel). Prior works showed that Alice can reliably and covertly transmit O(√n) message bits over n channel uses, but one drawback is that the computational complexity of the codes designed scales as 2Θ(√n). In this work we provide a capacity-achiveing coding scheme with provable guarantees on both reliability and covertness, and its computational complexity grows polynomially in the blocklength n.

We study authenticated communication over two-user multiple access channels (MAC) where one of the users is possibly adversarial. When both users behave non-adversarially, we want their messages to be decoded reliably. However, we also want to ensure that an adversarial user cannot cause an undetected error on the other (honest) user's message. We show that the following three-phase scheme is rate-optimal: a standard MAC code is first used to achieve unauthenticated communication; this is followed by two authentication phases where each user authenticates their message treating the other user as a possible adversary. We show that the authentication phases can be very short since this form of authentication itself, when possible, can be achieved for message sets whose size grow doubly exponentially in blocklength. This leads to our result that the authenticated communication capacity region of a discrete memoryless MAC is either zero or the (unauthenticated) MAC capacity region itself. This also, arguably, explains the similar nature of authenticated communication capacity of a discrete memoryless point-to-point adversarial channel recently found by Kosut and Kliewer (ITW, 2018). We also obtain analogous results for additive Gaussian noise channels.

We consider the problem of covert communication over continuous-time additive white Gaussian noise (AWGN) channels under spectral mask constraints. In addition to requiring the legitimate receiver to reliably decode, covert communication also requires that the warden is unable to estimate whether or not communication is taking place. The spectral mask at the transmitter restricts excessive radiation beyond the bandwidth of interest. We develop a communication scheme with theoretical guarantees for both covertness and reliability, based on pulse amplitude modulation (PAM) with Binary Phase Shift Keying (BPSK) and root raised cosine (RRC) carrier pulses. Given a fixed time T and a spectral mask with bandwidth parameter W, √ we show that one can transmit O( W T ) bits of information covertly and reliably, and our proposed scheme provides a lower bound on the covert capacity.

Communication over a three-user multiple access channel (MAC) is studied when any one of the users may behave adversarially. The capacity region is characterized for randomized codes (where each user shares an independent secret key with the receiver). The capacity region for deterministic codes is also studied. Necessary conditions including a new non-symmetrizability condition is obtained for this capacity region to be non-trivial. It is shown that when none of the users are symmetrizable, the randomized coding capacity region is also achievable with deterministic codes. This is analogous to the result of Ahlswede and Cai (1991) for arbitrarily varying MAC.

We consider the problem of stealth communication over a multipath network in the presence of an active adversary. The multipath network consists of multiple parallel noiseless links, and the adversary is able to eavesdrop and jam a subset of links. We consider two types of jamming - erasure jamming and overwrite jamming. We require the communication to be both stealthy and reliable, i.e., the adversary should be unable to detect whether or not meaningful communication is taking place, while the legitimate receiver should reconstruct any potential messages from the transmitter with high probability simultaneously. We provide inner bounds on the robust stealth capacities under both adversarial erasure and adversarial overwrite jamming.

Suppose that a transmitter Alice potentially wishes to communicate with a receiver Bob over an adversarially jammed binary channel. An active adversary James eavesdrops on their communication over a binary symmetric channel (BSC(q)), and may maliciously flip (up to) a certain fraction p of their transmitted bits based on his observation. We consider a setting where the communication must be simultaneously covert as well as reliable, i.e., James should be unable to accurately distinguish whether or not Alice is communicating, while Bob should be able to correctly recover Alice's message with high probability regardless of the adversarial jamming strategy. We show that, unlike the setting with passive adversaries, reliable covert communication against active adversaries requires Alice and Bob to have a shared key (of length at least Ω(log n)) even when Bob has a better channel than James. We present inner and outer bounds on the information-theoretically optimal throughputs as a function of the channel parameters, the desired level of covertness, and the amount of shared key available. Further, these bounds match for a wide range of parameters of interest.

In this paper, we consider networks where every edge is a compound Binary Symmetric Channel whose transition probability is determined by a global network state. We first examine the setting where the sum of the transition probabilities for all edges satisfies an overall global upper bound. For networks with exactly one source and one sink we show that capacity is given by the smallest min-cut among all permitted networks states. We show that routing along with end-to-end error correction is optimal for such networks. Next, we consider networks with one source and multiple sinks with multicast demands. We give upper and lower bounds on the capacity of such networks. The coding strategy that leads to our lower bound is intriguing - it involves both end-to-end error correction across the network as well as link-by-link error correction. Finally, we give a lower bound on the capacity of networks where the transition probabilities can take any arbitrary value from a known state-space.

Group-testing refers to the problem of identifying (with high probability) a (small) subset of D defectives from a (large) set of N items via a “small” number of “pooled” tests (i.e., tests that have a positive outcome if at least one of the items being tested in the pool is defective, else have a negative outcome). For ease of presentation in this paper, we focus on the regime when D = O(N1-δ) for some δ > 0. The tests may be noiseless or noisy, and the testing procedure may be adaptive (the pool defining a test may depend on the outcome of a previous test), or non-adaptive (each test is performed independent of the outcome of other tests). A rich body of the literature demonstrates that θ(D log(N)) tests are information-theoretically necessary and sufficient for the group-testing problem, and provides algorithms that achieve this performance. However, it is only recently that reconstruction algorithms with computational complexities that are sub-linear in N have started being investigated. In the scenario with adaptive tests with noisy outcomes, we present the first scheme that is simultaneously order-optimal (up to small constant factors) in both the number of tests and the decoding complexity (O (D log(N)) in both the performance metrics). The total number of stages of our adaptive algorithm is “small” (O (log(D))). Similarly, in the scenario with nonadaptive tests with noisy outcomes, we present the first scheme that is simultaneously near-optimal in both the number of tests and the decoding complexity (via an algorithm that requires O (D log(D) log(N)) tests and has a decoding complexity of O(D(log N +log2D)). Finally, we present an adaptive algorithm that only requires two stages, and for which both the number of tests and the decoding complexity scale as O(D(log N +log2D)). For all three settings, the probability of error of our algorithms scales as O (1/(poly(D)). For each of the statements mentioned earlier about the order of the number of measurements, decoding complexity, and probability of error, we provide explicitly computed “small” universal factors in our theorem statements.

In this paper, we introduce the notion of plausible deniability in an information theoretic framework. We consider a scenario where an entity that eavesdrops through a broadcast channel summons one of the parties in a communication protocol to reveal their message (or signal vector). It is desirable that the summoned party has enough freedom to produce a fake output that is likely plausible given the eavesdropper's observation. We examine three variants of this problem-message deniability, transmitter deniability, and receiver deniability. In the first setting, the message sender is summoned to produce the sent message. Similarly, in the second and third settings, the transmitter and the receiver are required to produce the transmitted codeword and the received vector, respectively. For each of these settings, we examine the maximum communication rate that allows a given minimum rate of plausible fake outputs. First, for the message deniability problem, we fully characterize the capacity region for general broadcast channels. Next, for the transmitter deniability problem, we give an achievable region for general broadcast channels by fully characterizing the set of rate pairs' achievable using deterministic coding schemes. Finally, for the receiver deniability problem, we give an achievable rate region for physically degraded broadcast channels.

We consider the problem of communication over a network containing a hidden and malicious adversary that can control a subset of network resources, and aims to disrupt communications. We focus on omniscient node-based adversary, i.e., the adversary can control a subset of nodes, and knows the message, network code and packets on all links. Characterizing information-theoretically optimal communication rates as a function of network parameters and bounds on the adversarially controlled network is in general open, even for unicast (single source, single destination) problems. In this work we characterize the information-theoretically optimal randomized capacity of such problems, i.e., under the assumption that the source node shares (an asymptotically negligible amount of) independent common randomness with each network node a priori. We propose a novel computationally-efficient communication scheme whose rate matches a natural information-theoretically “erasure outer bound” on the optimal rate. Our schemes require no prior knowledge of network topology, and can be implemented in a distributed manner as an overlay on top of classical distributed linear network coding.

In this paper, we design the first computationally efficient codes for simultaneously reliable and deniable communication over a Binary Symmetric Channel (BSC). Our setting is as follows. A transmitter Alice wishes to potentially reliably transmit a message to a receiver Bob, while ensuring that the transmission taking place is deniable from an eavesdropper Willie (who hears Alice's transmission over a noisier BSC). Prior works show that Alice can reliably and deniably transmit O(√n) bits over n channel uses without any shared secrets between Alice and Bob. One drawback of prior works is that the computational complexity of the codes designed scales as 2Θ(√n). In this work we provide the first computationally tractable codes with provable guarantees on both reliability and deniability, while simultaneously achieving the best known throughput for the problem.

Suppose x is any exactly k-sparse vector in Rn. We present a class of sparse matrices A, and a corresponding algorithm that we call short and fast1 (SHO-FA) that, with high probability over A, can reconstruct x from Ax. The SHO-FA algorithm is related to the invertible bloom lookup tables recently introduced by Goodrich et al., with two important distinctions- SHO-FA relies on linear measurements, and is robust to noise. The SHO-FA algorithm is the first to simultaneously have the following properties: 1) it requires only O(k) measurements; 2) the bit precision of each measurement and each arithmetic operation is O (log(n) + P) (here, 2-Pcorresponds to the desired relative error in the reconstruction of x); 3) the computational complexity of decoding is O(k) arithmetic operations and that of encoding is O(n) arithmetic operations; and 4) if the reconstruction goal is simply to recover a single component of x instead of all of x, with significant probability over A, this can be done in constant time. All the above constants are independent of all problem parameters other than the desired probability of success. For a wide range of parameters, these properties are informationtheoretically order-optimal. In addition, our SHO-FA algorithm works over fairly general ensembles of sparse random matrices, and is robust to random noise and (random) approximate sparsity for a large range of k. In particular, suppose the measured vector equals A(x + z) + e, where z and e correspond to the source tail and measurement noise, respectively. Under reasonable statistical assumptions on z and e, our decoding algorithm reconstructs x with an estimation error of O(||z||2 + ||e||2). The SHO-FA algorithm works with high probability over A, z, and e, and still requires only O(k) steps and O(k) measurements over O(log(n))-bit numbers. This is in contrast to most existing algorithms that focus on the worst case z model, where it is known that Ω(k log(n/k)) measurements over O(log(n))-bit numbers are necessary. Our algorithm has good empirical performance, as validated by simulations.

Principal component analysis (PCA) is a widely used mathematical technique for dimensionality reduction that works by identifying a smaller number of linearly uncorrelated variables (principal components) to explain the variation found in a data set. PCA as a technique has applications in almost all engineering disciplines including financial engineering. In this paper, we focus on PCA computations that arise in a (financial) real time risk management system (RTRM). A RTRM system has to simultaneously compute risk measures such as value-at-risk (VaR) or haircuts for large portfolios on a frequent basis. Typically, the portfolios on which these risk measures are computed, consist of thousands of financial assets. A general framework involves computation of the correlation matrix for the assets in the portfolio followed by the application of PCA to the correlation matrix and using the obtained principal components to eventually estimate the desired risk measure. In the case of large financial institutions, there could be several such portfolios corresponding to various clients and hence PCA has to be performed simultaneously on different correlation matrices. This scenario calls for an efficient high performance implementation and scheduling of concurrent PCA requests. This exposition addresses the stated scenario by proposing a solution for concurrent processing of multiple PCA requests. Concurrent processing of multiple PCA requests is achieved through suitable load distribution and scheduling mechanisms leading to optimal utilization of compute resources. The results are demonstrated on various high performance architectures including GP-GPUs and Intel based multi-core architectures. An important component of this work is a GPU based solution for PCA using CUDA streams.

We consider the problem of communication over a multi-path network in the presence of a causal adversary. The limited-view causal adversary is able to, based on the current and past observations, eavesdrop on a subset of links and also jam on a potentially overlapping subset of links. The goal is to ensure that the communication takes place reliably and secretly. We study two adversarial models - additive and overwrite jamming. For both adversarial models, we consider communication models both without and with passive feedback from decoder to encoder, i.e., the encoder sees everything that the decoder sees. The problem assumes transmissions are in the large alphabet regime. For both types of jamming models, we find the capacity under three scenarios - reliability without feedback, reliability and secrecy without feedback, and reliability with feedback. We observe that in comparison to the non-causal setting the capacity with a causal adversary is strictly increased for a wide variety of parameter settings, and present our intuition through several examples.

We consider reliable and secure communication of information over a multipath network. A transmitter Alice sends messages to the receiver Bob in the presence of a hidden adversary Calvin. The adversary Calvin can both eavesdrop and jam on (possibly non-identical) subsets of transmission links. The goal is to communicate reliably (intended receiver can understand the messages) and secretly (adversary cannot understand the messages). Two kinds of jamming, additive and overwrite, are considered. Additive jamming corresponds to wireless network model while overwrite jamming corresponds to wired network model and storage systems. The multipath network consists of C parallel links. Calvin can both jam and eavesdrop any zionumber of links, can eavesdrop (but not jam) any zi/onumber of links, and can jam (but not eavesdrop) any zo/inumber of links. We present the first “complete” information-theoretic characterization of maximum achievable rate as a function of the number of links that can be jammed and/or eavesdropped for equal and unequal link capacity multipath networks under additive and overwrite jamming in the large alphabet regime. Our achievability and converse proofs require non-trivial combination of information theoretic and coding theoretic ideas and our achievability schemes are computationally efficient. The PHaSE-Saving techniques1are used for achievability while a “stochastic” singleton bound is obtained for converse.

Compressive phase retrieval algorithms attempt to reconstruct a “sparse high-dimensional vector” from its “low-dimensional intensity measurements”. Suppose x is any length-n input vector over ℂ with exactly k non-zero entries, and A is an m × n (k1x|, ..., |Amx|) (corresponding to component-wise absolute values of the linear measurement Ax) - here Ai's correspond to the rows of the measurement matrix A. In this work, we present a class of measurement matrices A, and a corresponding decoding algorithm that we call SUPER, which can reconstruct x up to a global phase from intensity measurements. The SUPER algorithm is the first to simultaneously have the following properties: (a) it requires only O(k) (order-optimal) measurements, (b) the computational complexity of decoding is O(k log k) (near order-optimal) arithmetic operations, (c) it succeeds with high probability over the design of A. Our results hold for all k ∈ {1, 2, ..., n}.

We consider the scenario wherein a transmitter Alice wants to (potentially) communicate to the intended receiver Bob over a multipath network, i.e., a network consisting of multiple parallel links, in the presence of a passive eavesdropper Willie, who observes an unknown subset of links. A primary goal of our communication protocol is to make the communication “deniable”, i.e., Willie should not be able to reliably estimate whether or not Alice is transmitting any covert information to Bob. Moreover, if Alice is indeed actively communicating, her covert messages should be information-theoretically “hidable” in the sense that Willie's observations should not leak any information about Alice's (potential) message to Bob - our notion of hidability is slightly stronger than the notion of information-theoretic strong secrecy well-studied in the literature. We demonstrate that deniability does not imply either hidability or (weak or strong) information-theoretic secrecy; nor does information-theoretic secrecy imply deniability. We present matching inner and outer bounds on the capacity for deniable and hidable communication over multipath networks.

Alice wishes to potentially communicate with Bob over a compound Binary Symmetric Channel while Willie listens in over a compound Binary Symmetric Channel that is noisier than Bob's. The channel noise parameters for both Bob and Willie are drawn according to uniform distribution over a range, but none of the three parties know their exact values. Willie's goal is to infer whether or not Alice is communicating with Bob. We show that Alice can send her messages reliably to Bob while ensuring that even whether or not she is actively communicating is deniable to Willie. We find the best rate at which Alice can communicate both deniably and reliably using Shannon's random coding and prove a converse.

We survey here recent work pertaining to “deniable” communication - i.e., talking without being detected. We first highlight connections to other related notions (anonymity and secrecy). We then contrast the notions of deniability and secrecy. We highlight similarities and distinctions of deniability with a variety of related notions (LPD communications, stealth, channel resolvability) extant in the literature.

Alice may wish to reliably send a message to Bob over a binary symmetric channel (BSC) while ensuring that her transmission is deniable from an eavesdropper Willie. That is, if Willie observes a “significantly noisier” transmission than Bob does, he should be unable to estimate even whether Alice is transmitting or not. Even when Alice's (potential) communication scheme is publicly known to Willie (with no common randomness between Alice and Bob), we prove that over n channel uses Alice can transmit a message of length O(√n) bits to Bob, deniably from Willie. We also prove information-theoretically order-optimality of our results.

In this work we study an Arbitrarily Varying Channel (AVC) with quadratic power constraints on the transmitter and a so-called “oblivious” jammer (along with additional AWGN) under a maximum probability of error criterion, and no private randomness between the transmitter and the receiver. This is in contrast to similar AVC models under the average probability of error criterion considered in [1], [2], and models wherein common randomness is allowed [3] - these distinctions are important in some communication scenarios outlined below. We consider the regime where the jammer's power constraint is smaller than the transmitter's power constraint (in the other regime it is known no positive rate is possible). For this regime we show the existence of stochastic codes (with no common randomness between the transmitter and receiver) that enables reliable communication at the same rate as when the jammer is replaced with AWGN with the same power constraint. This matches known information-theoretic outer bounds. In addition to being a stronger result than that in [1] (enabling recovery of the results therein), our proof techniques are also somewhat more direct, and hence may be of independent interest.

We formulate and analyze a stochastic threshold group testing problem motivated by biological applications. Here a set of n items contains a subset of d ≪ C n defective items. Subsets (pools) of the n items are tested. The test outcomes are negative if the number of defectives in a pool is no larger than l; positive if the pool contains more than u defectives, and stochastic (negative/positive with some probability) if the number of defectives in the pool is in the interval [l, u]. The goal of our stochastic threshold group testing scheme is to identify the set of d defective items via a “small” number of such tests with high probability. In the regime that l = o(d) we present schemes that are computationally feasible to design and implement, and require near-optimal number of tests. Our schemes are robust to a variety of models for probabilistic threshold group testing.

We investigate the tradeoffs between rate (bits per channel use) and throughput (bits per time) in network coding over networks of independent noisy or noiseless channels under on-off scheduling. While some networks exhibit an inherent tradeoff between rate and throughput at finite blocklengths, our main result shows that rate and throughput can be simultaneously maximized in the limit of large blocklengths.

We consider the problem of finding network coding capacities of networks of independent point-to-point channels in the presence of a Byzantine adversary. We assume that the adversary knows all messages, and noise values and the code used to communicate across the network. The adversary controls an unknown subset of edges and can replace the channel output vectors from those edges. We show that finding the capacity for the above network is equivalent to finding the capacity of a network that is obtained by replacing each finite input alphabet point-to-point channel by a noiseless link of the noisy channel capacity. Our result shows the asymptotic optimality of separation between channel coding for each link followed by network coding for the resulting network under the corresponding model of adversarial attack.

We consider the problem of zero error source coding with limited feedback when side information is present at the receiver. First, we derive an achievable rate region for arbitrary joint distributions on the source and the side information. When all pairs of source and side information symbols are observed with non-zero probability, we show that this characterization gives the entire rate region. Next, we demonstrate a class of sources for which asymptotically zero feedback suffices to achieve zero-error coding at the rate promised by the Slepian-Wolf bound for asymptotically lossless coding. Finally, we illustrate these results with the aid of three simple examples.

Polar codes have attracted much recent attention as one of the first codes with low computational complexity that provably achieve optimal rate-regions for a large class of information-theoretic problems. One significant drawback, however, is that for current constructions the probability of error decays sub-exponentially in the block-length more detailed designs improve the probability of error at the cost of significantly increased computational complexity. In this work we show how the the classical idea of code concatenation - using "short" polar codes as inner codes and a "high-rate" Reed-Solomon code as the outer code - results in substantially improved performance. In particular, code concatenation with a careful choice of parameters boosts the rate of decay of the probability of error to almost exponential in the block-length with essentially no loss in computational complexity. We demonstrate such performance improvements for three sets of information-theoretic problems - a classical point-to-point channel coding problem, a class of multiple-input multiple output channel coding problems, and some network source coding problems.

We consider source coding over networks with unlimited feedback from the sinks to the sources. We first show examples of networks where the rate region with feedback is a strict superset of that without feedback. Next, we find an achievable region for multiterminal lossy source coding with feedback. Finally, we evaluate this region for the case when one of the sources is fully known at the decoder and use the result to show that this region is a strict superset of the best known achievable region for the problem without feedback.

We investigate the network source coding rate region for networks with multiple sources and multicast demands in the presence of side information, generalizing earlier results on multicast rate regions without side information. When side information is present only at the terminal nodes, we show that the rate region is precisely characterized by the cut-set bounds and that random linear coding suffices to achieve the optimal performance. When side information is present at a non-terminal node, we present an achievable region. Finally, we apply these results to obtain an inner bound on the rate region for networks with general source-demand structures.

We investigate the network coding capacity for line networks. For independent sources and a special class of dependent sources, we fully characterize the capacity region of line networks for all possible demand structures (e.g., multiple unicast, mixtures of unicasts and multicasts, etc.) Our achievability bound is derived by first decomposing a line network into single-demand components and then adding the component rate regions to get rates for the parent network. For general dependent sources, we give an achievability result and provide examples where the result is and is not tight.