In this paper, we study epidemic detection in a geographical region where a center for disease control (CDC) relies on two distinct testing agencies to assess an outbreak. Each agency operates within a defined area, and the quality of their testing performance can vary, leading to missed detections or false negatives. The CDC observes the test results from each agency and must detect whether an outbreak is occurring (or not). The CDC’s role is to perform distributed spatial sampling, i.e., define specific regions tested by each agency to optimize the collective detection error and enhance the reliability of epidemic detection. We refer to this decision-making challenge as the CDC problem. In this work, we focus on the CDC problem under the assumptions that (i) the epidemic is modeled as a spatially homogeneous Poisson counting process, and (ii) testing results are only affected by missed detections (without considering false positives). For this setting, we analyze how the distributed spatial sampling strategies (which may comprise disjointed or partially overlapping regions) of the testing agencies influence the overall detection accuracy. We derive optimal coverage strategies for each agency (and hence, for the CDC), with the objective of minimizing detection error. Notably, we demonstrate that the optimal error exponent can be expressed as a simple optimization problem, which we solve completely for the case of two testing agencies.

We study a variant of the active sequential hypothesis problem (SHT) with a decision-maker having a source probing capability, and a cognitive impairment in data processing. Here a data source outputs memoryless data samples, conditioned on the instantiated (binary) hypothesis and his current state. A potentially noisy version of the generated data is observed by a decision-maker that has cognitive limitations in processing the generated data; the cognitive impairment can, however, be managed by the decision-maker, albemt under some overall constraint. The decision-maker can also probe the data source, and induce a change in its state so as to generate a sample from a favorable source distribution from a collection known a-priori to all. However, similar to its choice of cognition level, the decision-maker has a probing-constraint (possibly due to practical limitations) that limits its long term choice of state selections. We first formalize the above problem as a constrained optimal stopping time problem in a sequential environment. We then present a systematic study of an optimal strategy for the decision maker comprising the stopping time, the pair of sequences of probing-state selection and cognition-levels, and the terminal decision rule. Using classical techniques of active SHT (involving dynamic programming), we show that the sequential probability ratio test (SPRT) is an optimal testing procedure for this problem, and then characterize the optimal stopping time. We also present an optimal choice for the probing state and cognition sequences.

Time-encoded sampling represents an emerging paradigm for temporal discretization, garnering recent interest. In this paper, we address the challenge of time-encoded sampling for the perfect recovery of signals residing in shift-invariant spaces (SISs) defined by multiple generators. Specifically, we establish a sufficient condition for achieving perfect recovery of a signal from a multigenerator SIS when it is sampled using a single Time-Encoded Machine (TEM). This condition is exclusively characterized in terms of the provided set of multiple generators. Our findings extend the prior work of Gontier and Vetterli [ACHA, ’13], which originally focused on single-generator SISs. We present illustrative results for both classic baseband signals and bandpass signals (both examples of SISs), highlighting the limitations of single-TEM-based time-encoding schemes.

We study the problem of Bayesian persuasion under receiver distrust. In the classical Bayesian persuasion problem introduced by Kamenica and Gentzkow [AER, 2011], there are two parties, a sender Alice and a receiver Bob, who engage in a one-way interaction from sender to receiver. The sender employs a signalling strategy so as to persuade or steer the receiver toward taking a certain action(s) with respect to a random state known only to her. Both parties are rational and seek to optimize their expected utilities; however, their utilities are intimately coupled as they are functions of the random state and the receiver's action. In this work, we initiate a systematic study of Bayesian persuasion when the receiver is distrustful of the sender. Extending the result of Kamenica and Gentzkow [AER, 2011], we present a necessary and sufficient criterion for the existence of a signalling scheme for persuasion under distrust. Interestingly, our results unveil the existence of a regime under a so-called ‘super-distrustful’ receiver when a rational sender should seek to ‘counter-persuade’ or employ ‘counter-suasion’ to derive maximal benefit.

