We study the binary hypothesis testing problem where an adversary may potentially corrupt a fraction of the samples. The detector is, however, permitted to abstain from making a decision if (and only if) the adversary is present. We consider a few natural “contamination models” and characterize for them the trade-off between the error exponents of the four types of errors - errors of deciding in favour of the incorrect hypothesis when the adversary is present and errors of abstaining or deciding in favour of the wrong hypothesis when the adversary is absent, under the two hypotheses. All missing proofs may be found in the extended version [1].

In the classical “Bits Through Queues” paper, it was hypothesized that full feedback always increases the capacity of first-in-first-out queues, except when the service time distribution is memoryless. More recently, a non-explicit sufficient condition under which feedback increases capacity was provided, along with simple examples of service times meeting this condition. While this condition yields examples where feedback is beneficial, it does not offer explicit structural properties of such service times. In this paper, we show that full feedback increases capacity whenever the service time has bounded support. This is achieved by investigating a generalized notion of feedback, with full feedback and weak feedback as particular cases.

In their "Bits Through Queues" paper, Anantharam and Verdú showed that if the service time is memoryless feedback does not increase capacity under a FIFO policy, and further conjectured that feedback increases capacity for all other service times. Towards this conjecture, a recent paper by Aptel and Tchamkerten provided a sufficient condition on the service time under which feedback increases capacity. While this condition yields examples of service times for which feedback is helpful, it does not provide explicit structural properties of such service times.In this paper, we consider the discrete-time setting and show that feedback increases capacity for any service time with finite support. We also show that the above sufficient condition is inconclusive for service times with infinite support.

We propose a scheme for analog-to-digital (A/D) conversion of a signal that is bandlimited most of the time but contains harmonics of a high frequency occasionally. To enable the capture of the high frequency components, such signals are usually oversampled. This framework is of practical interest in the case of electrical signals wherein one encounters high frequency faults or anomalies from time to time, all of which need to be retained for diagnostic purposes. Existing schemes that rely on oversampling for dithered A/D conversion of bandlimited signals are designed for the worst case and do not take into account the fact that the high frequency anomalies occur rarely. We propose an adaptive A/D conversion scheme that identifies the presence or absence of a high frequency component in a given block of samples by formulating it as a hypothesis testing problem. The proposed scheme performs better in terms of compression compared to a scheme designed for the worst case while retaining the same guarantees on the reconstruction error.

We consider a two-party distributed hypothesis testing problem for correlated Gaussian random variables. For a d-dimensional random vector X and a scalar random variable Y, where X and Y are jointly Gaussian with an unknown correlation vector ρ, partiesP1andP2observe independent copies of X and Y, respectively. The parties seek to test if their observations are correlated or not, namely they seek to test if ||ρ||2exceeds τ or is it 0. To that end, they communicate interactively and declare the test output. We show that roughly order d/τ2bits of communication are sufficient and necessary for resolving the distributed correlation testing problem above. Furthermore, we establish a lower bound of roughly d2/τ2bits for the communication needed for distributed estimation of ρ, implying that distributed correlation testing requires less communication than distributed estimation. Both our lower bounds for testing and estimation hold for an arbitrary d and interactive communication with shared randomness, while our distributed test requires only one-way communication with shared randomness. For the one-dimensional case, with one-way communication and with probability of one of the error-types fixed, our bounds are more refined in the dependence on the other error-type and are tight even in the constant.

Two parties observing sequences of bits want to determine if their bits were generated independently or not. To that end, the first party communicates to the second. A simple communication scheme involves taking as few sample bits as determined by the sample complexity of independence testing and sending it to the second party. But is there a scheme that uses fewer bits of communication than the sample complexity, perhaps by observing more sample bits? We show that the answer to this question is in the affirmative when the joint distribution is a binary symmetric source. More generally, for any given joint distribution, we present a distributed independence test that uses linear correlation between functions of the observed random variables. Furthermore, we provide lower bounds for the general setting that use hypercontractivity and reverse hypercontractivity to obtain a measure change bound between the joint and the independent distributions. The resulting bounds are tight for both a binary symmetric source and a Gaussian symmetric source.

We propose a distributed sequential algorithm for quick detection of spectral holes in a Cognitive Radio set up. Two or more local nodes make decisions and inform the fusion centre (FC) over a reporting Multiple Access Channel (MAC), which then makes the final decision. The local nodes use energy detection and the FC uses mean detection in the presence of fading, heavy-tailed electromagnetic interference (EMI) and outliers. The statistics of the primary signal, channel gain and the EMI is not known. Different nonparametric sequential algorithms are compared to choose appropriate algorithms to be used at the local nodes and the FC. Modification of a recently developed random walk test is selected for the local nodes for energy detection as well as at the fusion centre for mean detection. We show via simulations and analysis that the nonparametric distributed algorithm developed performs well in the presence of fading, EMI and outliers. The algorithm is iterative in nature making the computation and storage requirements minimal.

We consider non parametric sequential hypothesis testing problem when the distribution under the null hypothesis is fully known but the alternate hypothesis corresponds to some other unknown distribution with some loose constraints. We propose a simple algorithm to address the problem. This is also generalized to the case when the distribution under the null hypothesis is not fully known. These problems are primarily motivated from wireless sensor networks and spectrum sensing in Cognitive Radios. A decentralized version utilizing spatial diversity is also proposed. Its performance is analysed and asymptotic properties are proved. The simulated and analysed performance of the algorithm are shown to be better than an earlier algorithm addressing the same problem with similar assumptions. We also modify the algorithm for optimizing performance when information about the prior probabilities of occurrence of the two hypotheses are known.