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

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.

We study message identification over the binary noisy permutation channel. When a vector is transmitted over the binary noisy permutation channel, the components of the vector first get permuted (re-ordered) by a randomly chosen permutation, and then each bit is flipped with probability$p$. It is known from earlier works that the message size for reliable communication over this channel can grow as$n^{R}$, where$R>0$is defined as the rate. The capacity, defined as the supremum of achievable rates$R$, is proved to be$1 / 2$. We study message identification with stochastic encoders over this channel, where a decoder wants to determine if a particular message of interest was transmitted. We show that message sizes growing as$2^{\epsilon_{n}} \sqrt{\frac{n}{\log n}}$are identifiable for any$\epsilon_{n} \rightarrow 0$. We also prove a strong converse result showing that for any sequence of identification codes with message size$2^{R_{n} \sqrt{n} \log n}$, where$R_{n} \rightarrow \infty$, the sum of Type-I and Type-II error probabilities approaches at least 1 as$n \rightarrow \infty$. Defining identification rate as the$\log \log$of the message size, normalized by$\log n$, our results imply the achievability of any rate below$1 / 2$and a strong converse above this rate. Our proof of the strong converse uses the idea of channel resolvability. We propose a novel deterministic quantization scheme for the quantization of a Hamming weight distribution by an$M$-type distribution when the distortion is measured on the Hamming weight distribution at the output of$\text{BSC}(p)$in total variation distance. This plays a key role in the converse proof.

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

We study message identification over a noiselessq-ary uniform permutation channel, where the transmitted vector is permuted by a permutation chosen uniformly at random. The channel is noiseless in the sense that the channel only rearranges the symbols in a different order, without changing the symbol values. For discrete memoryless channels (DMCs), the number of identifiable messages grows doubly exponentially. Identification capacity, the maximum second-order exponent, is known to be the same as the Shannon capacity of the DMC. Permutation channels support reliable communication of only polynomially many messages. A simple achievability result shows that message sizes growing as 2ϵnnq−1are identifiable for any ϵn→ 0. We prove two converse results. A “soft” converse shows that for anyR> 0, there is no sequence of identification codes with message size growing as 2Rnq−1with a power-law decay (n−μ) of the error probability. We also prove a “strong” converse showing that for any sequence of identification codes with message size 2Rnnq−1, where Rn→ ∞, the sum of Type I and Type II error probabilities approaches at least 1 asn→ ∞. To prove the soft converse, we use a sequence of steps to construct a new identification code with a simpler structure which relates to a set system, and then use a lower bound on the normalized maximum pairwise intersection of a set system. To prove the strong converse, we use results on approximation of distributions. The achievability and converse results are generalized to the case of coding over multiple blocks. We also show that under deterministic encoding, the number of messages that can be identified per block is the number of types, i.e., (n+q−1q−1), and this is same as the message size for reliable communication. We finally study message identification over aq-ary uniform permutation channel in the presence of causal block-wise feedback from the receiver, where the encoder receives an entiren-length received block after the transmission of the block is complete. We show that in the presence of feedback, the maximum number of identifiable messages grows doubly exponentially even under deterministic encoding, and we present a two-phase achievability scheme.

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

We study message identification over the binary uniform permutation channels. For DMCs, the number of identifiable messages grows doubly exponentially. Identification capacity, the maximum second-order exponent, is known to be the same as the Shannon capacity of a DMC. We consider a binary uniform permutation channel where the transmitted vector is permuted by a permutation chosen uniformly at random. Permutation channels support reliable communication of only polynomially many messages. While this implies a zero second-order identification rate, we prove a “soft” converse result showing that even non-zero first-order identification rates are not achievable with a power-law decay of error probability for identification over binary uniform permutation channels. To prove the converse, we use a sequence of steps to construct a new identification code with a simpler structure and then use a lower bound on the normalized maximum pairwise intersection of a set system on$\{0, \ldots, n\}$.

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

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