In this work, we study the problem of distributed sampling and interpolation for perfect reconstruction of graph signals. In particular, we explore and present a generalization of Papoulis' classic generalized sampling expansion (GSE) to graph signals. We consider a single-time instance of a graph signal from a space of bandlimited graph signals, appropriately defined via the graph Fourier transform associated to the graph. For such bandlimited graph signals, we first identify a sufficient condition for perfect reconstruction via distributed sampler/interpolator pairs, in the spirit of the Shannon-Nyquist criterion. When this perfect reconstruction criteria is satisfied by the individual sampler rates, we then propose a distributed sampler/interpolator architecture which is shown to be achievable for the underlying bandlimited space. The results represent a unique generalization of Papoulis' generalized sampling expansion (GSE) paradigm to graph signals. Interestingly, our results show that such achievable schemes-comprising several pairs of individual sampler/interpolator pairs- are such that every component sampler can be essentially perceived as a concatenation of a pre-sampling filtering operation followed by binary vertex-sampling. The corresponding interpolator is then obtained as a linear transformation which is completely dependent on the vertex-sampling operation but is independent of the pre-sampling filter.

This paper considers the problem of hypothesis testing through the distributed sampling of a remote Poisson source. More specifically, we consider the scenario in which one of two Poisson sources is observed at a set of$K$remote observers. These source observations are subject to erasure-type noise, so some of the source spikes are not received at some of the$K$observers, leading to incomplete signal reception. The partially received signal is then transmitted to a central detector whose task is to identify the originating source. A crucial constraint in our study is the limited capacity for signal forwarding from the observers to the central detector. We assume that these remote observers are subject to a sampling constraint so that only a portion of the total signal received at all remote observers can be forwarded to the central detector. Given this sampling constraint, we determine the optimal sampling strategy at the remote observers that minimizes the probability of error in the detection of the remote source. This problem setting is motivated by the problem of testing of large populations through multiple tests, each subject to a certain false positive and false negative rates. Our paper contributes to the field through a comprehensive mathematical analysis, providing innovative strategies and insights for efficient resource allocation in large-scale testing. The proposed model not only enhances understanding of distributed Poisson sampling under constraints but also offers practical applications in robust decision-making for hypothesis testing in complex environments.

We propose the problem of wiretapped commitment, where two parties, say committer Alice and receiver Bob, engage in a commitment protocol using a noisy channel as a resource, in the presence of an eavesdropper, say Eve. Noisy versions of Alice's transmission over the wiretap channel are received by both Bob and Eve. We seek to determine the maximum commitment throughput in the presence of eavesdropper, i.e., wiretapped commitment capacity, where in addition to the standard security requirements for two-party commitment, one seeks to ensure that Eve doesn't learn about the commit string. A key interest in this work is to explore the effect of collusion (or lack of it) between the eavesdropper Eve and either Alice or Bob. Toward the same, we present results on the wiretapped commitment capacity under the so-called Y-private regime (when Alice or Bob cannot collude with Eve) and the 2-private regime (when Alice or Bob may collude with Eve).

Commitment is a key primitive which resides at the heart of several cryptographic protocols. Noisy channels can help realize information-theoretically secure commitment schemes; however, their imprecise statistical characterization can severely impair such schemes, especially their security guarantees. Keeping our focus on channel ‘unreliability’ in this work, we study commitment over unreliable continuous alphabet channels called the Gaussian unfair noisy channels or Gaussian UNCs.We present the first results on the optimal throughput or commitment capacity of Gaussian UNCs. It is known that ‘classical’ Gaussian channels have infinite commitment capacity, even under finite transmit power constraints. For ‘unreliable’ Gaussian UNCs, we prove the surprising result that their commitment capacity may be finite, and in some cases, zero. When commitment is possible, we present achievable rate lower bounds by constructing positive-throughput protocols under given input power constraint, and (two-sided) channel elasticity at committer Alice and receiver Bob. Our achievability results establish an interesting fact – Gaussian UNCs with zero elasticity have infinite commitment capacity. This result brings a completely new perspective as to why classic Gaussian channels, i.e., Gaussian UNCs with zero elasticity, have infinite capacity. Finally, we precisely characterize the positive commitment capacity threshold for a Gaussian UNC in terms of the channel elasticity, when the transmit power tends to infinity.

