We propose a discrete transport equation on graphs which connects distributions on both vertices and edges. We then derive a discrete analogue of the Benamou-Brenier formulation for Wasserstein-$1$ distance on a graph and as a result classify all $W_1$ geodesics on graphs.

We consider a version of the classical group testing problem motivated by PCR testing for COVID-19. In the so-called tropical group testing model, the outcome of a test is the lowest cycle threshold (Ct) level of the individuals pooled within it, rather than a simple binary indicator variable. We introduce the tropical counterparts of three classical non-adaptive algorithms (COMP, DD and SCOMP), and analyse their behaviour through both simulations and bounds on error probabilities. By comparing the results of the tropical and classical algorithms, we gain insight into the extra information provided by learning the outcomes (Ct levels) of the tests. We show that in a limiting regime the tropical COMP algorithm requires as many tests as its classical counterpart, but that for sufficiently dense problems tropical DD can recover more information with fewer tests, and can be viewed as essentially optimal in certain regimes.

In response to the rise of crime in short-range communication systems, a novel method for authenticating co-located devices is presented. Our method, Channel Randomness Yields Secure Proximity (ChRYSP) exploits the fundamental properties of the wireless RF channel to protect against relay attacks and replay attacks - the two most common impersonation attacks in short-range communication systems. ChRYSP is based on the fact that two devices in close proximity - typically a couple of wavelengths - experience correlated fading on a received RF signal. ChRYSP is facilitated by the employment of a helper node and can be implemented by low-cost, narrowband transceivers. Numerical results demonstrate high accuracy in detecting both relay attacks and replay attacks.

Mass reinsuring of blockchain-based parametric insurance contracts has so far been unsuccessful due to a lack of protocols promoting securitisation. We introduce a proof of concept reinsurance smart contract system, based on traditional catastrophe bonds, to hedge and securitise bushfire risk on the Australian continent. The system combines the benefits of approximating human-assessed loss through a risk index with the draw of traditional indemnity insurance’s ability to hedge very specific risks. At this stage the platform faces significant challenges due to the immaturity of relevant oracles.

Channel-State-Information (CSI)-based Key Generation (KG) is an attractive technique for generating symmetric cryptographic keys due to low memory and processing power requirements. CSI-based KG protocols also promise high key rates for vehicular communication channels due to the rich entropy inherited in such dynamic channels. However, as a relatively new field, physical layer security is often limited to idealistic scenarios. The assumption that the channels decorrelate at a half-wavelength distance brings secrecy vulnerabilities that are quantified and brought to attention. This paper convinces that, even in rich scattering environments, the distance of half-wavelength is not perfectly secure, and it may be disastrous under non-idealistic antenna gain patterns. Aiming to bring CSI-based KG a step closer to practical implementation, this paper drops one of the most common idealistic assumptions in the field of PLS and redefines secure distance.

The group testing problem is concerned with identifying a small set of infected individuals in a large population. At our disposal is a testing procedure that allows us to test several individuals together. In an idealized setting, a test is positive if and only if at least one infected individual is included and negative otherwise. Significant progress was made in recent years towards understanding the information-theoretic and algorithmic properties in this noiseless setting. In this paper, we consider a noisy variant of group testing where test results are flipped with certain probability, including the realistic scenario where sensitivity and specificity can take arbitrary values. Using a test design where each individual is assigned to a fixed number of tests, we derive explicit algorithmic bounds for two commonly considered inference algorithms and thereby naturally extend the results of Scarlett & Cevher (2016) and Scarlett & Johnson (2020). We provide improved performance guarantees for the efficient algorithms in these noisy group testing models – indeed, for a large set of parameter choices the bounds provided in the paper are the strongest currently proved.