We consider the coded caching problem with an additional privacy constraint that a user should not get any information about the demands of the other users. We first show that a demand-private scheme for$N$files and$K$users can be obtained from a non-private scheme that serves only a subset of the demands for the$N$files and$NK$users problem. We further use this fact to construct a demand-private scheme for$N$files and$K$users from a particular known non-private scheme for$N$files and$NK-K+1$users. It is then demonstrated that, the memory-rate pair$(M,\min \{N,K\}(1-M/N))$, which is achievable for non-private schemes with uncoded transmissions, is also achievable under demand privacy. We further propose a scheme that improves on these ideas by removing some redundant transmissions. The memory-rate trade-off achieved using our schemes is shown to be within a multiplicative factor of 3 from the optimal when$K < N$and of 8 when$N \leq K$. Finally, we give the exact memory-rate trade-off for demand-private coded caching problems with$N\geq K=2$.

We study the fundamental problem of index coding under an additional privacy constraint that requires each receiver to learn nothing more about the collection of messages beyond its demanded messages from the server and what is available to it as side information. To enable such private communication, we allow the use of a collection of independent secret keys, each of which is shared amongst a subset of users and is known to the server. The goal is to study properties of the key access structures that make the problem feasible and then design encoding and decoding schemes efficient in the size of the server transmission as well as the sizes of the secret keys. We call this theprivate index codingproblem. We begin by characterizing the key access structures that make private index coding feasible. We also give conditions to check if a given linear scheme is a valid private index code. For up to three users, we characterize the rate region of feasible server transmission and key rates, and show that all feasible rates can be achieved using scalar linear coding and time sharing; we also show that scalar linear codes are sub-optimal for four receivers. The outer bounds used in the case of three users are extended to arbitrary number of users and seen as a generalized version of the well-known polymatroidal bounds for the standard non-private index coding. We also show that the presence of common randomness and private randomness does not change the rate region. Furthermore, we study the case where the server has the ability to multicast to any subset of users, and demonstrate how this flexibility can be used to provide privacy and characterize the minimum number of server multicasts required.

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

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

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

We consider the demand-private coded caching problem in a noiseless broadcast network. It is known from past works that a demand-private scheme for N files and K users can be obtained from a non-private scheme for N files and NK users. We first propose a scheme that improves on this idea by removing some redundant transmissions. The memory- rate trade-off achieved using this scheme is shown to be within a multiplicative factor of 3 from the optimal for all the memory regimes when KK = 2.

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

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

We consider 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.

We consider a function computation problem in a three-node wireless network. Nodes A and B observe two correlated sources X and Y, respectively, and want to compute a function f (X, Y). To achieve this, nodes A and B send messages to a relay node C at rates RA and RB, respectively. The relay C then broadcasts a message to A and B at rate RC. We allow block coding and study the achievable region of rate triples under both zero-error and E-error. As a preparation, we first consider a broadcast network from the relay to A and B. A and B have side information X and Y, respectively. The relay node C observes both X and Y and broadcasts an encoded message to A and B. We want to obtain the optimal broadcast rate such that A and B can recover the function f (X, Y) from the received message and their individual side information X and Y, respectively. For this problem, we show equivalence between E-error and zero-error computations-this gives a rate characterization for zero-error computation. As a corollary, this also gives a rate characterization for the relay network under zero error for a class of functions called component-wise one-to-one functions when the support set of pXY is full. For the relay network, the zero-error rate region for arbitrary functions is characterized in terms of graph coloring of some suitably defined probabilistic graphs. We then give a single-letter inner bound to this rate region. Furthermore, we extend the graph theoretic ideas to address the E-error problem and obtain a single-letter inner bound.

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 study the problem of index coding under the privacy requirement that receivers do not learn anything more than the messages they already have as side information and the message they want from the server. To achieve this private index coding, we consider the use of secret keys that are shared among various subsets of users and the server. We characterize key access structures that allow private index coding. For up to three receivers, we characterize the rate region of transmission and key rates and show that scalar coding is optimal; we also show that scalar linear codes are sub-optimal for four receivers. Furthermore, when no keys are available, we consider a weaker notion of privacy analogous to weak security. Finally, for a different setting in which the server is allowed to send messages exclusively to a subset of users, we study the number of transmissions required to achieve error-free decoding and privacy.

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.

