156 citations · 624 across the 20 of their papers we have counts for
20 papers
Projected Variational Quantum Extragradient for Zero-Sum Games
Duong The Do, Matthew Aldridge, Duong Tung Nguyen
We propose a projected variational quantum extragradient (VQEG) framework for computing approximate Nash equilibria in two-player zero-sum matrix games. Mixed strategies are parame…
Small error algorithms for tropical group testing
Vivekanand Paligadu, Oliver Johnson, Matthew Aldridge
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 lowe…
Pooled testing to isolate infected individuals
Matthew Aldridge
The usual problem for group testing is this: For a given number of individuals and a given prevalence, how many tests T* are required to find every infected individual? In real lif…
Pooled testing and its applications in the COVID-19 pandemic
Matthew Aldridge, David Ellis
When testing for a disease such as COVID-19, the standard method is individual testing: we take a sample from each individual and test these samples separately. An alternative is p…
Conservative two-stage group testing in the linear regime
Matthew Aldridge
Inspired by applications in testing for Covid-19, we consider a variant of two-stage group testing called "conservative" (or "trivial") two-stage testing, where every item declared…
Group Testing: An Information Theory Perspective
Matthew Aldridge, Oliver Johnson, Jonathan Scarlett
The group testing problem concerns discovering a small number of defective items within a large population by performing tests on pools of items. A test is positive if the pool con…
Rates of adaptive group testing in the linear regime
Matthew Aldridge
We consider adaptive group testing in the linear regime, where the number of defective items scales linearly with the number of items. We analyse an algorithm based on generalized…
Individual testing is optimal for nonadaptive group testing in the linear regime
Matthew Aldridge
We consider nonadaptive probabilistic group testing in the linear regime, where each of n items is defective independently with probability p in (0,1), and p is a constant independ…
On the optimality of some group testing algorithms
Matthew Aldridge
We consider Bernoulli nonadaptive group testing with defectives, for . The practical definite defectives (DD) detection algorithm is known to be optimal fo…
Performance of group testing algorithms with near-constant tests-per-item
Oliver Johnson, Matthew Aldridge, Jonathan Scarlett
We consider the nonadaptive group testing with N items, of which are defective. We study a test design in which each item appears in nearly the same number of tests. F…
Improved group testing rates with constant column weight designs
Matthew Aldridge, Oliver Johnson, Jonathan Scarlett
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…
The capacity of Bernoulli nonadaptive group testing
Matthew Aldridge
We consider nonadaptive group testing with Bernoulli tests, where each item is placed in each test independently with some fixed probability. We give a tight threshold on the maxim…
Almost Separable Matrices
Matthew Aldridge, Leonardo Baldassini, Karen Gunderson
An matrix with column supports is -separable if the disjunctions are all distinct over all sets $\mathcal{K…
Group testing algorithms: bounds and simulations
Matthew Aldridge, Leonardo Baldassini, Oliver Johnson
We consider the problem of non-adaptive noiseless group testing of items of which are defective. We describe four detection algorithms: the COMP algorithm of Chan et al.; t…
The Capacity of Adaptive Group Testing
Leonardo Baldassini, Oliver Johnson, Matthew Aldridge
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…
Adaptive group testing as channel coding with feedback
Matthew Aldridge
Group testing is the combinatorial problem of identifying the defective items in a population by grouping items into test pools. Recently, nonadaptive group testing - where all the…
Interference Mitigation in Large Random Wireless Networks
Matthew Aldridge
A central problem in the operation of large wireless networks is how to deal with interference -- the unwanted signals being sent by transmitters that a receiver is not interested…
Delay-rate tradeoff in ergodic interference alignment
Oliver Johnson, Matthew Aldridge, Robert Piechocki
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 b…
Asymptotic Sum-Capacity of Random Gaussian Interference Networks Using Interference Alignment
Matthew Aldridge, Oliver Johnson, Robert Piechocki
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…
Interference alignment-based sum capacity bounds for random dense Gaussian interference networks
Oliver Johnson, Matthew Aldridge, Robert Piechocki
We consider a dense user Gaussian interference network formed by paired transmitters and receivers placed independently at random in a fixed spatial region. Under natural condi…