We study the problem of distributed sampling and detection of remote point processes. A remote source, modelled as a homogeneous Poisson counting process (PCP) is observed at multiple remote observers in noise. The observers have a sampling constraint which limits their ability to forward their observations to a centralized fusion center, or ‘detector’. More precisely, we assume that the remote observers can send any fixed fraction of their observation to the detector noiselessly; in addition, the overall time duration of the observation received, or the ON time, at the detector is limited. We refer to this constraint as a joint sampling/communication constraint, as it accounts for both of the following: (i) the finite energy available for sampling at the remote observers, and (ii) the finite capacity of the uplink toward the fusion center. Our main contribution is the complete characterization of optimal strategies for joint sampling and detection of the remote source. We first present optimal strategies when there are two samplers, and then extend the characterization for the K-sampler, K > 2, case. Our results reveal a fundamental tension in the design of distributed sampling strategies between (i) obtaining noisy observations of the remote source at multiple samplers so as to jointly ‘reject’ their individual observation noise at the detector, and (ii) observing noisy realization at exactly one appropriately chosen sampler over a longer time period to obtain a better estimate of the remote PCP source intensity. Our results also reveal the interesting fact that two simultaneously active samplers are necessary and sufficient for complete noise-rejection.

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 this paper, we study the detection of Poisson point sources when the central detector observes the remote source via a restricted number of samples from distributed sensors. More specifically, we consider the scenario in which a Poisson source is observed, in noise, at two remote observers or samplers. At each sampler, the noisy observations are sampled as part of a distributed strategy designed by the central detector by accounting for a communication constraint between the sensor and the detector. Such limited sampling/estimation/communication scenarios are fundamental to modern cyberphysical systems. In such systems, discrete events such as signals for detection, control, and feedback propagate through a common communication and sensing infrastructure. For this scenario, we study the problem of optimally selecting the distributed sampling strategy employed at all remote samplers under the constraint that samples can be acquired for a given fraction of time across both samplers. We focus on point processes in this work and derive an optimal sampling strategy for the case of a homogeneous Poisson source which may be corrupted by another independent, additive and homogeneous Poisson noise source with known intensity. We show that any optimal solution combines either or both of these two distributed sampling strategies: (i) a time-sharing strategy –samplers communicate samples corresponding to non-overlapping time intervals, and (ii) a noise rejection strategy –samplers communicate samples during an identical time interval of activity, thus allowing for identification and subsequent rejection of the spurious additive noise realizations at either sampler. We argue that these two strategies play a crucial role in more general scenarios, encompassing a more general class of sources and noise realizations.

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 study commitments over unreliable compound noisy channels, where parties may know the compound channel state but lack control over that state. Commitment is one of the common building blocks for many cryptographic protocols which realize multi-party computational functionalities in a secure manner. A noisy channel, among others, is widely acknowledged as a promising resource for realizing information-theoretically secure cryptographic primitives, including commitment. However, unreliable noisy channels with poorly or imprecisely characterized statistical behaviour can severely degrade commitment guarantees. Our focus is unreliability on account of a compound channel state, albeit under public awareness of that state.Building on prior work, we seek to characterize the optimal commitment throughput or commitment capacity of compound binary symmetric channels when parties may be state-aware. State-awareness implies a passive and publicly known capability of precise channel knowledge (whether said party is honest or dishonest); however, state-awareness precludes any active and private channel state control as in, for instance, the classic unfair noisy channels (UNCs). We present new results on the commitment capacity under all possible configurations where individual parties may (or may not) be state-aware. An important takeaway of our work is the following: even a fairly weak capability of state-awareness (albeit when asymmetric and only at the committer-side) can degrade the commitment throughput to the same extent as under strongly capable parties that can privately control the compound state.

Commitment is an important cryptographic primitive. It is well known that noisy channels are a promising resource to realize commitment in aninformation-theoreticallysecure manner. However, oftentimes, channel behaviour may be poorly characterized thereby limiting the commitment throughput and/or degrading the security guarantees; a particularly problematic situation arises when a dishonest party, unbeknown to the honest one, maliciously alters the channel characteristics. Reverse elastic channels (RECs) are an interesting class of suchunreliablechannels where only a dishonestcommitter, say Alice, can maliciously alter the channel. RECs have attracted recent interest in the study of several cryptographic primitives. Our principal contribution is the REC commitment capacity characterization; this proves a recent related conjecture. A key result is our tight converse which analyses a specific cheating strategy by Alice. Along with elastic channels (ECs), where only a dishonestreceiverBob can alter the channel, RECs are also closely related to the classic unfair noisy channels (UNCs). In stark contrast to UNCs, both RECs and ECs always exhibit positive commitment throughput for all non-trivial channel parameters. Interestingly, our results show that channels with exclusiveone-sided elasticityfor dishonest parties, exhibit a fundamentalasymmetrywhere, a committer with one-sided elasticity has a significantly more debilitating effect on the commitment throughput than a similarly capable receiver.