We study a lossy source coding problem for a memoryless remote source. The source data is broadcast over an arbitrarily varying channel (AVC) controlled by an adversary. One output of the AVC is received as input at the encoder, and another output is received as side information at the decoder. The adversary is assumed to know the source data non-causally, and can employ randomized jamming strategies arbitrarily correlated to the source data. The decoder reconstructs the source data from the encoded message and the side information. We prove upper and lower bounds on the adversarial rate distortion function for the source under randomized coding. Furthermore, we present some interesting special cases of our general setup where the above bounds coincide, and thus, provide their complete rate distortion function characterization.

We study communication systems over the state-dependent channels in the presence of a malicious state-aware jamming adversary. The channel has a memoryless state with an underlying distribution. The adversary introduces a jamming signal into the channel. The message and the entire state sequence are known non-causally to both the encoder and the adversary. This state-aware adversary may choose an arbitrary jamming vector depending on the message and the state vector. Taking an arbitrarily varying channel (AVC) approach, we consider two setups, namely, the discrete memoryless Gel'fand-Pinsker AVC and the additive white Gaussian dirty paper (DP) AVC. We determine the randomized coding capacity of both the AVCs under a maximum probability of error criterion. Similar to other randomized coding setups, we show that the capacity is the same even under the average probability of error criterion. Though the adversary can choose an arbitrary vector jamming strategy, we prove that the adversary cannot affect the rate any worse than when it employs a memoryless strategy, which depends only on the instantaneous state. Thus, the AVC capacity characterization is given in terms of the capacity of the worst memoryless channels with state, induced by the adversary employing such memoryless jamming strategies. For the DP-AVC, it is further shown that among memoryless jamming strategies, none impact the communication more than a memoryless Gaussian jamming strategy which completely disregards the knowledge of the state. Thus, the capacity of the DP-AVC equals that of a standard additive white Gaussian noise (AWGN) channel with two independent sources of AWGN, i.e., the channel noise and the jamming noise.

In this paper, we study the problem of obtaining 1-of-2 string oblivious transfer (OT) between users Alice and Bob, in the presence of a passive eavesdropper Eve. The resource enabling OT in our setup is a noisy broadcast channel from Alice to Bob and Eve. Apart from the OT requirements between the users, Eve is not allowed to learn anything about the users' inputs. When Alice and Bob are honest-but-curious and the noisy broadcast channel is made up of two independent binary erasure channels (connecting Alice-Bob and Alice-Eve), we derive the 1-of-2 string OT capacity for both 2-privacy (when Eve can collude with either Alice or Bob) and 1-privacy (when no such collusion is allowed). We generalize these capacity results to 1-of-N string OT and study other variants of this problem. When Alice and/or Bob are malicious, we present a different scheme based on interactive hashing. This scheme is shown to be optimal for certain parameter regimes. We present a new formulation of multiple, simultaneous OTs between Alice-Bob and Alice-Cathy. For this new setup, we present schemes and outer bounds that match in all but one regime of parameters. Finally, we consider the setup where the broadcast channel is made up of a cascade of two independent binary erasure channels (connecting Alice-Bob and Bob-Eve) and 1-of-2 string OT is desired between Alice and Bob with 1-privacy. For this setup, we derive an upper and lower bound on the 1-of-2 string OT capacity which match in one of two possible parameter regimes.

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 oblivious transfer (OT) over OFDM and MIMO wireless communication systems where only the receiver knows the channel state information. The sender and receiver also have unlimited access to a noise-free real channel. Using a physical layer approach, based on the properties of the noisy fading channel, we propose a scheme for honest-but-curious parties that enables the transmitter to send obliviously one-of-two files, i.e., without knowing which one has been actually requested by the receiver, while also ensuring that the receiver does not get any information about the other file.

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.