We present a novel scheme for testing the proximity of an Ultra-high frequency (UHF) Radio Frequency Identification (RFID) transponder, based on the fact that two co-located devices experience correlated channel fluctuations on a reference signal. When the interrogator requests data from the transponder, the latter performs backscattering modulation on the carrier-wave provided by a helper node. The interrogator applies signal processing techniques on the backscattered signal to extract the channel characteristics of the channel between itself and the helper, and the channel between the transponder and the helper. If the two channels are correlated, then the proximity of the transponder is validated by the fundamental properties of spatial channel correlation. The proposed scheme can be employed seamlessly in RFID systems from the transponder's point of view and is resilient to distance-fraud attack.

We consider the behaviour of the Fisher information of scaled sums of independent and identically distributed random variables in the Central Limit Theorem regime. We show how this behaviour can be related to the second-largest non-trivial eigenvalue of the operator associated with the Hirschfeld-Gebelein-Rényi maximal correlation. We prove that assuming this eigenvalue satisfies a strict inequality, an O(1/n) rate of convergence and a strengthened form of monotonicity hold.

The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of possibly-noisy tests, and is relevant in applications such as medical testing, communication protocols, pattern matching, and more. We study the noisy version of this problem, where the outcome of each standard noiseless group test is subject to independent noise, corresponding to passing the noiseless result through a binary channel. We introduce a class of algorithms that we refer to as Near-Definite Defectives (NDD), and study bounds on the required number of tests for asymptotically vanishing error probability under Bernoulli random test designs. In addition, we study algorithm-independent converse results, giving lower bounds on the required number of tests under Bernoulli test designs. Under reverse Z-channel noise, the achievable rates and converse results match in a broad range of sparsity regimes, and under Z-channel noise, the two match in a narrower range of dense/low-noise regimes. We observe that although these two channels have the same Shannon capacity when viewed as a communication channel, they can behave quite differently when it comes to group testing. Finally, we extend our analysis of these noise models to a general binary noise model (including symmetric noise), and show improvements over known existing bounds in broad scaling regimes.

We present a range of novel attacks which exploit information about the volume of answers to range queries in encrypted database. Our attacks rely on a strategy which is simple yet robust and effective. We illustrate the robustness of our strategy in a number of ways. We show how i) to adapt the attack for several variations of a basic usage scenario ii) to defeat countermeasures intended to thwart the premise of our basic attack and iii) to perform partial reconstruction of secret data when unique reconstruction is information theoretically impossible. Furthermore, over the state of the art, our attacks require one order of magnitude fewer queries. We show how to improve the attacks even further, under the assumption that some partial information is known to the adversary. We validate experimentally all of our attacks through extensive experiments on real-world medical data and justify theoretically the effectiveness of our strategy for the basic attack scenario. Our new attacks further underscore the difficulty of striking an appropriate functionality-security trade-off for encrypted databases.

Security has traditionally been dealt with at layers higher than the physical layer but in the wake of 5G, security at all layers is necessary to deal with the variations in complexity of connected devices. Low power devices may use physical layer security as a solution, while other devices may use physical layer security to complement security at higher layers. One key metric for physical layer security is the secrecy capacity. This is the maximum rate that a system can transmit with perfect secrecy. Multiple Input Multiple Output (MIMO) and Massive MIMO systems look likely to play a part in 5G, but the secrecy capacity for such systems is not fully understood. For a Gaussian MIMO channel, the secrecy capacity is a non-convex optimisation problem for which a general solution is not available. This paper presents an optimisation scheme that enables us to determine the secrecy capacity of a MIMO system with a single eavesdrop antenna. It is shown that, for certain parameters, the presented scheme is a concave problem which can therefore be solved efficiently using existing convex optimisation software.

We consider the nonadaptive group testing with N items, of which K = Θ(Nθ) are defective. We study a test design in which each item appears in nearly the same number of tests. For each item, we independently pick L tests uniformly at random with replacement and place the item in those tests. We analyze the performance of these designs with simple and practical decoding algorithms in a range of sparsity regimes and show that the performance is consistently improved in comparison with standard Bernoulli designs. We show that our new design requires roughly 23% fewer tests than a Bernoulli design when paired with the simple decoding algorithms known as combinatorial orthogonal matching pursuit and definite defectives (DD). This gives the best known nonadaptive group testing performance for θ > 0.43 and the best proven performance with a practical decoding algorithm for all θ ∈ (0, 1). We also give a converse result showing that the DD algorithm is optimal with respect to our randomized design when θ > 1/2. We complement our theoretical results with simulations that show a notable improvement over Bernoulli designs in both sparse and dense regimes.