We study the problem of commitment over channels under cost constraints. Commitment is a widely studied cryptographic primitive, where two mutually distrustful parties, say Alice and Bob, interact over two phases of a protocol, viz., commit phase followed by reveal phase, to achieve commitment on a bit string available to Alice. Commitment (over the string) is said to occur if (i) Alice commits to the string which remains securely hidden from Bob at the end of the commit phase involving Alice's transmission to Bob, and (ii) Alice reveals a string to Bob and Bob is able to successfully detect whether the string is the committed one or not. When Alice and Bob are computationally unbounded, i.e., under the information-theoretic setting, it is well known that even a single bit commitment is impossible when the channel available to Alice and Bob is noiseless. Noisy channels, however, offer the potential of non-zero commitment rate, and thus, are a valuable resource. We study information-theoretically secure commitment over noisy discrete memoryless channels (DMCs). The largest commitment throughput over noisy channels is called the commitment capacity or simply capacity. In this work, we completely characterize via a single-letter expression, the commitment capacity of DMCs under general cost constraints; this generalizes the previously known result in the absence of such cost constraints. We show that cost constrained commitment capacity of any given DMC can significantly differ from its unconstrained value. We also present a dual capacity characterization in terms of output distributions. Interestingly, we show that every input distribution achieving the capacity results in the same output distribution; the latter is the unique optimizer of our dual capacity expression.

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.

In this work, we study commitment over a class of channels called reverse elastic channels (RECs). In the commitment problem, two mutually distrustful parties, say Alice and Bob, seek to commit on a bit string available to Alice. The parties interact via a commitment protocol comprising two phases, viz., commit phase followed by reveal phase. Alice commits to a string, and transmits it to Bob securely in a manner Bob cannot learn it until Alice chooses to reveal it; at the time of reveal, however, Bob can successfully detect if Alice cheats. It is well known that noisy channels are a promising resource to realize information-theoretically secure commitment; however, oftentimes, channel behaviour may be poorly characterized thereby limiting the commitment throughput and/or degrading the security guarantees. Particularly problematic is a scenario where dishonest parties can actively alter the channel characteristics. RECs are an interesting class of such unreliable channels, where essentially only a dishonest committer Alice can meaningfully alter the channel; RECs have attracted active recent interest. Our principal contribution is the REC commitment capacity characterization for all parameters; this proves a recent related conjecture. Apart from presenting an achievable scheme, a key result in our work is a tight converse which analyses a specific cheating strategy by Alice. The significance of RECs stems from the fact that along with elastic channels (ECs), where only a dishonest receiver Bob can alter the channel, these two channel models represent special cases of the more widely studied unfair noisy channels (UNCs). Interestingly, for a given set of parameters, our result shows that the REC commitment capacity is no larger than that for the ECs. Furthermore, similar to the ECs, RECs offer non-trivial commitment throughput for all meaningful parameters; this is in stark contrast to UNCs where the throughput may possibly be zero.

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.

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

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

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.

It is well known that timing jitter can degrade the bit error rate (BER) of receivers that recover clock information from the input data. In this paper, we show that timing jitter can also result in an indefinite increase in the settling time of clock recovery circuits, particularly in low swing mesochronous systems. Mesochronous clock retiming circuits are used to recover a clock of the correct phase from a clock of the correct frequency. Such receivers are required for repeaterless on-chip interconnects and in off-chip interconnects that use a forwarded clock. We first show how timing jitter can result in large increase in the settling time of the clock recovery circuit. Next, we model the circuit as a Markov chain with absorbing states. Here, the mean time of absorption of the Markov chain, which represents the mean settling time of the circuit, is determined. The model is validated by confirming its predictions with behavioural simulations of the circuit. Using insights provided by the model, techniques for reducing the settling time are proposed and their efficacy is confirmed with circuit level simulations.

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