We study oblivious transfer (OT) between Alice and Bob in the presence of an eavesdropper Eve over a degraded wiretapped binary erasure channel from Alice to Bob and Eve. In addition to the privacy goals of oblivious transfer between Alice and Bob, we require privacy of Alice and Bob's private data from Eve. In previous work we derived the OT capacity (in the honest-but-curious model) of the wiretapped binary independent erasure channel where the erasure processes of Bob and Eve are independent. Here we derive a lower bound on the OT capacity in the same secrecy model when the wiretapped binary erasure channel is degraded in favour of Bob.

We study the following private data transfer problem: Alice has a database of files. Bob and Cathy want to access a file each from this database (which may or may not be the same file), but each of them wants to ensure that their choices of file do not get revealed even if Alice colludes with the other user. Alice, on the other hand, wants to make sure that each of Bob and Cathy does not learn any more information from the database than the files they demand (the identities of which will be unknown to her). Moreover, they should not learn any information about the other files even if they collude. It turns out that it is impossible to accomplish this if Alice, Bob, and Cathy have access only to private randomness and noiseless communication links. We consider this problem when a binary erasure broadcast channel with independent erasures is available from Alice to Bob and Cathy in addition to a noiseless public discussion channel. We study the file-length-per-broadcast-channel-use rate in the honest-but-curious model. We focus on the case when the database consists of two files, and obtain the optimal rate. We then extend to the case of larger databases, and give upper and lower bounds on the optimal rate.

We consider zero error function computation in a three node wireless network. Nodes A and B observe X and Y respectively, and want to compute a function f(X, Y ) with zero error. To achieve this, nodes A and B send messages to a relay node C at rates RAand RBrespectively. The relay C then broadcasts a message to A and B at rate RCto help them compute f(X, Y ) with zero error. We allow block coding, and study the region of rate-triples (RA, RB, RC) that are feasible. The rate region is characterized in terms of graph coloring of some suitably defined probabilistic graphs. We give single letter inner and outer bounds which meet for some simple examples. We provide a sufficient condition on the joint distribution pXYunder which the relay can also compute f(X, Y ) if A and B can compute it with zero error.

We consider the problem of oblivious transfer (OT) over OFDM and MIMO wireless communication systems where only the receiver knows the channel state information. The sender and receiver also have unlimited access to a noise-free real channel. Using a physical layer approach, based on the properties of the noisy fading channel, we propose a scheme that enables the transmitter to send obliviously one-of-two files, i.e, without knowing which one has been actually requested by the receiver, while also ensuring that the receiver does not get any information about the other file.

Traditionally, the capacity region of a coherent fading multiple access channel (MAC) is analyzed in two popular contexts. In the first, a centralized system with full channel state information at the transmitters (CSITs) is assumed, and the transmit power and data-rate can be jointly chosen for every fading vector realization. On the other hand, in fast-fading links with distributed CSIT, the lack of full CSI is compensated by performing ergodic averaging over sufficiently many channel realizations. Notice that the distributed CSI may necessitate decentralized power-control for optimal data-transfer. Apart from these two models, the case of slow-fading links and distributed CSIT, though relevant to many systems, has received much less attention. In this paper, a block-fading additive white Gaussian noise MAC with full CSI at the receiver and distributed CSI at the transmitters is considered. The links undergo independent fading, but otherwise have arbitrary fading distributions. The channel statistics and respective long-term average transmit powers are known to all parties. We first consider the case where each encoder has knowledge only of its own link quality, and not of others. For this model, we compute the adaptive capacity region, i.e., the collection of average rate-tuples under blockwise coding/decoding such that the rate-tuple for every fading realization is inside the instantaneous MAC capacity region. The key step in our solution is an optimal rate allocation function for any given set of distributed power control laws at the transmitters. This also allows us to structurally characterize the optimal power control for a wide class of fading models. Further extensions are also proposed for the case where each encoder has additional partial CSI about the other links.