We discuss properties of the “beamsplitter addition” operation, which provides a non-standard scaled convolution of random variables supported on the non-negative integers. We give a simple expression for the action of beamsplitter addition using generating functions. We use this to give a self-contained and purely classical proof of a heat equation and de Bruijn identity, satisfied when one of the variables is geometric.

We prove new strong converse results in a variety of group testing settings, generalizing a result of Baldassini et al.. First, in the non-adaptive case, we mimic the hypothesis testing argument introduced in the finite blocklength channel coding regime by Polyanskiy et al., and using joint source-channel coding arguments of Kostina and Verdú. In the adaptive case, we combine this approach with a novel model formulation based on causal probability and directed information theory. In both cases, we prove results, which are valid for finite sized problems, and imply capacity results in the asymptotic regime. These results are illustrated graphically for a range of models.

We consider nonadaptive group testing where each item is placed in a constant number of tests. The tests are chosen uniformly at random with replacement, so the testing matrix has (almost) constant column weights. We show that performance is improved compared to Bernoulli designs, where each item is placed in each test independently with a fixed probability. In particular, we show that the rate of the practical COMP detection algorithm is increased by 31% in all sparsity regimes. In dense cases, this beats the best possible algorithm with Bernoulli tests, and in sparse cases is the best proven performance of any practical algorithm. We also give an algorithm-independent upper bound for the constant column weight case; for dense cases this is again a 31% increase over the analogous Bernoulli result.

Heterogeneous networks have a key role in the design of future mobile communication networks, since the employment of small cells around a macrocell enhances the network's efficiency and decreases complexity and power demand. Moreover, research on Blind Interference Alignment (BIA) has shown that optimal Degrees of Freedom (DoF) can be achieved in certain network architectures, with no requirement of Channel State Information (CSI) at the transmitters. Our contribution is a generalised model of BIA in a heterogeneous network with one macrocell with K users and K femtocells each with one user, by using Kronecker (Tensor) Product representation. We introduce a solution on how to vary beamforming vectors under power constraints to maximize the sum rate of the network and how optimal DoF can be achieved over K+1 time slots.

We consider the problem of nonadaptive noiseless group testing of N items of which K are defective. We describe four detection algorithms, the COMP algorithm of Chan et al., two new algorithms, DD and SCOMP, which require stronger evidence to declare an item defective, and an essentially optimal but computationally difficult algorithm called SSS. We consider an important class of designs for the group testing problem, namely those in which the test structure is given via a Bernoulli random process. In this class of Bernoulli designs, by considering the asymptotic rate of these algorithms, we show that DD outperforms COMP, that DD is essentially optimal in regimes where K ≥ √N, and that no algorithm can perform as well as the best nonrandom adaptive algorithms when K > N0.35. In simulations, we see that DD and SCOMP far outperform COMP, with SCOMP very close to the optimal SSS, especially in cases with larger K.

We define capacity for group testing problems and deduce bounds for the capacity of a variety of noisy models, based on the capacity of equivalent noisy communication channels. For noiseless adaptive group testing we prove an information-theoretic lower bound which tightens a bound of Chan et al. This can be combined with a performance analysis of a version of Hwang's adaptive group testing algorithm, in order to deduce the capacity of noiseless and erasure group testing models.

Ergodic interference alignment, as introduced by Nazer et al (NGJV), is a technique that allows high-rate communication in n-user interference networks with fast fading. It works by splitting communication across a pair of fading matrices. However, it comes with the overhead of a long time delay until matchable matrices occur: the delay is qn2for field size q. In this paper, we outline two new families of schemes, called JAP and JAP-B, that reduce the expected delay, sometimes at the cost of a reduction in rate from the NGJV scheme. In particular, we give examples of good schemes for networks with few users, and show that in large n-user networks, the delay scales like qT, where T is quadratic in n for a constant per-user rate and T is constant for a constant sum-rate. We also show that half the single-user rate can be achieved while reducing NGJV's delay from qn2to q(n-1)(n-2).

