Group testing is the problem of identifying a small subset of defectives from a large set using as few binary tests as possible. In most current literature on group testing the binary test outcome is $1$ if the pool contains at least one defective, and $0$ otherwise. In this work we initiate the study of a generalized model of group testing that accommodates the physical effects of dilution of infected samples in large pools. In this model the binary test outcome is $1$ with probability $f(\rho)$, where $\rho$ is the density of the defectives in the test, and $f:[0,1]\rightarrow [0,1]$ is a given "test function" that models this dilution process. For a large class of test functions our results establish near-optimal sample complexity bounds, by providing information-theoretic lower bounds on the number of tests necessary to recover the set of defective items, and providing computationally efficient algorithms with sample complexities that match these lower bounds up to constant or logarithmic factors. Furthermore, using tools from real analysis, we extend our results to any "sufficiently well-behaved function" $f:[0,1]\rightarrow [0,1]$.

In an arbitrarily varying channel (AVC), the channel has a state which is under the control of an adversarial jammer and the corresponding capacities are often functions of the “power” constraints on the transmitter and jammer. In this paper we propose a model in which the constraints must hold almost surely over contiguous subsequences of the codeword and state, which we call a sliding window constraint. We study oblivious jammers and codes with stochastic encoding under maximum probability of error. We show that this extra limitation on the jammer is beneficial for the transmitter: in some cases, the capacity for unique decoding with a sliding window constraint is equal to the capacity for list decoding in the standard model without sliding windows, roughly implying that the addition of window constraints reduces list decoding to unique decoding. The list decoding capacity in the standard model can be strictly larger than the unique decoding capacity.

It is shown that a memoryless source can be compressed arbitrarily close to its entropy rate while guaranteeing the private local decoding of any source symbol. This is achieved through a remarkably simple compression scheme that effectively separates compression and privacy.

This work provides a framework for the design of codes for zero-error information theory problems via superposition coding and suitable expurgation processes. For the Hamming metric, the proposed code construction meets the Gilbert-Varshamov bound via a different construction/analysis than the folklore uniformly random ensemble usually considered in the literature.

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 propose a concatenated code construction for a class of discrete-alphabet oblivious arbitrarily varying channels (AVCs) with cost constraints. The code has time and space complexity polynomial in the blocklength$n$. It uses a Reed-Solomon outer code, logarithmic blocklength random inner codes, and stochastic encoding by permuting the codeword before transmission. When the channel satisfies a condition called strong DS-nonsymmetrizability (a modified version of nonsymmetrizability originally due to Dobrushin and Stambler), we show that the code achieves a rate that for a variety of oblivious AVCs (such as classically studied error/erasure channels) match the known capacities.

We study communication models for channels with erasures in which the erasure pattern can be controlled by an adversary with partial knowledge of the transmitted codeword. In particular, we design block codes for channels with binary inputs with an adversary who can erase a fraction p of the transmitted bits. We consider causal adversaries, who must choose to erase an input bit using knowledge of that bit and previously transmitted bits, and myopic adversaries, who can choose an erasure pattern based on observing the transmitted codeword through a binary erasure channel with random erasures. For both settings we design efficient (polynomial time) encoding and decoding algorithms that use randomization at the encoder only. Our constructions achieve capacity for the causal and "sufficiently myopic" models. For the "insufficiently myopic" adversary, the capacity is unknown, but existing converses show the capacity is zero for a range of parameters. For all parameters outside of that range, our construction achieves positive rates.

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.

In the problem of classical group testing one aims to identify a small subset (of size$d$) of diseased individuals/defective items in a large population (of size$n$). This process is based on a minimal number of suitably-designed group tests on subsets of items, where the test outcome is positive iff the given test contains at least one defective item. Motivated by physical considerations, such as scenarios with imperfect test apparatus, we consider a generalized setting that includes as special cases multiple other group-testing-like models in the literature. In our setting the test outcome is governed by an arbitrarymonotonically increasing(stochastic) test function$f(\cdot)$, with the test outcome being positive with probability$f(x)$, where$x$is the number of defectives tested in that pool. This formulation subsumes as special cases a variety of noiseless and noisy group-testing models in the literature. Our main contributions are as follows. Firstly, for any monotone test function$f(\cdot)$we present a non-adaptive scheme that with probability$1-\varepsilon $identifies all defective items. Our scheme requires at most${\mathcal{ O}}\left ({{\Psi (f)} d\log \left ({\frac {n}{\varepsilon }}\right)}\right)$tests, where${\Psi (f)}$is a suitably defined “sensitivity parameter” of$f(\cdot)$, and is never larger than${\mathcal{ O}}(d^{1+o(1)})$, but indeed can be substantially smaller for a variety of$f(\cdot)$. Secondly, we argue that any non-adaptive group testing scheme needs at least$\Omega \left ({(1-\varepsilon) {\psi (f)} d\log \left ({\frac {n} d}\right)}\right)$tests to ensure high reliability recovery. Here${\psi (f)}$is a suitably defined “concentration parameter” of$f(\cdot)$, and${\psi (f)}\in \Omega {(1)}$. Thirdly, we prove that our sample-complexity bounds for generalized group testing are information-theoretically near-optimal for a variety of sparse-recovery group-testing models in the literature. That is, forany“noisy” test function$f(\cdot)$(i.e.,$0 < f(0) < f(d) < 1$), and for a variety of “(one-sided) noiseless” test functions$f(\cdot)$(i.e., either$f(0)=0$, or$f(d)=1$, or both) studied in the literature we show that$\frac {\Psi (f)} {\psi (f)} \in \Theta (1)$. As a by-product we tightly characterize the heretofore open information-theoretic order-wise sample-complexity for the well-studied model of threshold group-testing. For general (near)-noiseless test functions$f(\cdot)$we show that$\frac {\Psi (f)} {\psi (f)} \in {\mathcal{ O}}(d^{1+o(1)})$. We also demonstrate a “natural” test-function$f(\cdot)$whose sample complexity scales “extremally” as$\Theta (d^{2}\log n)$, rather than$\Theta (d\log n)$as in the case of classical group-testing. Some of our techniques may be of independent interest – in particular our achievability requires a delicate saddle-point approximation, our impossibility proof relies on a novel bound relating the mutual information of pair of random variables with the mean and variance of a specific function, and as a by-product of our proof showing that our sample-complexity upper and lower bounds are close we derive novel structural results about monotone functions.

In the problem of classical group testing one aims to identify a small subset (of size $d$) diseased individuals/defective items in a large population (of size $n$) via a minimal number of suitably-designed group tests on subsets of items, where the test outcome is positive iff the given test contains at least one defective item. Motivated by physical considerations, we consider a generalized setting that includes as special cases multiple other group-testing-like models in the literature. In our setting, which subsumes as special cases a variety of noiseless and noisy group-testing models in the literature, the test outcome is positive with probability $f(x)$, where $x$ is the number of defectives tested in a pool, and $f(\cdot)$ is an arbitrary {\it monotonically increasing} (stochastic) test function. Our main contributions are as follows. 1. We present a non-adaptive scheme that with probability $1-\varepsilon$ identifies all defective items. Our scheme requires at most ${\cal O}( H(f) d\log(n/\varepsilon))$ tests, where $H(f)$ is a suitably defined “sensitivity parameter" of $f(\cdot)$, and is never larger than ${\cal O}(d^{1+o(1)})$, but may be substantially smaller for many $f(\cdot)$. 2. We argue that any non-adaptive group testing scheme needs at least $\Omega (h(f) d\log(n/d))$ tests to ensure high reliability recovery. Here $h(f)$ is a suitably defined “concentration parameter" of $f(\cdot)$, and $h(f) \in \Omega{(1)}$. 3. We prove that our sample-complexity bounds for generalized group testing are information-theoretically near-optimal for a variety of sparse-recovery group-testing models in the literature. That is, for {\it any} “noisy" test function $f(\cdot)$ (i.e. $0< f(0) < f(d) <1$), and for a variety of “(one-sided) noiseless" test functions $f(\cdot)$ (i.e., either $f(0)=0$, or $f(d)=1$, or both) studied in the literature we show that $H(f)/h(f) \in \Theta(1)$. As a by-product we tightly characterize the heretofore open information-theoretic sample-complexity for the well-studied model of threshold group-testing. For general (near)-noiseless test functions $f(\cdot)$ we show that $H(f)/h(f) \in {\cal O}(d^{1+o(1)})$. We also demonstrate a “natural" test-function $f(\cdot)$ whose sample complexity scales “extremally" as $\Theta ( d^2\log(n))$, rather than $\Theta ( d\log(n))$ as in the case of classical group-testing. Some of our techniques may be of independent interest – in particular our achievability requires a delicate saddle-point approximation, and our impossibility proof relies on a novel bound relating the mutual information of pair of random variables with the mean and variance of a specific function, and we derive novel structural results about monotone functions.