In this paper, the problem of writing on a dirty paper in the presence of jamming is examined. We consider an AWGN channel with an additive white Gaussian state and an additive adversarial jammer. The state is assumed to be known non-causally to the encoder and the jammer but not to the decoder. The capacity of the channel in the presence of a jammer is determined. A surprising result that this capacity is equal to the capacity of a relaxed version of the problem, where the state is also known non-causally to the decoder, is proved.

We study correlated jamming in joint source-channel communication systems. An i.i.d. source is to be communicated over a memoryless channel in the presence of a correlated jammer with non-causal knowledge of user transmission. This user-jammer interaction is modeled as a zero sum game. A set of conditions on the source and the channel is provided for the existence of a Nash equilibrium for this game, where the user strategy is uncoded transmission and the jammer strategy is i.i.d jamming. This generalizes a well-known example of uncoded communication of Gaussian sources over Gaussian channels with additive jamming. Another example, of a Binary Symmetric source over a Binary Symmetric channel with jamming, is provided as a validation of this result.

We consider oblivious transfer between Alice and Bob in the presence of an eavesdropper Eve when there is a broadcast channel from Alice to Bob and Eve. In addition to the secrecy constraints of Alice and Bob, Eve should not learn the private data of Alice and Bob. When the broadcast channel consists of two independent binary erasure channels, we derive the oblivious transfer capacity for both 2-privacy (where the eavesdropper may collude with either party) and 1-privacy (where there are no collusions).

We consider a multiple access system (MAC) with bursty arrivals. The transmissions are grouped into slots and the users are frame-synchronized. At the start of each time slot, variable sized packets independently arrive at each of the transmitting terminals. The packets are to be delivered to a common receiver by the end of the slot. Each terminal knows only its own arrival process, i.e. the packet-sizes at the rest of the terminals are unknown to each transmitter. The respective link gains from the transmitters to the receiver are assumed to be fixed and known to all. In this random access system, we propose schemes which will deliver the arriving data without any outage, under strict delay constraints. Our schemes are optimal in minimizing the total average power spent in data transport.

In secure multiparty computation, mutually distrusting users in a network want to collaborate to compute functions of data which is distributed among the users. The users should not learn any additional information about the data of others than what they may infer from their own data and the functions they are computing. Previous works have mostly considered the worst case context (i.e., without assuming any distribution for the data); Lee and Abbe (2014) is a notable exception. Here, we study the average case (i.e., we work with a distribution on the data) where correctness and privacy is only desired asymptotically. For concreteness and simplicity, we consider a secure version of the function computation problem of Körner and Marton (1979) where two users observe a doubly symmetric binary source with parameter p and the third user wants to compute the XOR. We show that the amount of communication and randomness resources required depends on the level of correctness desired. When zero-error and perfect privacy are required, the results of Data et al. (2014) show that it can be achieved if and only if a total rate of 1 bit is communicated between every pair of users and private randomness at the rate of 1 is used up. In contrast, we show here that, if we only want the probability of error to vanish asymptotically in blocklength, it can be achieved by a lower rate (binary entropy of p) for all the links and for private randomness; this also guarantees perfect privacy. We also show that no smaller rates are possible even if privacy is only required asymptotically.

We study oblivious transfer (OT) using a binary erasure broadcast channel from Alice to Bob and Charlie. Alice wants to establish independent OTs with Bob and Charlie with 2-privacy, i.e., where secrecy needs to be maintained even against pairs of parties in addition to against parties working on their own. We give an achievable rate-region in the honest-but-curious setting and show its optimality for a range of erasure probabilities.

We consider a block-fading Gaussian MAC under a local CSI model where the transmitters have access to their own fading states. The system requires that the joint transmission rate-vector should not be in outage in any block. The average rate-tuples that can be achieved in fading MAC under such local distributed CSI and outage-free transmission belong to the so called adaptive capacity region. We present the adaptive capacity region of MACs under fairly general fading distributions and local CSI. Our results considerably generalize the known sum-capacity solutions in literature, by evaluating the full capacity region. Our results also provide the adaptive capacity region for arbitrary given power allocation functions. We further extend our results to more general CSI models where each user has additional quantized CSI of the other links.