We consider a dense K user Gaussian interference network formed by paired transmitters and receivers placed independently at random in a fixed spatial region. Under natural conditions on the node position distributions and signal attenuation, we prove convergence in probability of the average per-user capacity CΣ/K to 1/2E log(1 + 2SNR). The achievability result follows directly from results based on an interference alignment scheme presented in recent work of Nazer et al. Our main contribution comes through an upper bound, motivated by ideas of "bottleneck capacity" developed in recent work of Jafar. By controlling the physical location of transmitter-receiver pairs, we can match a large proportion of these pairs to form so-called ε-bottleneck links, with consequent control of the sum capacity.

We consider a dense n-user Gaussian interference network formed by paired transmitters and receivers placed independently at random in Euclidean space. Under natural conditions on the node position distributions and signal attenuation, we prove convergence in probability of the average per-user capacity CΣ/n to ½ E log(1 + 2SNR). The achievability result follows directly from results based on an interference alignment scheme presented in recent work of Nazer et al. Our main contribution comes through the converse result, motivated by ideas of `bottleneck links' developed in recent work of Jafar. An information theoretic argument gives a capacity bound on such bottleneck links, and probabilistic counting arguments show there are sufficiently many such links to tightly bound the sum-capacity of the whole network.

Rényi'sthinningoperation on a discrete random variable is a natural discrete analog of the scaling operation for continuous random variables. The properties of thinning are investigated in an information-theoretic context, especially in connection with information-theoretic inequalities related to Poisson approximation results. The classical Binomial-to-Poisson convergence (sometimes referred to as the “law of small numbers”) is seen to be a special case of a thinning limit theorem for convolutions of discrete distributions. A rate of convergence is provided for this limit, and nonasymptotic bounds are also established. This development parallels, in part, the development of Gaussian inequalities leading to the information-theoretic version of the central limit theorem. In particular, a “thinning Markov chain” is introduced, and it is shown to play a role analogous to that of the Ornstein-Uhlenbeck process in connection to the entropy power inequality.

We consider the entropy of sums of independent discrete random variables, in analogy with Shannon's Entropy Power Inequality, where equality holds for normals. In our case, infinite divisibility suggests that equality should hold for Poisson variables. We show that some natural analogues of the EPI do not in fact hold, but propose an alternative formulation which does always hold. The key to many proofs of Shannon's EPI is the behavior of entropy on scaling of continuous random variables. We believe that Rényi's operation of thinning discrete random variables plays a similar role to scaling, and give a sharp bound on how the entropy of ultra log-concave random variables behaves on thinning. In the spirit of the monotonicity results established by Artstein, Ball, Barthe, and Naor, we prove a stronger version of concavity of entropy, which implies a strengthened form of our discrete EPI.

The Poisson distribution is known to have maximal entropy among all distributions (on the nonnegative integers) within a natural class. Interestingly, straightforward attempts to generalize this result to general compound Poisson distributions fail because the analogous result is not true in general. However, we show that the compound Poisson does indeed have a natural maximum entropy characterization when the distributions under consideration are log-concave. This complements the recent development by the same authors of an information-theoretic foundation for compound Poisson approximation inequalities and limit theorems.

Building on the recent work of Johnson (2007) and Yu (2008), we prove that entropy is a concave function with respect to the thinning operation Talpha. That is, if X and Y are independent random variables on Z+with ultra-log-concave probability mass functions, then H(TalphaX + T1-alphaY) ges alphaH(X) + (1 - alpha)H(Y), 0 les alpha les 1, where H denotes the discrete entropy. This is a discrete analogue of the inequality (h denotes the differential entropy) h(radicalphaX + radic1 - alphaY ) ges alphah(X) + (1 - alpha)h(Y), 0 les alpha les 1, which holds for continuous X and Y with finite variances and is equivalent to Shannon's entropy power inequality. As a consequence we establish a special case of a conjecture of Shepp and Olkin (1981). Possible extensions are also discussed.

The law of thin numbers is a Poisson approximation theorem related to the thinning operation. We use information projections to derive lower bounds on the information divergence from a thinned distribution to a Poisson distribution. Conditions for the existence of projections are given. If an information projection exists it must be an element of the associated exponential family. Exponential families are used to derive lower bounds on information divergence and lower bounds on the rate of convergence in the law of thin numbers. A method of translating results related to Poisson distributions into results related to Gaussian distributions is developed and used to prove a new non-trivial result related to the central limit theorem.

The "thinning" operation on a discrete random variable is the natural discrete analog of scaling a continuous variable, i.e., multiplying it by a constant. We examine the role and properties of thinning in the context of information-theoretic inequalities for Poisson approximation. The classical Binomial-to-Poisson convergence, often referred to as the "law of small numbers," is seen to be a special case of a thinning limit theorem for convolutions of discrete distributions. A rate of convergence is also provided for this limit. A Nash equilibrium is established for a channel game, where Poisson noise and a Poisson input are optimal strategies. Our development partly parallels the development of Gaussian inequalities leading to the information- theoretic version of the central limit theorem.

Fisher information plays a fundamental role in the analysis of Gaussian noise channels and in the study of Gaussian approximations in probability and statistics. For discrete random variables, the scaled Fisher information plays an analogous role in the context of Poisson approximation. Our first results show that it also admits a minimum mean squared error characterization with respect to the Poisson channel, and that it satisfies a monotonicity property that parallels the monotonicity recently established for the central limit theorem in terms of Fisher information. We next turn to the more general case of compound Poisson distributions on the nonnegative integers, and we introduce two new "local information quantities" to play the role of Fisher information in this context. We show that they satisfy subadditivity properties similar to those of classical Fisher information, we derive a minimum mean squared error characterization, and we explore their utility for obtaining compound Poisson approximation bounds.

Two new information-theoretic methods are introduced for establishing Poisson approximation inequalities. First, using only elementary information-theoretic techniques it is shown that, when S/sub n/=/spl Sigma//sub i=1//sup n/X/sub i/ is the sum of the (possibly dependent) binary random variables X/sub 1/,X/sub 2/,...,X/sub n/, with E(X/sub i/)=p/sub i/ and E(S/sub n/)=/spl lambda/, then D(P(S/sub n/)/spl par/Po(/spl lambda/)) /spl les//spl Sigma//sub i=1//sup n/p/sub i//sup 2/+[/spl Sigma//sub i=1//sup n/H(X/sub i/)-H(X/sub 1/,X/sub 2/,...,X/sub n/)] where D(P(S/sub n/)/spl par/Po(/spl lambda/)) is the relative entropy between the distribution of S/sub n/ and the Poisson (/spl lambda/) distribution. The first term in this bound measures the individual smallness of the X/sub i/ and the second term measures their dependence. A general method is outlined for obtaining corresponding bounds when approximating the distribution of a sum of general discrete random variables by an infinitely divisible distribution. Second, in the particular case when the X/sub i/ are independent, the following sharper bound is established: D(P(S/sub n/)/spl par/Po(/spl lambda/))/spl les/1//spl lambda/ /spl Sigma//sub i=1//sup n/ ((p/sub i//sup 3/)/(1-p/sub i/)) and it is also generalized to the case when the X/sub i/ are general integer-valued random variables. Its proof is based on the derivation of a subadditivity property for a new discrete version of the Fisher information, and uses a recent logarithmic Sobolev inequality for the Poisson distribution.

We provide a condition under which a version of Shannon's entropy power inequality will hold for dependent variables. We first provide a Fisher information inequality extending that found in the independent case. The key ingredients are a conditional expectation representation for the score function of a sum, and the de Bruijn identity which relates entropy and Fisher information.