We consider the problem of communication over adversarial channels with feedback. Two parties comprising sender Alice and receiver Bob seek to communicate reliably. An adversary James observes Alice's channel transmission entirely and chooses, maliciously, its additive channel input or jamming state thereby corrupting Bob's observation. Bob can communicate over a one-way reverse link with Alice; we assume that transmissions over this feedback link cannot be corrupted by James. Our goal in this work is to study the optimum throughput or capacity over such channels with feedback. We first present results for the quadratically-constrained additive channel where communication is known to be impossible when the noise-to-signal (power) ratio (NSR) is at least 1. We present a novel achievability scheme to establish that positive rate communication is possible even when the NSR is as high as 8/9. We also present new converse upper bounds on the capacity of this channel under potentially stochastic encoders and decoders. We also study feedback communication over the more widely studied q-ary alphabet channel under additive noise. For the q -ary channel, where q > 2, it is well known that capacity is positive under full feedback if and only if the adversary can corrupt strictly less than half the transmitted symbols. We generalize this result and show that the same threshold holds for positive rate communication when the noiseless feedback may only be partial; our scheme employs a stochastic decoder. We extend this characterization, albeit partially, to fully deterministic schemes under partial noiseless feedback. We also present new converse upper bounds for q-ary channels under full feedback, where the encoder and/or decoder may privately randomize. Our converse results bring to the fore an interesting alternate expression for the well known converse bound for the q—ary channel under full feedback which, when specialized to the binary channel, also equals its known capacity.

In the classic adversarial communication problem, two parties communicate over a noisy channel in the presence of a malicious jamming adversary. The arbitrarily varying channels (AVCs) offer an elegant framework to study a wide range of interesting adversary models. The optimal throughput or capacity over such AVCs is intimately tied to the underlying adversary model; in some cases, capacity is unknown and the problem is known to be notoriously hard. The omniscient adversary, one which knows the sender’s entire channel transmission a priori, is one of such classic models of interest; the capacity under such an adversary remains an exciting open problem. The myopic adversary is a generalization of that model where the adversary’s observation may be corrupted over a noisy discrete memoryless channel. Through the adversary’s myopicity, one can unify the slew of different adversary models, ranging from the omniscient adversary to one that is completely blind to the transmission (the latter is the well known oblivious model where the capacity is fully characterized).In this work, we present new results on the capacity under both the omniscient and myopic adversary models. We completely characterize the positive capacity threshold over general AVCs with omniscient adversaries. The characterization is in terms of two key combinatorial objects: the set of completely positive distributions and the CP-confusability set. For omniscient AVCs with positive capacity, we present non-trivial lower and upper bounds on the capacity; unlike some of the previous bounds, our bounds hold under fairly general input and jamming constraints. Our lower bound improves upon the generalized Gilbert-Varshamov bound for general AVCs while the upper bound generalizes the well known Elias-Bassalygo bound (known for binary and q-ary alphabets). For the myopic AVCs, we build on prior results known for the so-called sufficiently myopic model, and present new results on the positive rate communication threshold over the so-called insufficiently myopic regime (a completely insufficient myopic adversary specializes to an omniscient adversary). We present interesting examples for the widely studied models of adversarial bit-flip and bit-erasure channels. In fact, for the bit-flip AVC with additive adversarial noise as well as random noise, we completely characterize the omniscient model capacity when the random noise is sufficiently large vis-a-vis the adversary’s budget.

We characterize the capacity for the discrete-time arbitrarily varying channel with discrete inputs, outputs, and states when (a) the encoder and decoder do not share common randomness, (b) the input and state are subject to cost constraints, (c) the transition matrix of the channel is deterministic given the state, and (d) at each time step the adversary can only observe the current and past channel inputs when choosing the state at that time. The achievable strategy involves stochastic encoding together with list decoding and a disambiguation step. The converse uses a two-phase "babble-and-push" strategy where the adversary chooses the state randomly in the first phase, list decodes the output, and then chooses state inputs to symmetrize the channel in the second phase. These results generalize prior work on specific channels models (additive, erasure) to general discrete alphabets and models.

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is allowed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding or stochastic encoding, i.e., with no common randomness between the encoder/decoder pair. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most$2\log (n)$bits in one sub-regime, and at most$\Omega ({n})$bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques involve a novel myopic list-decoding result for achievability, and a Plotkin-type push attack for the converse in a subregion of the NSRs, both of which may be of independent interest. We also give bounds on the strong secrecy capacity of this channel assuming that the jammer is simultaneously eavesdropping.

We consider the problem of reliable communication over a network containing a hidden myopic adversary who can eavesdrop on some Zrolinks, jam some Zwolinks, and do both on some Zrwlinks. We provide the first information-theoretically tight characterization of the optimal rate of reliable communication possible under all possible settings of the tuple (Zro, Zwo, Zrw) by providing a novel coding scheme/analysis for a subset of parameter regimes. In particular, by leveraging the adversary's uncertainty on unobserved links our vanishing-error schemes bypass the Network Singleton Bound (which requires a zero-error recovery criteria) in a certain parameter regime where the capacity had been heretofore open. As a direct corollary we also obtain the capacity of the corresponding problem where information-theoretic secrecy against eavesdropping is required in addition to reliable communication.

We study list-decoding over adversarial channels governed by oblivious adversaries (a.k.a. oblivious Arbitrarily Varying Channels (AVCs)). This type of adversaries aims to maliciously corrupt the communication without knowing the actual transmission from the sender. For any oblivious AVCs potentially with constraints on the sender's transmitted sequence and the adversary's noise sequence, we determine the exact value of the minimum list-size that can support a reliable communication at positive rate. This generalizes a classical result by Hughes (IEEE Transactions on Information Theory, 1997) and answers an open question posed by Sarwate and Gastpar (IEEE Transactions on Information Theory, 2012). A lower bound on the list-decoding capacity (whenever positive) is presented. Under a certain combinatorial conjecture, we also prove a matching upper bound. En route to a tight characterization of the list-decoding capacity, we propose a method for subcode construction towards the resolution of the combinatorial conjecture.

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.

This paper concerns itself with the question of list decoding for general adversarial channels, e.g., bit-flip ($\textsf{XOR}$) channels, erasure channels, $\textsf{AND}$ ($Z$-) channels, $\textsf{OR}$ channels, real adder channels, noisy typewriter channels, etc. We precisely characterize when exponential-sized (or positive rate) $(L-1)$-list decodable codes (where the list size $L$ is a universal constant) exist for such channels. Our criterion asserts that: "For any given general adversarial channel, it is possible to construct positive rate $(L-1)$-list decodable codes if and only if the set of completely positive tensors of order-$L$ with admissible marginals is not entirely contained in the order-$L$ confusability set associated to the channel." The sufficiency is shown via random code construction (combined with expurgation or time-sharing). The necessity is shown by 1. extracting equicoupled subcodes (generalization of equidistant code) from any large code sequence using hypergraph Ramsey's theorem, and 2. significantly extending the classic Plotkin bound in coding theory to list decoding for general channels using duality between the completely positive tensor cone and the copositive tensor cone. In the proof, we also obtain a new fact regarding asymmetry of joint distributions, which be may of independent interest. Other results include 1. List decoding capacity with asymptotically large $L$ for general adversarial channels; 2. A tight list size bound for most constant composition codes (generalization of constant weight codes); 3. Rederivation and demystification of Blinovsky's [Bli86] characterization of the list decoding Plotkin points (threshold at which large codes are impossible); 4. Evaluation of general bounds ([WBBJ]) for unique decoding in the error correction code setting.

Consider the communication efficient secret sharing problem. A dealer wants to share a secret with n parties such that any k ≤ n parties can reconstruct the secret and any z <; k parties eavesdropping on their shares obtain no information about the secret. In addition, a legitimate user contacting any d, k ≤d ≤n, parties to decode the secret can do so by reading and downloading the minimum amount of information needed. We are interested in communication efficient secret sharing schemes that tolerate the presence of malicious parties actively corrupting their shares and the data delivered to the users. The knowledge of the malicious parties about the secret is restricted to the shares they obtain. We characterize the capacity, i.e., maximum size of the secret that can be shared. We derive the minimum amount of information needed to to be read and communicated to a legitimate user to decode the secret from d parties, k ≤d≤ n. We construct codes that achieve capacity. In addition, the constructed codes achieve minimum read and communication costs for all possible values of d. Our codes are based on Staircase codes, previously introduced for communication efficient secret sharing, and on the use of a pairwise hashing scheme used in distributed data storage and network coding settings to detect the presence of a limited knowledge adversary.

Myopic arbitrarily varying channels (AVCs) are point-to-point communication models in which a channel state is controlled by a malicious adversary (a jammer) who receives side-information about the transmitted codeword via a side-channel (wiretapping) and wishes to maximize the probability of error. Compared to standard "oblivious" AVCs, myopic AVCs can potentially use the side information to launch a more effective attack, lowering the capacity of the channel. In this paper, we define a novel property, myopic symmetrizability, and prove it is a sufficient condition for the capacity of any myopic AVC to be zero. We also study the sufficiently myopic setting, in which, roughly speaking, the jammer's side information reveals less information on the codeword transmitted than eventually available at the receiver. In this scenario we show that myopic symmetrizability is also a necessary condition for the capacity to equal zero, by providing a novel code construction using non-i.i.d. codebooks. A key technical lemma, interesting in its own right, is an argument showing that for any positive-rate code (whether for myopic AVCs or not) one can identify a corresponding distribution PX,X'that is a convex combination of product distributions, and such that a constant fraction of pairs of codewords have an empirical distribution approximately equaling PX,X'.