We consider a distributed MAC setting with block-wise flat fading links and full receiver CSI (channel state information). Of the L transmitters, a subset is assumed to have knowledge of the global CSI vector in each block, whereas the remaining users have access only to their respective link qualities, i.e. each one in the latter set is unaware of the quality of other links. Outage is not allowed in any communication block. We propose efficient power-allocation and rate-adaptation strategies which are sum-rate optimal when users in each subset observe identical fading distributions chosen from a class, which includes the popular Rayleigh, Ricean etc.

We consider a two-user block-fading MAC with distributed channel state information (CSI), where each user has access to only its own fading coefficients. The average rate-pairs of communication while employing within-block coding is known as the adaptive capacity region, where each user adapts the rate based on its perceived link gain. We evaluate the adaptive sum-capacity of MAC channels with general fading distributions, for discrete as well as continuous valued ones.

We consider in-network computation of an arbitrary function over an arbitrary communication network. A network with capacity constraints on the links is given. Some nodes in the network generate data, e.g., like sensor nodes in a sensor network. An arbitrary function of this distributed data is to be obtained at a terminal node. The structure of the function is described by a given computation schema, which in turn is represented by a directed tree. We design computing and communicating schemes to obtain the function at the terminal at the maximum rate. For this, we formulate linear programs to determine network flows that maximize the computation rate. We then develop a fast combinatorial primal-dual algorithm to obtain near-optimal solutions to these linear programs. As a subroutine for this, we develop an algorithm for finding the minimum cost embedding of a tree in a network with any given set of link costs. We then briefly describe extensions of our techniques to the cases of multiple terminals wanting different functions, multiple computation schemas for a function, computation with a given desired precision, and to networks with energy constraints at nodes.

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.

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 directed acyclic network is considered where all the terminals need to recover the sum of the symbols generated at all the sources. We call such a network a sum-network. It is shown that there exists a solvably (and linear solvably) equivalent sum-network for any multiple-unicast network, and thus for any directed acyclic communication network. It is also shown that there exists a linear solvably equivalent multiple-unicast network for every sum-network. It is shown that for any set of polynomials having integer coefficients, there exists a sum-network which is scalar linear solvable over a finite field F if and only if the polynomials have a common root in F. For any finite or cofinite set of prime numbers, a network is constructed which has a vector linear solution of any length if and only if the characteristic of the alphabet field is in the given set. The insufficiency of linear net- work coding and unachievability of the network coding capacity are proved for sum-networks by using similar known results for communication networks. Under fractional vector linear network coding, a sum-network and its reverse network are shown to be equivalent. However, under nonlinear coding, it is shown that there exists a solvable sum-network whose reverse network is not solvable.

We consider in-network computation of an arbitrary function over an arbitrary communication network. We consider the same model as our earlier work in [1]. The given network consists of directed/undirected links with capacity constraints, some source nodes which generate data, and other intermediate forwarding nodes. An arbitrary function of this distributed data is to be computed at a terminal node. The structure of the function is described by a given computation schema represented by a directed tree. In our earlier work, we presented a linear program to define the maximum rate of computation, and then introduced a notion of flow-conservation suitable in this context so as to come up with a flow-conservation based linear program which can be solved in polynomial time. In this paper, we develop a combinatorial primal-dual algorithm to obtain (1-∈)-approximate solutions to these linear programs. As a part of this, we present an algorithm to find a minimum-cost embedding in a network of weighted links--which is of independent interest. We then describe application of our techniques to other practically interesting problems of multiple terminals wanting different functions, computation with a given desired precision, and to networks with energy constraints at nodes.

We consider in-network computation of an arbitrary function over an arbitrary communication network. A network with capacity constraints on the links is given. Some nodes in the network generate data, e.g., sensor nodes in a sensor network. An arbitrary function of this distributed data is to be obtained at a terminal node. The structure of the function is described by a given computation schema, which in turn is represented by a directed tree. We define a new notion of conservation of flow suitable in this setup and design computing and communicating schemes to obtain the function at the terminal at the maximum rate. For this, we formulate linear programs to determine network flows that maximize the computation rate. Our approach introduces the network flow techniques to the distributed function computation setup where such a scope was hitherto unsuspected due to the lack of traditional conservation of flow.

We consider the problem of finding optimal, fair and distributed power-rate strategies to achieve the sum capacity of the Gaussian multiple-access block-fading channel. The transmitters have access to only their own fading coefficients, while the receiver has access to all of the fading coefficients. We propose a distributed strategy called the `midpoint' strategy which is optimal when the system cannot tolerate outage. In addition, we demonstrate a successive decoding scheme that can achieve this maximal sum-rate. In presence of outage, we show that the strategies based on a single threshold are suboptimal.

We consider the problem of collaborative filtering from a channel coding perspective. We model the underlying rating matrix as a finite alphabet matrix with block constant structure. The observations are obtained from this underlying matrix through a discrete memoryless channel with a noisy part representing noisy user behavior and an erasure part representing missing data. Moreover, the clusters over which the underlying matrix is constant are unknown. We establish a threshold result for this model: if the largest cluster size is smaller than C1log(mn) (where the rating matrix is of size m × n), then the underlying matrix cannot be recovered with any estimator, but if the smallest cluster size is larger than C2log(mn), then we show a polynomial time estimator with asymptotically vanishing probability of error. In the case of uniform cluster size, not only the order of the threshold, but also the constant is identified.

We consider a directed acyclic network where there are two source-terminal pairs and the terminals need to receive the symbols generated at the respective sources. Each source independently generates an i.i.d. random process over the same alphabet. Each edge in the network is error-free, delay-free, and can carry one symbol from the alphabet per use. We give a simple necessary and sufficient condition for being able to simultaneously satisfy the unicast requirements of the two source-terminal pairs at rate-pair (1,1) using vector network coding. The condition is also sufficient for doing this using only "XOR" network coding and is much simpler compared to the necessary and sufficient conditions known from previous work. Our condition also yields a simple characterization of the capacity region of a double-unicast network which does not support the rate-pair (1,1).

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.

We consider a directed acyclic network with three sources and three terminals such that each source independently generates one symbol from a given field F and each terminal wants to receive the sum (over F) of the source symbols. Each link is error-free, delay-free and can carry one symbol from the field in each use. We call such a network a 3-source 3-terminal (3s/3t) sum-network. We give a necessary and sufficient condition for a 3s/3t sum-network to be solvable over any field. Some lemmas provide interesting simpler sufficient conditions for the same. We show that linear codes, and in most cases XOR codes, are sufficient for this problem for 3s/3t though they are known to be insufficient for arbitrary number of sources and terminals. We also prove a recent conjecture that the capacity of a 3s/3t sum-network is either 0, 2/3 or ≥ 1.

Motivated by recommendation systems, we consider the problem of estimating block constant binary matrices (of size m × n) from sparse and noisy observations. The observations are obtained from the underlying block constant matrix after unknown row and column permutations, erasures, and errors. We derive upper and lower bounds on the achievable probability of error. For fixed erasure and error probability, we show that there exists a constant C1such that if the cluster sizes are less than C1ln(mn), then for any algorithm the probability of error approaches one as m, n ¿ ¿. On the other hand, we show that a simple polynomial time algorithm gives probability of error diminishing to zero provided the cluster sizes are greater than C2ln(mn) for a suitable constant C2.

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 consider directed acyclic sum-networks with m sources and n terminals where the sources generate symbols from an arbitrary alphabet field F, and the terminals need to recover the sum of the sources over F. We show that for any co-finite set of primes, there is a sum-network which is linearly solvable only over fields of characteristics belonging to that set. We further construct a sum-network where a scalar linear solution exists over all fields other than the binary field F2. We also show that a sum-network is linearly solvable over a field if and only if its reverse network is linearly solvable over the same field.

Tight closed form lower bounds for the average bit error rate (BER) are derived for a dual hop cooperative network employing nonregenerative relays for the multiple input multiple output (MIMO) relay channel experiencing Rayleigh fading. The bounds are obtained for three different nonregenerative relaying schemes. The lower bounds for the BER are obtained using the moment generating function (MGF) approach by evaluating the MGF of the end-to-end equivalent signal to noise ratio (SNR) of the system. From the BER expressions obtained, we also show that the diversity order for the MIMO relay cooperative system with each relay having M antennas increases approximately by a factor M from that of a system with single-antenna relays. Simulation results confirm that the analytical expressions for the lower bounds are very tight and can thus be used to get approximate values of the BER.

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.

This paper describes the existence of good self-dual quasicyclic codes. In this paper, with the assumption that there are infinite primes p for which 2 is primitive, we prove that there exist classes of self-dual 2p-quasicyclic codes and Type II 8p-quasicyclic codes of length respectively 2p/sup 2/ and 8p/sup 2/ which asymptotically meet the Gilbert-Varshamov bound.

Algebraic structure of codes over F q , closed under arbitrary abelian group G of permutations with exponent relatively prime to q, called G-invariant codes, is investigated using a transform domain approach. In particular, this general approach unveils algebraic structure of quasi-cyclic codes, abelian codes, cyclic codes, and quasi-abelian codes with restriction on G to appropriate special cases. Dual codes of G-invariant codes and self-dual G-invariant codes are characterized. The number of G-invariant self-dual codes for any abelian group G is found. In particular, this gives the number of self-dual l-quasi-cyclic codes of length ml over F q when (m,q)=1. We extend Tanner's approach for getting a bound on the minimum distance from a set of parity check equations over an extension field and outline how it can be used to get a minimum distance bound for a G-invariant code. Karlin's decoding algorithm for a systematic quasi-cyclic code with a single row of circulants in the generator matrix is extended to the case of systematic quasi-abelian codes. In particular, this can be used to decode systematic quasi-cyclic codes with columns of parity circulants in the generator matrix.

For a long time, asymptotically good self-dual codes have been known to exist. Asymptotically good 2-quasicyclic codes of rate 1/2 have also been known to exist for a long time. Recently, it was proved that there are binary self-dual n/3-quasicyclic codes of length n asymptotically meeting the Gilbert-Varshamov bound. Unlike 2-quasicyclic codes, which are defined to have a cyclic group of order n/2 as a subgroup of their permutation group, the n/3-quasicyclic c codes are defined with a permutation group of fixed order of 3. So, from the decoding point of view, 2-quasicyclic c codes are preferable to n/3-quasicyclic c codes. In this correspondence, with the assumption that there are infinite primes p with respect to (w r t.) which 2 is primitive, we prove that there exist classes of self-dual 2p-quasicyclic c codes and Type II 8p-quasicyclic c codes of length respectively 2p/sup 2/ and 8p/sup 2/ which asymptotically meet the Gilbert-Varshamov bound. When compared with the order of the defining permutation groups, these classes of codes lie between the 2-quasicyclic c codes and the n/3-quasicyclic c codes of length n, considered in previous works.

Recently, Blackford and Ray-Chaudhuri used transform domain techniques to permutation groups of cyclic codes over Galois rings. They used the same technique to find a set of necessary and sufficient conditions for extended cyclic codes of length 2/sup m/ over any subring of GR(4,m) to be affine invariant. Here, we use the same technique to find a set of necessary and sufficient conditions for extended cyclic codes of length p/sup m/ over any subring of GR(p/sup e/,m) to be affine invariant, for e=2 with arbitrary p and for p=2 with arbitrary e. These are used to find two new classes of affine invariant Bose-Chaudhuri-Hocquenghem (BCH) and generalized Reed-Muller (GRM) codes over Z/sub 2//sup e/ for arbitrary e and a class of affine invariant BCH codes over Z/sub p//sup 2/ for arbitrary prime p.