In this article, we revisit the classical problem of channel coding and obtain novel results on properties of capacity- achieving codes. Specifically, we give a linear algebraic characterization of the set of capacity-achieving input distributions for discrete memoryless channels. This allows us to characterize the dimension of the manifold on which the capacity-achieving distributions lie. We then proceed by examining empirical properties of capacity-achieving codebooks by showing that the joint-type of k-tuples of codewords in a good code must be close to the k- fold product of the capacity-achieving input distribution. While this conforms with the intuition that all capacity-achieving codes must behave like random capacity-achieving codes, we also show that some properties of random coding ensembles do not hold for all codes. We prove this by showing that there exist pairs of communication problems such that random code ensembles simultaneously attain capacities of both problems, but certain (superposition ensembles) do not.Due to lack of space, several proofs have been omitted but can be found at https://sites.google.com/view/yihan/ [1]

We study achievable rates of reliable communication in a power-constrained two-way additive interference channel over the real alphabet where communication is disrupted by a power-constrained jammer. This models the wireless communication scenario where two users Alice and Bob, operating in the full duplex mode, wish to exchange messages with each other in the presence of a jammer, James. Alice and Bob simultaneously transmit their encodings xAand xBover n channel uses. It is assumed that James can choose his jamming signal s as a noncausal randomized function of xA+ xB, and the codebooks used by Alice and Bob. Alice and Bob observe xA+ xB+ s, and must recover each others' messages reliably. In this article, we provide upper and lower bounds on the capacity of this channel which match each other and equal 1/2 log (1/2 + SNR) in the high-SNR regime (where SNR, signal to noise ratios, is defined as the ratio of the power constraints of the users to the power constraint of the jammer). We give a code construction based on lattice codes, and derive achievable rates for large SNR. We also present upper bounds based on two specific attack strategies for James. Along the way, sumset property of lattices for the achievability and general properties of capacity-achieving codes for memoryless channels for the converse are proved, which might be of independent interest. The full version of this paper is [1].

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 an adversarial communication problem where sender Alice wishes to send a message m to receiver Bob over an arbitrarily varying channel (AVC) controlled by a malicious adversary James. We assume that Alice and Bob share randomness K unknown to James. Using K, Alice first encodes the message m to a codeword X and transmits it over the AVC. James knows the message m, the (randomized) codebook and the codeword X. James then inputs a jamming state S to disrupt communication; we assume a state-deterministic AVC where S completely specifies the channel noise. Bob receives a noisy version Y of codeword X; it outputs a message estimate m using Y and the shared randomness K. We study AVCs, called `adversary-weakened' AVCs here, where the availability of shared randomness strictly improves the optimum throughput or capacity over it than when it is not available; the randomized coding capacity characterizes the largest rate possible when K is unrestricted. In this work, we characterize the exact threshold for the amount of shared randomness K so as to achieve the randomized coding capacity for `adversary-weakened' AVCs. We show that exactly log(n) equiprobable and independent bits of randomness, shared between Alice and Bob and unknown to adversary James, are both necessary and sufficient for achieving randomized coding capacity for `adversary-weakened' AVCs. For sufficiency, our achievability is based on a randomized code construction which uses deterministic list codes along with a polynomial hashing technique which uses the shared randomness. Our converse, which establishes the necessity of log(n) bits of shared randomness, uses a known approach for binary AVCs, and extends it to general `adversary-weakened' AVCs using a notion of confusable codewords.

The difference in capacity formulae between worst-case and average-case channel noise models has been part of information theory since the early days of the field. This paper continues a line of work studying intermediate models in which the channel behavior can depend partially on the transmitted codeword. In particular, we consider a model in which a binary erasure channel (with maximum fraction of erasures p) is controlled by an adversary who can observe the transmitted codeword through an independent and memoryless erasure channel (with erasure probability q). Upper and lower bounds on the capacity are given for two models: a noncausal model, in which the adversary can choose their erasures based on the entire (partially observed) codeword, and a causal model, in which at each time the adversary must choose its erasures based on the current and previously observed codeword bits. The achievable rate for the noncausal case is larger than the Gilbert-Varshamov bound and for some parameter ranges exceeds the linear programming (LP) bound; we also provide a non-trivial outer bound on the capacity. For the causal case, we show the capacity is 1-2p+q for p ≥ q (prior work shows the capacity to equal 1-p when p<;q). Our code construction in both scenarios are novel, requiring the encoder to carefully add “low-weight correlated noise” to its transmission.

We study a general Omniscient Arbitrarily Varying Channel (AVC) problem where Alice wishes to communicate a message to receiver Bob by inputting a length-n vector x to a channel. Jammer James observes x, and as a function of x chooses a state sequence s. Bob observes y (such that channel inputs and outputs are related component-wise as yi= w(xi,si) for some deterministic function w(.,.)) from which he must estimate m with no error. Input and state constraints determine feasible inputs x and s for Alice and James respectively. In this work we characterize when a positive communication rate is possible.We first show that the capacity of any such AVC completely depends upon the relationship between a confusability set, and the set of completely-positive-self-couplings (both are convex sets of certain single-letter probability distributions). Our main result provides essentially matching necessary and sufficient conditions for capacity positivity; we show that the zero-error capacity of an AVC is positive if there are completely-positive-self-couplings outside the confusability set of the given AVC; and that the AVC capacity is zero if all completely-positive-self couplings are in the interior of this confusability set. Our achievability uses a novel code construction based on completely-positive-self-couplings called cloud codes which are strict generalizations of all known Gilbert-Varshamov (GV) type codes. Our converse is based upon Ramsey-theoretic ideas, a generalization of the Plotkin bound leveraging a known result on the duality of completely positive matrices and copositive matrices, and a Fourier-analytic proof of the non-existence of certain sequences of random variables.

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.

In the q-ary online (or “causal”) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1,..., xn) ∈ {0, 1,..., q-1}nsymbol-by-symbol via a channel limited to at most pn errors and p*n erasures. The channel is “online” in the sense that at the ith step of communication the channel decides whether to corrupt the ith symbol or not based on its view so far, i.e., its decision depends only on the transmitted symbols (x1, . . ., xi). This is in contrast to the classical adversarial channel in which the corruption is chosen by a channel that has full knowledge of the sent codeword x. In this paper, we study the capacity of q-ary online channels for a combined corruption model, in which the channel may impose at most pn errors and at most p*n erasures on the transmitted codeword. The online channel (in both the error and erasure case) has seen a number of recent studies, which present both upper and lower bounds on its capacity. In this paper, we give a full characterization of the capacity as a function of q, p, and p*.

We consider a communication problem in which a sender, Alice, wishes to communicate with a receiver, Bob, over a channel controlled by an adversarial jammer, James, who is myopic. Specifically, for blocklength n, the codeword Xntransmitted by Alice is corrupted by James who must base his adversarial decisions (of which locations of Xnto corrupt and how to corrupt them) on the non-causal observation Znof Xnobtained through a noisy memoryless channel. More specifically, our communication model may be described by two channels. A memoryless channelpZ|Xfrom Alice to James, and an arbitrarily varying channel from Alice to Bob, pY|XSgoverned by a state Sndetermined by James. In standard adversarial channels, the states Snmay depend on the codeword Xn, but in our setting Sndepends non-causally only on James's view Zn. We present upper and lower bounds on the capacity of myopic channels. For a number of special cases of interest we show that our bounds are tight. We then extend our results to the setting of secure communication, in which we require that the transmitted message remains secret from James. For example, we show that if 1i) James may flip at most a p fraction of the bits communicated between Alice and Bob and 2) James views Xnthrough a binary symmetric channel with crossover probability q, then once James is “sufficiently myopic” (in this case, when pH(p)), then the optimal communication rate is that of an adversary who is “blind” (that is, an adversary that does not have any knowledge of Xnat all), which is 1- H(p) for standard communication, and H(q)- H(p) for secure communication. A similar phenomenon exists for more general models of communication.

Group testing is the process of pooling arbitrary subsets from a set of n items so as to identify, with a minimal number of tests, a “small” subset of d defective items. In “classical” non-adaptive group testing, it is known that when d is substantially smaller than n, Θ(dlog(n)) tests are both information-theoretically necessary and sufficient to guarantee recovery with high probability. Group testing schemes in the literature that meet this bound require most items to be tested Ω(log(n)) times, and most tests to incorporate Ω(n/d) items. Motivated by physical considerations, we study group testing models in which the testing procedure is constrained to be “sparse.” Specifically, we consider (separately) scenarios in which 1) items are finitely divisible and hence may participate in at most γ ∈ o(log(n)) tests; or 2) tests are size-constrained to pool no more than ρ ∈ o(n/d) items per test. For both scenarios, we provide information-theoretic lower bounds on the number of tests required to guarantee high probability recovery. In particular, one of our main results shows that γ-finite divisibility of items forces any non-adaptive group testing algorithm with the probability of recovery error at most ϵ to perform at least γd(n/d)(1-5ϵ)/γtests. Analogously, for ρ-sized constrained tests, we show an information-theoretic lower bound of Ω(n/ρ) tests for high-probability recovery-hence in both settings the number of tests required grows dramatically (relative to the classical setting) as a function of n. In both scenarios, we provide both randomized constructions and explicit constructions of designs with computationally efficient reconstruction algorithms that require a number of tests that is optimal up to constant or small polynomial factors in some regimes of n, d, γ, and ρ. The randomized design/reconstruction algorithm in the ρ-sized test scenario is universal-independent of the value of d, as long as ρ ∈ o(n/d). We also investigate the effect of unreliability/noise in test outcomes, and show that whereas the impact of noise in test outcomes can be obviated with a small (constant factor) penalty in the number of tests in the ρ-sized tests scenario, there is no group-testing procedure, regardless of the number of tests, that can combat noise in the γ-divisible scenario.

In this work we prove new impossibility results for perhaps the simplest non-linear estimation problem, that of Group Testing (GT), via the Madiman-Tetali inequalities. Group Testing concerns itself with identifying d defective items from a set of n items via t disjunctive measurements. We consider the linear sparsity regime, i.e. d=δn for any constant , a hitherto little-explored (though natural) regime. In a standard information-theoretic setting, where the tests are required to be non-adaptive and a small probability of reconstruction error is allowed, our lower bounds on t are the first that improve over the classical counting lower bound, t/n ≥ H(δ), where H(·) is the binary entropy function. As corollaries of our result, we show that (i) for δ >~0.347, individual testing is essentially optimal, i.e., t ≥ n(1-o(1)); and (ii) there is an adaptivity gap, since for δ ∈ (0.3471,0.3819) known adaptive GT algorithms require fewer than n tests to reconstruct D, whereas our bounds imply that the best nonadaptive algorithm must essentially be individual testing of each element. Perhaps most importantly, our work provides a framework for combining combinatorial and information-theoretic methods for deriving lower bounds for a variety of non-linear estimation problems.

We study the problem of communication over a discrete arbitrarily varying channel (AVC) when a noisy version of the state is known non-causally at the encoder. The state is chosen by an adversary which knows the coding scheme. A state-myopic encoder observes this state non-causally, though imperfectly, through a noisy discrete memoryless channel (DMC). We first characterize the capacity of this state-dependent channel when the encoder-decoder share randomness unknown to the adversary, i.e., the randomized coding capacity. Next, we show that when only the encoder is allowed to randomize, the capacity remains unchanged when positive. Interesting and well-known special cases of the state-myopic encoder model are also presented.

Group Testing (GT) addresses the problem of identifying a small subset of defective items from a large population, by grouping items into as few test pools as possible. In Adaptive GT (AGT), outcomes of previous tests can influence the makeup of future tests. This scenario has been studied from an information theoretic point of view. Aldridge 2012 showed that in the regime of a few defectives, adaptivity does not help much, as the number of tests required for identification of the set of defectives is essentially the same as for non-adaptive GT. Secure GT considers a scenario where there is an eavesdropper who may observe a fraction δ of the outcomes, and should not be able to infer the status of the items. In the non-adaptive scenario, the number of tests required is 1/(1-δ) times the number of tests without the secrecy constraint. In this paper, we consider Secure Adaptive GT. Specifically, when an adaptive algorithm has access to a private feedback link of rate Rf, we prove that the number of tests required for both correct reconstruction at the legitimate user, with high probability, and negligible mutual information at the eavesdropper is 1/min{1,1-δ+Rf} times the number of tests required with no secrecy constraint. Thus, unlike non-secure GT, where an adaptive algorithm has only a mild impact, under a security constraint it can significantly boost performance. A key insight is that not only the adaptive link should disregard test results and send keys, these keys should be enhanced through a “secret sharing” scheme before usage.

We consider the problem of communication over a channel with a causal jamming adversary subject to quadratic constraints. A sender Alice wishes to communicate a message to a receiver Bob by transmitting a real-valued length-n codeword x=(x1, ..., xn) through a communication channel. Alice and Bob do not share common randomness. Knowing Alice's encoding strategy, a jammer James chooses a real-valued length- n adversarial noise sequence s=(s1, ..., sn) in a causal manner: each st (1 ≤ t ≤ n) can only depend on (x1, ..., xt). Bob receives y, the sum (over \mathbbR) of Alice's transmission x and James' jamming vector s, and is required to reliably estimate Alice's message from this sum. In addition, Alice and James's transmission powers are restricted by quadratic constraints P > 0 and N > 0 such that Σt=1nxt2≤ nP and Σt=1nst2≤ nN. In this work, we characterize the channel capacity for such a channel as the limit superior of the optimal values Cn([P/N]) of a series of optimizations. Upper and lower bounds on Cn([P/N]) are provided both analytically and numerically. Interestingly, unlike many communication problems, in this causal setting Alice's optimal codebook may not have a uniform power allocation - for certain SNR a codebook with a two-level uniform power allocation results in a strictly higher rate than a codebook with a uniform power allocation would.

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.

We study communication in the presence of a jamming adversary where quadratic power constraints are imposed on the transmitter and the jammer. The jamming signal is assumed to be a function of the codebook, and a noncausal but noisy observation of the transmitted codeword. For a certain range of the noise-to-signal ratios (NSRs) of the transmitter and the jammer, we are able to characterize the capacity of this channel under deterministic encoding. For the remaining NSR regimes, we determine the capacity under the assumption of a small amount of common randomness (at most O(log(n)) bits in one sub-regime, and at most O(n) bits in the other sub-regime) available to the encoder-decoder pair. Our proof techniques include a novel myopic list-decoding result for achievability and a Plotkin-type push attack for the converse in a subregion of the NSRs, which may be of independent interest.

We study a lossy source coding problem for an arbitrarily varying remote source (AVRS) which was proposed in a prior work. An AVRS transmits symbols, each generated in an independent and identically distributed manner, which are sought to be estimated at the decoder. These symbols are remotely generated, and the encoder and decoder observe noise corrupted versions received through a two-output noisy channel. This channel is an arbitrarily varying channel controlled by a jamming adversary. We assume that the adversary knows the coding scheme as well as the source data non-causally, and hence, can employ malicious jamming strategies correlated to them. Our interest lies in studying the rate distortion function for codes with a stochastic encoder, i.e, when the encoder can privately randomize while the decoder is deterministic. We provide upper and lower bounds on this rate distortion function.

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 highly dynamic wireless networks, communications face several challenges. In the first place, noise levels between nodes might be difficult to predict a priori. Besides, a Byzantine attacker hidden in the network, with knowledge of the network topology and observation of all transmissions, can choose arbitrary locations to inject corrupted packets. Considering that transmissions are usually in bits and hardware in wireless networks usually use modulation schemes with the size of modulation alphabet being powers of two, e.g. BPSK, QPSK, 16-QAM, 64-QAM, and so on, to address the above problem, we study coding for networks experiencing worst case bit errors, and with network codes over binary extension fields. We demonstrate that in this setup prior network error-correcting schemes can be arbitrarily far from achieving the optimal network throughput. A new transform metric for errors under the considered model is proposed. Using this metric, we replicate many of the classical results from coding theory. Specifically, new Hamming-type, Plotkin-type, and Elias-Bassalygo-type upper bounds on the network capacity are derived. A commensurate lower bound is shown based on Gilbert-Varshamov (GV)-type codes for error-correction. The GV codes used to attain the lower bound can be non-coherent, that is, they require neither prior knowledge of the network topology nor network coding kernels. We also propose a computationally efficient concatenation scheme. The rate achieved by our concatenated codes is characterized by a Zyablov-type lower bound. We provide a generalized minimum-distance decoding algorithm which decodes up to half the minimum distance of the concatenated codes. The end-to-end nature of our design enables our codes to be overlaid on the classical distributed random linear network codes. The other advantage of the end-to-end strategy over the link-by-link error-correction is that it reduces the computational cost at the internal nodes for performing error-correction.

Alice and Bob want to exchange information over an additive interference channel that also contains a malicious eavesdropper-jammer James who aims to disrupt this two-way communication. In the baseline model (motivated by wireless jamming scenarios), Alice and Bob transmit length-n q-ary encodings xAand xBrespectively of their own messages. James observes the interference pattern z = xA+ xB, and as a non-causal function of ζ and his knowledge of Alice and Bob's codebooks, chooses a jamming pattern s of power (Hamming weight) at most pn. Alice and Bob then both observe the interfered-jammed signal xA+ xB+ s, and aim to decode each others' messages despite the jamming pattern s. We demonstrate that in such a model, the fact of interference actually aids communication by allowing for communication to occur in each direction at a rate of 1 - Hq(p), i.e., the jammer can do no worse than act like “random noise”.1Interestingly, neither linear codes nor random codes (as “usually” defined) achieve this performance - we thus define and analyze a new class of codes we call linearish codes that do. We then extend our results to general q-ary additive-error channels with asymmetric jamming patterns (with potentially different powers) to Alice and Bob, and also demonstrate how to simultaneously ensure information-theoretic secrecy of both Alice and Bob's messages from James.

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.

This paper deals with an abstraction of a unified problem of drug discovery and pathogen identification. Pathogen identification involves the identification of disease-causing biomolecules. Drug discovery involves finding chemical compounds, called lead compounds, that bind to pathogenic proteins and eventually inhibit the function of the protein. In this paper, the lead compounds are abstracted as inhibitors, pathogenic proteins as defectives, and the mixture of “ineffective” chemical compounds and non-pathogenic proteins as normal items. A defective could be immune to the presence of an inhibitor in a test. So, a test containing a defective is positive if it does not contain its “associated” inhibitor. The goal of this paper is to identify the defectives, inhibitors, and their “associations” with high probability, or in other words, learn the immune defectives graph (IDG) efficiently through group tests. We propose a probabilistic non-adaptive pooling design, a probabilistic two-stage adaptive pooling design, and decoding algorithms for learning the IDG. For the two-stage adaptive-pooling design, we show that the sample complexity of the number of tests required to guarantee recovery of the inhibitors, defectives, and their associations with high probability, i.e., the upper bound, exceeds the proposed lower bound by a logarithmic multiplicative factor in the number of items. To be precise, lower and upper bounds of Ω((r + d) log n + rd) and O(rd log n) tests, respectively, are identified for classifying r inhibitors and d defectives amongst n items, and identifying their associations. For the nonadaptive pooling design, we show that the upper bound (given by O((r + d)2log n) tests) exceeds the proposed lower bound (given by max{Q((r + d)logn + rd), Ω((r2/log r) log n), Ω(d2)} tests) by at most a logarithmic multiplicative factor in the number of items.

The problem of one-way file synchronization, henceforth called “file updates”, is studied in this paper. Specifically, a client edits a file, where the edits are modeled by insertions and deletions (InDels). An old copy of the file is stored remotely at a data-centre, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the data-centre to update its old copy to the newly edited file. Two models for the source files and edit patterns are studied: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime, in which the number of insertions and deletions is a small (but constant) fraction of the length of the original file. For both models, information-theoretic lower bounds on the best possible compression rates that enable file updates are derived (up to first order terms). Conversely, a simple compression algorithm using dynamic programming (DP) and entropy coding (EC), henceforth called DP-EC algorithm, achieves rates that are within constant additive gap (which diminishes as the alphabet size increases) to information-theoretic lower bounds for both models. For the RPES-LtRRID model, a dynamic-programming-run-length-compression (DP-RLC) algorithm is proposed, which achieves a compression rate matching the information-theoretic lower bound up to first order terms. Therefore, when the insertion and deletion probabilities are small (such that first order terms dominate), the achievable rate by DP-RLC is nearly optimal for the RPES-LtRRID model.

In the q-ary online (causal) channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, . . . , xn) ∈ {0, 1, . . . , q - 1}nsymbol-by-symbol via a channel limited to at most p*n errors (symbol changes) and p*n erasures. The channel is "online" (i.e., "causal") in the sense that at the ith step of communication the channel decides whether to corrupt the ith symbol or not only based on its view of the symbols (x1,. . . , xi). This is in contrast to the classical adversarial channel in which the corruption is chosen with full knowledge of the sent codeword x. In this work we extend the results obtained in [1]-[4] (in which the capacities of binary online bit-flip-only channels, and separately binary online erasure-only channels were characterized). We here extend those prior results in two important ways. First, we obtain the capacity of q-ary online channels for general q (rather than just q = 2). Second, we analyze combined error-erasure corruption models (rather than studying them separately). Characterization of this much broader class of symmetric online channels gives a fuller understanding of the effects of causality on jamming adversaries. The extensions in this paper require novel approaches for both optimal code designs, and matching information-theoretic converse arguments.

We consider the problem of communicating a message m in the presence of a malicious jamming adversary (Calvin), who can erase an arbitrary set of up to pn bits, out of n transmitted bits X = (x1, ..., xn). The capacity of such a channel when Calvin is exactly causal, i.e. Calvin's decision of whether or not to erase bit xidepends on his observations (x1, ..., xi) was recently characterized [1], [2] to be 1 - 2p. In this work we show two (perhaps) surprising phenomena. Firstly, we demonstrate via a novel code construction that if Calvin is delayed by even a single bit, i.e. Calvin's decision of whether or not to erase bit xidepends only on (x1, ..., xi-1) (and is independent of the “current bit” xi) then the capacity increases to 1 - p when the encoder is allowed to be stochastic. Secondly, we show via a novel jamming strategy for Calvin that, in the single-bit-delay setting, if the encoding is deterministic (i.e. the transmitted codeword X is a deterministic function of the message m) then no rate asymptotically larger than 1 - 2p is possible with vanishing probability of error, hence stochastic encoding (using private randomness at the encoder) is essential to achieve the capacity of 1- p against a one-bit-delayed Calvin.

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.

Recent empirical results have demonstrated that generalized belief propagation (GBP) can be used to closely estimate the capacity of certain 2D runlength-limited constraints. We provide a partial analytical validation of these observations by showing that GBP yields a lower bound on the partition function of 2D Ising models with restricted grid size. While previous papers have proved that belief propagation (BP) can be used to obtain a lower bound on the partition function of 2D Ising models, this paper is the first work that analyzes GBP-based partition function approximations of 2D Ising models.

In this work we consider the communication setting in which a sender, Alice, wishes to communicate with a receiver, Bob, over a channel controlled by an adversarial entity, Calvin, who is myopic. Roughly speaking, for blocklength n, the codeword Xntransmitted by Alice is corrupted by Calvin who must base his adversarial decisions, on which characters of Xnto corrupt and how to corrupt them, not on the entire view of the codeword Xnbut on Zn, the image of Xnthrough a noisy memoryless channel. More specifically, our communication model may be described by two channels. A memoryless channel p(z|x) from Alice to Calvin, and an arbitrarily varying channel from Alice to Bob, p(y|x, s) governed by a states Sndetermined by Calvin. In standard adversarial channels, the states Snmay depend on the codeword Xn, however in our setting Sndepends only on Calvin's view Zn. The myopic channel captures a broad range of channels and bridges between the standard models of memoryless and adversarial (zero error) channels. In this work we present upper and lower bounds on the capacity of myopic channels. For a number of special cases of interest we show that our bounds are tight. We extend our results to the setting of secure communication in which we require that the transmitted message remain secret from Calvin. For example, we show that if (i) Calvin may flip at most a p fraction of the bits communicated between Alice and Bob, and (ii) Calvin views Xnthrough a binary symmetric channel with parameter q, then once Calvin is “sufficiently myopic” (in this case, when q > p), then the optimal communication rate is that of an adversary who is “blind” (that is, an adversary that does not see Xnat all), which is 1-H(p) for standard communication, and H(q)-H(p) for secure communication. A similar phenomena exists for our general model of communication.

This paper abstracts the unified problem of drug discovery and pathogen identification as an inhibitor-defective classification problem and learning of “association pattern” between the inhibitors and defectives. We refer to the “association graph” between the inhibitors and defectives as the Immune-Defectives Graph (IDG). Here, the expression of a defective might be inhibited by a subset of the inhibitors rather than all the inhibitors as in the well-known 1-inhibitor model. A test containing a defective is positive iff it does not contain its associated inhibitor. The goal of this paper is to identify the defectives, inhibitors, and their “associations” with high probability, or in other words, learn the IDG using group tests. We propose a probabilistic non-adaptive pooling design, a probabilistic two-stage adaptive pooling design and decoding algorithms for learning the IDG. The sample complexity of the number of tests required for the proposed two-stage adaptive pooling design is shown to be close to the lower bound, while that for the proposed non-adaptive pooling design is close to the lower bound in the large inhibitor regime.

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.

Group testing with inhibitors (GTI) introduced by Farach at al. is studied in this paper. There are three types of items, d defectives, r inhibitors and n−d−r normal items in a population of n items. The presence of any inhibitor in a test can prevent the expression of a defective. For this model, we propose a probabilistic non-adaptive pooling design with a low complexity decoding algorithm. We show that the sample complexity of the number of tests required for guaranteed recovery with vanishing error probability using the proposed algorithm scales as T = O(d log n) and equation in the regimes r = O(d) and d = o(r) respectively. In the former regime, the number of tests meets the lower bound order while in the latter regime, the number of tests is shown to exceed the lower bound order by a log r over d multiplicative factor. The decoding complexity of the proposed decoding algorithm scales as O(nT).

A client/encoder edits a file, as modeled by an insertion-deletion (InDel) process. An old copy of the file is stored remotely at a data-centre/decoder, and is also available to the client. We consider the problem of throughput- and computationally-efficient communication from the client to the data-centre, to enable the server to update its copy to the newly edited file. We study two models for the source files/edit patterns: the random pre-edit sequence left-to-right random InDel (RPES-LtRRID) process, and the arbitrary pre-edit sequence arbitrary InDel (APES-AID) process. In both models, we consider the regime in which the number of insertions/deletions is a small (but constant) fraction of the original file. For both models we prove information-theoretic lower bounds on the best possible compression rates that enable file updates. Conversely, our compression algorithms use dynamic programming (DP) and entropy coding, and achieve rates that are approximately optimal.

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.

In the binary online (or "causal") channel coding model, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1,...,xn) ∈ {0,1}n bit by bit via a channel limited to at most pn corruptions. The channel is "online" in the sense that at the ith step of communication the channel decides whether to corrupt the ith bit or not based on its view so far, i.e., its decision depends only on the transmitted bits (x1,...,xi). This is in contrast to the classical adversarial channel in which the error is chosen by a channel that has full knowledge of the transmitted codeword x.

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.

We consider a new group testing model wherein each item is a binary random variable defined by an a priori probability of being defective. We assume that each probability is small and that items are independent, but not necessarily identically distributed. The goal of group testing algorithms is to identify with high probability the subset of defectives via non-linear (disjunctive) binary measurements. Our main contributions are two classes of algorithms: (1) adaptive algorithms with tests based either on a maximum entropy principle, or on a Shannon-Fano/Huffman code; (2) non-adaptive algorithms. Under loose assumptions and with high probability, our algorithms only need a number of measurements that is close to the information-theoretic lower bound, up to an explicitly-calculated universal constant factor.

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.

We consider some computationally efficient and provably correct algorithms with near-optimal sample complexity for the problem of noisy nonadaptive group testing. Group testing involves grouping arbitrary subsets of items into pools. Each pool is then tested to identify the defective items, which are usually assumed to be sparse. We consider nonadaptive randomly pooling measurements, where pools are selected randomly and independently of the test outcomes. We also consider a model where noisy measurements allow for both some false negative and some false positive test outcomes (and also allow for asymmetric noise, and activation noise). We consider three classes of algorithms for the group testing problem (we call them specifically the coupon collector algorithm, the column matching algorithms, and the LP decoding algorithms-the last two classes of algorithms (versions of some of which had been considered before in the literature) were inspired by corresponding algorithms in the compressive sensing literature. The second and third of these algorithms have several flavors, dealing separately with the noiseless and noisy measurement scenarios. Our contribution is novel analysis to derive explicit sample-complexity bounds-with all constants expressly computed-for these algorithms as a function of the desired error probability, the noise parameters, the number of items, and the size of the defective set (or an upper bound on it). We also compare the bounds to information-theoretic lower bounds for sample complexity based on Fano's inequality and show that the upper and lower bounds are equal up to an explicitly computable universal constant factor (independent of problem parameters).

We consider the problem of communicating information over a network secretly and reliably in the presence of a hidden adversary who can eavesdrop and inject malicious errors. We provide polynomial-time distributed network codes that are information-theoretically rate-optimal for this scenario, improving on the rates achievable in prior work by Ngai Our main contribution shows that as long as the sum of the number of links the adversary can jam (denoted by ZO) and the number of links he can eavesdrop on (denoted by ZI) is less than the network capacity (denoted by C) (i.e., ), our codes can communicate (with vanishingly small error probability) a single bit correctly and without leaking any information to the adversary. We then use this scheme as a module to design codes that allow communication at the source rate of C- ZO when there are no security requirements, and codes that allow communication at the source rate of C- ZO- ZI while keeping the communicated message provably secret from the adversary. Interior nodes are oblivious to the presence of adversaries and perform random linear network coding; only the source and destination need to be tweaked. We also prove that the rate-region obtained is information-theoretically optimal. In proving our results, we correct an error in prior work by a subset of the authors in this paper.

This paper studies rateless network error correction codes for reliable multicast in the presence of adversarial errors. We present rateless coding schemes for two adversarial models, where the source sends more redundancy over time, until decoding succeeds. The first model assumes there is a secret channel between the source and the destination that the adversaries cannot overhear. The rate of the channel is negligible compared to the main network. In the second model the source and destination share random secrets independent of the input information. The amount of secret information required is negligible compared to the amount of information sent. Both schemes are capacity optimal, distributed, polynomial-time and end-to-end in that other than the source and destination nodes, other intermediate nodes carry out classical random linear network coding.

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 analyze inter-session network coding in a wired network using game theory. We assume that users are selfish and act as strategic players to maximize their own utility, which leads to a resource allocation game among users. In particular, we study a butterfly network, where a bottleneck link is shared by network coding and routing flows. We assume that network coding is performed using pairwise XOR operations. We prove the existence of Nash equilibrium for a wide range of utility functions. We also show that the number of Nash equilibria can be large (even infinite) for certain choices of parameters. This is in sharp contrast to a similar game setting with traditional packet forwarding, where the Nash equilibrium is always unique. We characterize the worst-case efficiency bound, i.e., the Price-of-Anarchy (PoA), compared to an optimal and cooperative network design. We show that by using a discriminatory pricing scheme which charges encoded and forwarded packets differently, we can improve the PoA in comparison with the case where a single pricing scheme is used. However, even when a discriminatory pricing scheme is used, the PoA is still worse than for the case when network coding is not applied. This implies that, although inter-session network coding can improve performance compared to routing, it is much more sensitive to users' strategic behavior.

In this paper, we consider the communication of information in the presence of an online adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codewordx=(x1,...,xn) symbol-by-symbol over a communication channel. The adversarial jammer can view the transmitted symbolsxione at a time and can change up to ap-fraction of them. However, for each symbolxi, the jammer's decision on whether to corrupt it or not (and on how to change it) must depend only onxjforj≤i. This is in contrast to the “classical” adversarial jammer which may base its decisions on its complete knowledge ofx. More generally, for a delay parameter δ ∈ (0,1), we study the scenario in which the jammer's decision on the corruption ofximust depend solely onxjforj≤i-δn. In this study, the transmitted symbols are assumed to be over a sufficiently large field F. The sender and receiver do not share resources such as common randomness (though the sender is allowed to use stochastic encoding). We present a tight characterization of the amount of information one can transmit in both the 0-delay and, more generally, the δ-delay online setting. We show that for 0-delay adversaries, the achievable rate asymptotically equals that of the classical adversarial model. For positive values of δ, we consider two types of jamming: additive and overwrite. We also extend our results to a jam-or-listen online model, where the online adversary can either jam a symbol or eavesdrop on it. We present computationally efficient achievability schemes even against computationally unrestricted jammers.

In this paper, we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codewordx=(x1, ...,xn) bit-by-bit over a communication channel. The sender and the receiver do not share common randomness. The adversarial jammer can view the transmitted bitsxione at a time and can change up to ap-fraction of them. However, the decisions of the jammer must be made in a causal manner. Namely, for each bitxi, the jammer's decision on whether to corrupt it or not must depend only onxjforj≤i. This is in contrast to the “classical” adversarial jamming situations in which the jammer has no knowledge ofx, or knowsxcompletely. In this study, we present upper bounds (that hold under both the average and maximal probability of error criteria) on the capacity which hold for both deterministic and stochastic encoding schemes.

Cut-set bounds are not, in general, tight for all classes of network communication problems. In this paper, we introduce a new technique for proving converses for the problem of transmission of correlated sources in networks, which results in bounds that are tighter than the corresponding cut-set bounds. We also define the concept of “uncertainty region” which might be of independent interest. We provide a full characterization of this region for the case of two correlated random variables. The bounding technique works as follows: on one hand, we show that if the communication problem is solvable, the uncertainty of certain random variables in the network with respect to imaginary parties that have partial knowledge of the sources must satisfy some constraints that depend on the network architecture. On the other hand, the same uncertainties have to satisfy constraints that only depend on the joint distribution of the sources. Matching these two leads to restrictions on the statistical joint distribution of the sources in communication problems that are solvable over a given network architecture. Our technique also provides nontrivial outer bounds for communication problems with secrecy constraints.

The problem of maximum rate achievable with analog network coding for a unicast communication over a layered wireless relay network with directed links is considered. A relay node performing analog network coding scales and forwards the signals received at its input. Recently this problem has been considered under two assumptions: (A) each relay node scales its received signal to the upper bound of its transmit power constraint, (B) the relay nodes in specific subsets of the network operate in the high-SNR regime. We establish that assumption (A), in general, leads to suboptimal end-to-end rate. We also characterize the performance of analog network coding in a class of symmetric layered networks without assumption (B). The key contribution of this work is a lemma that states that in a layered relay network a globally optimal set of scaling factors for the nodes that maximizes the end-to-end rate can be computed layer-by-layer. Specifically, a rate-optimal set of scaling factors for the nodes in a layer is the one that maximizes the sum-rate of the nodes in the next layer. This critical insight allows us to characterize analog network coding performance in network scenarios beyond those that can be analyzed using the existing approaches. We illustrate this by computing the maximum rate achievable with analog network coding in one particular layered network, in various communication scenarios.

We present computationally efficient and provably correct algorithms with near-optimal sample-complexity for noisy non-adaptive group testing. Group testing involves grouping arbitrary subsets of items into pools. Each pool is then tested to identify the defective items, which are usually assumed to be sparsely distributed. We consider random non-adaptive pooling where pools are selected randomly and independently of the test outcomes. Our noisy scenario accounts for both false negatives and false positives for the test outcomes. Inspired by compressive sensing algorithms we introduce four novel computationally efficient decoding algorithms for group testing, CBP via Linear Programming (CBP-LP), NCBP-LP (Noisy CBP-LP), and the two related algorithms NCBP-SLP+ and NCBP-SLP- (“Simple” NCBP-LP). The first of these algorithms deals with the noiseless measurement scenario, and the next three with the noisy measurement scenario. We derive explicit sample-complexity bounds - with all constants made explicit - for these algorithms as a function of the desired error probability; the noise parameters; the number of items; and the size of the defective set (or an upper bound on it). We show that the sample-complexities of our algorithms are near-optimal with respect to known information-theoretic bounds.

In this work we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, ..., xn) bit-by-bit over a communication channel. The adversarial jammer can view the transmitted bits xione at a time, and can change up to a p-fraction of them. However, the decisions of the jammer must be made in a causal manner. Namely, for each bit xithe jammer's decision on whether to corrupt it or not must depend only on xjfor j ≤ i. This is in contrast to the “classical” adversarial jammer which may base its decisions on its complete knowledge of x. Binary channels with causal adversarial jammers have seen recent studies in which both lower bounds and upper bounds on their capacity is derived. In this work, we present improved upper bounds on the capacity which hold for both deterministic and stochastic encoding schemes.

A communication scenario where a source communicates with a destination over a directed layered relay network is considered. Each relay performs analog network coding where it scales and forwards the signals received at its input. In this scenario, we address the question: What portion of the maximum end-to-end achievable rate can be maintained if only a fraction of relay nodes available at each layer are used? We consider, in particular, the Gaussian diamond network and a class of symmetric layered networks. For these networks we provide upper bounds on additive and multiplicative gaps between the optimal analog network coding performance when all N relays in each layer are used and when only k such relays are are used, k <; N (network simplification). We show that asymptotically (in source power), the additive gap increases at most logarithmically with ratio N/k and the number of layers, and the corresponding multiplicative gap increases at most linearly with ratio N/k and is independent of the number of layers in the layered network. To the best of our knowledge, this work offers the first characterization of the performance of network simplification in general layered amplify-and-forward relay networks. Further, unlike most of the current approximation results that attempt to bound optimal rates either within an additive gap or a multiplicative gap, our results suggest a new rate approximation scheme that allows for the simultaneous computation of additive and multiplicative gaps.

Passive network tomography uses end-to-end observations of network communications to characterize the network, for instance, to estimate the network topology and to localize random or adversarial faults. Under the setting of linear network coding, this work provides a comprehensive study of passive network tomography in the presence of network (random or adversarial) faults. To be concrete, this work is developed along two directions: 1) tomographic upper and lower bounds (i.e., the most adverse conditions in each problem setting under which network tomography is possible, and corresponding schemes (computationally efficient, if possible) that achieve this performance) are presented for random linear network coding (RLNC). We consider RLNC designed with common randomness, i.e., the receiver knows the random codebooks of all intermediate nodes. (To justify this, we show an upper bound for the problem of topology estimation in networks using RLNC without common randomness.) In this setting, we present the first set of algorithms that characterize the network topology exactly. Our algorithm for topology estimation with random network errors has time complexity that is polynomial in network parameters. For the problem of network error localization given the topology information, we present the first computationally tractable algorithm to localize random errors, and prove that it is computationally intractable to localize adversarial errors. 2) New network coding schemes are designed that improve the tomographic performance of RLNC while maintaining the desirable low-complexity, throughput-optimal, distributed linear network coding properties of RLNC. In particular, we design network codes based on Reed–Solomon codes so that a maximal number of adversarial errors can be localized in a computationally efficient manner even without the information of network topology. The tomography schemes proposed in the paper can be used to monitor networks with other faults such as packet losses and link delays, etc.

Random linear network codes can be designed and implemented in a distributed manner, with low computational complexity. However, these codes are classically implemented over finite fields whose size depends on some global network parameters (size of the network, the number of sinks) that may be unknown prior to code design. Also, the entire network code may have to be redesigned when a new node joins. In this work, we present the first universal and robust distributed linear network coding schemes. Our schemes are universal since they are independent of all network parameters. They are robust since in case nodes join or leave, the remaining nodes do not need to change their coding operations and the receivers can still decode. They are distributed since nodes need only have topological information about the part of the network upstream of them, which can be naturally streamed as part of the communication protocol. We present both probabilistic and deterministic schemes that are all asymptotically rate-optimal in the coding block-length, and have guarantees of correctness. Our probabilistic designs are computationally efficient, with order-optimal complexity. Our deterministic designs guarantee zero error decoding, albeit via codes with high computational complexity in general. Our coding schemes are based on network codes over “scalable fields”. Instead of choosing coding coefficients from one field at every node as in, each node uses linear coding operations over an “effective field-size” which depends on the node's distance from the source node. The analysis of our schemes requires technical tools that may be of independent interest. In particular, we generalize the Schwartz-Zippel lemma by proving a nonuniform version, wherein variables are chosen from sets of possibly different sizes. We also provide a novel robust distributed algorithm to assign unique IDs to network nodes.

Cut-set bounds on achievable rates for network communication protocols are not in general tight. In this paper we introduce a new technique for proving converses for the problem of transmission of correlated sources in networks, that results in bounds that are tighter than the corresponding cut-set bounds. We also define the concept of “uncertainty region” which might be of independent interest. We provide a full characterization of this region for the case of two correlated random variables. The bounding technique works as follows: on one hand we show that if the communication problem is solvable, the uncertainty of certain random variables in the network with respect to imaginary parties that have partial knowledge of the sources must satisfy some constraints that depend on the network architecture. On the other hand, the same uncertainties have to satisfy constraints that only depend on the joint distribution of the sources. Matching these two leads to restrictions on the statistical joint distribution of the sources in communication problems that are solvable over a given network architecture.

In this work, we define delay invariant convolutional network codes which guarantee multicast communication at asymptotically optimal rates in networks with arbitrary delay patterns. We show the existence of such a code over every symbol field. Moreover, the code can be constructed with high probability when coding coefficients are independently and uniformly chosen from a sufficiently large set of coding operations. On the other hand, if the symbol field is no smaller than the number of receivers, we devise a method to efficiently construct a delay invariant convolutional network code with scalar coding coefficients.

A general class of wireless relay networks with a single source-destination pair is considered. Intermediate nodes in the network employ an amplify-and-forward scheme to relay their input signals. In this case the overall input-output channel from the source via the relays to the destination effectively behaves as an intersymbol interference channel with colored noise. Unlike previous work we formulate the problem of the maximum achievable rate in this setting as an optimization problem with no assumption on the network size, topology, and signal-to-noise ratio. Previous work considered only scenarios wherein relays use all their power to amplify their received signals. We demonstrate that this may not always maximize the achievable rate in amplify-and-forward relay networks. The proposed formulation allows us to not only recover known results on the performance of the amplify-and-forward schemes for some simple relay networks but also characterize the performance of such schemes in more complex relay networks which cannot be addressed in a straightforward manner with existing approaches. Using cut-set arguments, we derive simple upper bounds on the capacity of general wireless relay networks. Through various examples, we show that a large class of amplify-and-forward relay networks can achieve rates within a constant factor of these upper bounds asymptotically in network parameters.

We consider network coding for networks experiencing worst-case bit-flip errors, and argue that this is a reasonable model for highly dynamic wireless network transmissions. We demonstrate that in this setup prior network error-correcting schemes can be arbitrarily far from achieving the optimal network throughput. We propose a new metric for errors under this model. Using this metric, we prove a new Hamming-type upper bound on the network capacity. We also show a commensurate lower bound based on GV-type codes that can be used for error-correction. The codes used to attain the lower bound are non-coherent (do not require prior knowledge of network topology). The end-to-end nature of our design enables our codes to be overlaid on classical distributed random linear network codes. Further, we free internal nodes from having to implement potentially computationally intensive link-by-link error-correction.

This work considers the multiple-access multicast error-correction scenario over a packetized network withzmalicious edge adversaries. The network has min-cutmand packets of lengthl, and each sink demands all information from the set of sourcesS. The capacity region is characterized for both a “side-channel” model (where sources and sinks share some random bits that are secret from the adversary) and an “omniscient” adversarial model (where no limitations on the adversary's knowledge are assumed). In the “side-channel” adversarial model, the use of a secret channel allows higher rates to be achieved compared to the “omniscient” adversarial model, and a polynomial-complexity capacity-achieving code is provided. For the “omniscient” adversarial model, two capacity-achieving constructions are given: the first is based on random subspace code design and has complexity exponential inlm, while the second uses a novel multiple-field-extension technique and has O(lm|S|) complexity, which is polynomial in the network size. Our code constructions are “end-to-end” in that all nodes except the sources and sinks are oblivious to the adversaries and may simply implement predesigned linear network codes (random or otherwise). Also, the sources act independently without knowledge of the data from other sources.

By allowing routers to randomly mix the information content in packets before forwarding them, network coding can maximize network throughput in a distributed manner with low complexity. However, such mixing also renders the transmission vulnerable to pollution attacks, where a malicious node injects corrupted packets into the information flow. In a worst case scenario, a single corrupted packet can end up corrupting all the information reaching a destination. In this paper, we propose RIPPLE, a symmetric key based in-network scheme for network coding authentication. RIPPLE allows a node to efficiently detect corrupted packets and encode only the authenticated ones. Despite using symmetric key based homomorphic Message Authentication Code (MAC) algorithms, RIPPLE achieves asymmetry by delayed disclosure of the MAC keys. Our work is the first symmetric key based solution to allow arbitrary collusion among adversaries. It is also the first to consider tag pollution attacks, where a single corrupted MAC tag can cause numerous packets to fail authentication farther down the stream, effectively emulating a successful pollution attack.

Network Tomography (or network monitoring) uses end-to-end measurements to characterize the network, such as estimating the network topology and localizing random or adversarial glitches. Under the setting that all nodes in the network perform random linear network coding, this work provides a comprehensive study of passive network tomography in the presence of network failures, in particular adversarial/random errors and adversarial/random erasures. Our results are categorized into two classes: 1. Topology Estimation. In the presence of both adversarial/random failures, we prove it is both necessary and sufficient for all nodes in the network to share common randomness, i.e., the receiver knows the random code-books of other nodes. Without such common randomness, we prove that in the presence of adversarial or random failures it is either theoretically impossible or computationally intractable to estimate topology accurately. With common randomness, we present the first set of algorithms for characterizing topology exactly. Our algorithms for topology estimation in the presence of random errors/erasures have polynomial-time complexity. 2. Failure Localization. Given the topology, we present the first polynomial time algorithms to localize random errors and adversarial erasures. For the problem of locating adversarial errors, we prove that it is intractable.

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.

In this work we consider the communication of information in the presence of a delayed adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, ..., xn) over a communication channel. The adversarial jammer can view the transmitted symbols xi one at a time, but must base its action (when changing xi) on xjfor j ≤ i - Δn, where Δ ∈ [0, 1] is a delay parameter. In this work, we study codes for a class of delayed adversaries, and for any delay Δ > 0 present a single letter characterization of the achievable communication rate in the presence of such adversaries.

The network communication scenario where one or more receivers request all the information transmitted by different sources is considered. We introduce the first polynomial-time (in network size) network codes that achieve any point inside the rate-region for the problem of multiple-source multicast in the presence of malicious errors, for any fixed number of sources. Our codes are fully distributed and different sources require no knowledge of the data transmitted by their peers. Our codes are “end-to-end”, that is, all nodes apart from the sources and the receivers are oblivious to the adversaries present in the network and simply implement random linear network coding.

A common assumption in the network coding literature is that the users are cooperative and will not pursue their own interests. However, this assumption can be violated in practice. In this paper, we analyze inter-session network coding in a wired network, assuming that the users are selfish and act as strategic players to maximize their own utility. We prove the existence of Nash equilibria for a wide range of utility functions. The number of Nash equilibria can be large (even infinite) under certain conditions, which is in sharp contrast to a similar game setting with traditional packet forwarding. We then characterize the worst-case efficiency bounds, i.e., the price-of-anarchy (PoA), compared to an optimal and cooperative network design. We show that by using a novel discriminatory pricing scheme that charges encoded and forwarded packets differently, we can improve PoA in comparison with the case where a single pricing scheme is being used. However, PoA is still worse than the case when network coding is not applied. This implies that inter-session network coding is more sensitive to strategic behavior. For example, for the case where only two network coding flows share a single bottleneck link, the efficiency at certain Nash equilibria can be as low as 48%. These results generalize the well-known result of guaranteed 67% efficiency bounds shown by Johari and Tsitsiklis for traditional packet forwarding networks.

Node-capacitated networks are networks in which the capacity constraint is put on every node. They have recently attract attention as a good model for Peer-to-Peer (P2P) overlay networks. Existing work gives results on networks with constraints of node upload capacities. In this paper, we consider networks with constraints on both node upload and node download capacity. For such networks, we investigate the rate optimality of routing versus network coding. In general, network coding achieves a larger rate region than routing. However, for some important communication scenarios, routing achieves the same rate region as network coding.

In this work we consider the communication of information in the presence of a causal adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (x1, ..., xn) bit-by-bit over a communication channel. The adversarial jammer can view the transmitted bits xione at a time, and can change up to a p-fraction of them. However, the decisions of the jammer must be made in an online or causal manner. Namely, for each bit xithe jammer's decision on whether to corrupt it or not (and on how to change it) must depend only on xjfor j ¿ i. This is in contrast to the ¿classical¿ adversarial jammer which may base its decisions on its complete knowledge of x. We present a non-trivial upper bound on the amount of information that can be communicated. We show that the achievable rate can be asymptotically no greater than min{1 - H(p), (1 - 4p)+}. Here H(.) is the binary entropy function, and (1 - 4p)+equals 1 - 4p for p ¿ 0.25, and 0 otherwise.

We provide a novel achievability proof of the Slepian-Wolf theorem for i.i.d. sources over finite alphabets. We demonstrate that random codes that are linear over the real field achieve the classical Slepian-Wolf rate region. For finite alphabets we show that decoding is equivalent to solving an integer program. The techniques used may be of independent interest for code design for a wide class of information theory problems, and for the field of compressed sensing.

Network coding substantially increases network throughput. But since it involves mixing of information inside the network, a single corrupted packet generated by a malicious node can end up contaminating all the information reaching a destination, preventing decoding. This paper introduces distributed polynomial-time rate-optimal network codes that work in the presence of Byzantine nodes. We present algorithms that target adversaries with different attacking capabilities. When the adversary can eavesdrop on all links and jam links, our first algorithm achieves a rate of , where is the network capacity. In contrast, when the adversary has limited eavesdropping capabilities, we provide algorithms that achieve the higher rate of . Our algorithms attain the optimal rate given the strength of the adversary. They are information-theoretically secure. They operate in a distributed manner, assume no knowledge of the topology, and can be designed and implemented in polynomial time. Furthermore, only the source and destination need to be modified; nonmalicious nodes inside the network are oblivious to the presence of adversaries and implement a classical distributed network code. Finally, our algorithms work over wired and wireless networks.

We consider the distributed computation of a function of random sources with minimal communication. Specifically, given two discrete memoryless sources, X and Y, a receiver wishes to compute f(X, Y) based on (encoded) information sent from X and Y in a distributed manner. A special case, f(X, Y) = (X, Y), is the classical question of distributed source coding considered by Slepian and Wolf (1973). Orlitsky and Roche (2001) considered a somewhat restricted setup when Y is available as side information at the receiver. They characterized the minimal rate at which X needs to transmit data to the receiver as the conditional graph entropy of the characteristic graph of X based on f. In our recent work (2006), we further established that this minimal rate can be achieved by means of graph coloring and distributed source coding (e.g. Slepian-Wolf coding). This characterization allows for the separation between "function coding" and "correlation coding." In this paper, we consider a more general setup where X and Y are both encoded (separately). This is a significantly harder setup for which to give a single-letter characterization for the complete rate region. We find that under a certain condition on the support set of X and Y (called the zigzag condition), it is possible to characterize the rate region based on graph colorings at X and Y separately. That is, any achievable pair of rates can be realized by means of first coloring graphs at X and Y separately (function coding) and then using Slepian-Wolf coding for these colors (correlation coding). We also obtain a single-letter characterization of the minimal joint rate. Finally, we provide simulation results based on graph coloring to establish the rate gains on real sequences

Network coding substantially increases network throughput. But since it involves mixing of information inside the network, a single corrupted packet generated by a malicious node can end up contaminating all the information reaching a destination, preventing decoding. This paper introducesthefirstdistributedpolynomial-timerate-optimalnetwork codes that work in the presence of Byzantine nodes. We present algorithms that target adversaries with different attacking capabilities. When the adversary can eavesdrop on all links and jam zOlinks , our first algorithm achieves a rate ofC- 2zO, where C is the network capacity. In contrast, when the adversary has limited snooping capabilities, we provide algorithms that achieve the higher rate ofC- zO. Our algorithms attain the optimal rate given the strength of the adversary. They are information-theoretically secure. They operate in a distributed manner, assume no knowledge of the topology, and can be designed and implemented in polynomial-time. Furthermore, only the source and destination need to be modified; non-malicious nodes inside the network are oblivious to the presence of adversaries and implement a classical distributed network code. Finally, our algorithms work over wired and wireless networks.

Network coding can substantially improve network throughput and performance. However, these codes have a major drawback if the network contains hidden malicious nodes that can eavesdrop on transmissions and inject fake information. In this scenario, even a small amount of information injected by a single malicious hidden node could mix with and contaminate much of the information inside the network, causing a decoding error. We improve on previous work by providing a polynomial- time, rate-optimal distributed network code design that functions even in the presence of a Byzantine adversary with substantial eavesdropping capabilities. As long as the sum of the adversary's jamming rate Zoand his eavesdropping rate ZIis less than the network capacity C, (Zo+ ZIo. The network codes we design are information-theoretically secure and assume no knowledge of network topology. Prior to transmission, no honest node knows the location or strength of the adversary. In our code design, interior nodes are oblivious to the presence of adversaries and implement a classical low- complexity distributed network code design; only the source and destination need to be changed. Finally, our codes work for both wired and wireless networks.

In this paper we consider the per-node run-time complexity of network multicast codes. We show that the randomized algebraic network code design algorithms described extensively in the literature result in codes that on average require a number of operations that scales quadratically with the block-length m of the codes. We then propose an alternative type of linear network code whose complexity scales linearly in m and still enjoys the attractive properties of random algebraic network codes. We also show that these codes are optimal in the sense that any rate-optimal linear network code must have at least a linear scaling in run-time complexity

We design codes to transmit information over a network, some subset of which is controlled by a malicious adversary. The computationally unbounded, hidden adversary knows the message to be transmitted, and can observe and change information over the part of the network being controlled. The network nodes do not share resources such as shared randomness or a private key. We first consider a unicast problem in a network with |epsiv parallel, unit-capacity, directed edges. The rate-region has two parts. If the adversary controls a fraction p < 0.5 of the |epsiv edges, the maximal throughput equals (1 - p) |epsiv|. We describe low-complexity codes that achieve this rate-region. We then extend these results to investigate more general multicast problems in directed, acyclic networks

The famous max-flow min-cut theorem states that a source node s can send information through a network (V, E) to a sink node t at a rate determined by the min-cut separating s and t. Recently, it has been shown that this rate can also be achieved for multicasting to several sinks provided that the intermediate nodes are allowed to re-encode the information they receive. We demonstrate examples of networks where the achievable rates obtained by coding at intermediate nodes are arbitrarily larger than if coding is not allowed. We give deterministic polynomial time algorithms and even faster randomized algorithms for designing linear codes for directed acyclic graphs with edges of unit capacity. We extend these algorithms to integer capacities and to codes that are tolerant to edge failures.

The problem of truly-lossless (Pe=0) distributed source coding requires knowledge of the joint statistics of the sources. In particular the locations of the zeroes of the probability mass functions (pmfs) are crucial for encoding at rates below (H(X),H(Y)). We consider the distributed computation of the empirical joint pmf Pnof a sequence of random variable pairs observed at physically separated nodes of a network. We consider both worst-case and average measures of information exchange and treat both exact calculation of Pnand a notion of approximation. We find that in all cases the communication cost grows linearly with the size of the input. Further, we consider the problem of determining whether the empirical pmf has a zero in a particular location and show that in most cases considered this also requires a communication cost that is linear in the input size