133 citations · 803 across the 68 of their papers we have counts for
48 papers · 1 filter
Diagnosing the Refuted Mismatched Decoding Converse for Binary-Input Channels
Jonathan Scarlett
We revisit the claimed converse theorem for mismatched decoding over binary-input discrete memoryless channels (Balakirsky, 1995) and the subsequent work refuting this converse via…
Maxflow-Based Bounds for Low-Rate Information Propagation over Noisy Networks
Yan Hao Ling, Jonathan Scarlett
We study error exponents for the problem of low-rate communication over a directed graph, where each edge in the graph represents a noisy communication channel, and there is a sing…
Multi-Bit Relaying over a Tandem of Channels
Yan Hao Ling, Jonathan Scarlett
We study error exponents for the problem of relaying a message over a tandem of two channels sharing the same transition law, in particular moving beyond the 1-bit setting studied…
Model-Based and Graph-Based Priors for Group Testing
Ivan Lau, Jonathan Scarlett, Yang Sun
The goal of the group testing problem is to identify a set of defective items within a larger set of items, using suitably-designed tests whose outcomes indicate whether any defect…
Mismatched Rate-Distortion Theory: Ensembles, Bounds, and General Alphabets
Millen Kanabar, Jonathan Scarlett
In this paper, we consider the mismatched rate-distortion problem, in which the encoding is done using a codebook, and the encoder chooses the minimum-distortion codeword according…
Universal 1-Bit Compressive Sensing for Bounded Dynamic Range Signals
Sidhant Bansal, Arnab Bhattacharyya, Anamay Chaturvedi +1
A {\em universal 1-bit compressive sensing (CS)} scheme consists of a measurement matrix such that all signals belonging to a particular class can be approximately recovere…
Performance Bounds for Group Testing With Doubly-Regular Designs
Nelvin Tan, Way Tan, Jonathan Scarlett
In the group testing problem, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether any defective item is…
Simple Coding Techniques for Many-Hop Relaying
Yan Hao Ling, Jonathan Scarlett
In this paper, we study the problem of relaying a single bit of information across a series of binary symmetric channels, and the associated trade-off between the number of hops $m…
Noisy Adaptive Group Testing via Noisy Binary Search
Bernard Teo, Jonathan Scarlett
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 has numerous practical ap…
Fast Splitting Algorithms for Sparsity-Constrained and Noisy Group Testing
Eric Price, Jonathan Scarlett, Nelvin Tan
In group testing, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether at least one defective item is pre…
Optimal Rates of Teaching and Learning Under Uncertainty
Yan Hao Ling, Jonathan Scarlett
In this paper, we consider a recently-proposed model of teaching and learning under uncertainty, in which a teacher receives independent observations of a single bit corrupted by b…
A Fast Binary Splitting Approach to Non-Adaptive Group Testing
Eric Price, Jonathan Scarlett
In this paper, we consider the problem of noiseless non-adaptive group testing under the for-each recovery guarantee, also known as probabilistic group testing. In the case of …
Optimal Non-Adaptive Probabilistic Group Testing in General Sparsity Regimes
Wei Heng Bay, Eric Price, Jonathan Scarlett
In this paper, we consider the problem of noiseless non-adaptive probabilistic group testing, in which the goal is high-probability recovery of the defective set. We show that in t…
Improved Bounds and Algorithms for Sparsity-Constrained Group Testing
Nelvin Tan, Jonathan Scarlett
In group testing, the goal is to identify a subset of defective items within a larger set of items based on tests whose outcomes indicate whether any defective item is present. Thi…
Information-Theoretic Foundations of Mismatched Decoding
Jonathan Scarlett, Albert Guillén i Fàbregas, Anelia Somekh-Baruch +1
Shannon's channel coding theorem characterizes the maximal rate of information that can be reliably transmitted over a communication channel when optimal encoding and decoding stra…
On the All-Or-Nothing Behavior of Bernoulli Group Testing
Lan V. Truong, Matthew Aldridge, Jonathan Scarlett
In this paper, we study the problem of non-adaptive group testing, in which one seeks to identify which items are defective given a set of suitably-designed tests whose outcomes in…
Information-Theoretic Lower Bounds for Compressive Sensing with Generative Models
Zhaoqiang Liu, Jonathan Scarlett
It has recently been shown that for compressive sensing, significantly fewer measurements may be required if the sparsity assumption is replaced by the assumption the unknown vecto…
Learning Erdős-Rényi Random Graphs via Edge Detecting Queries
Zihan Li, Matthias Fresacher, Jonathan Scarlett
In this paper, we consider the problem of learning an unknown graph via queries on groups of nodes, with the result indicating whether or not at least one edge is present among tho…
Sublinear-Time Non-Adaptive Group Testing with Tests via Bit-Mixing Coding
Steffen Bondorf, Binbin Chen, Jonathan Scarlett +2
The group testing problem consists of determining a small set of defective items from a larger set of items based on tests on groups of items, and is relevant in applications such…
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…
Support Recovery in the Phase Retrieval Model: Information-Theoretic Fundamental Limits
Lan V. Truong, Jonathan Scarlett
The support recovery problem consists of determining a sparse subset of variables that is relevant in generating a set of observations. In this paper, we study the support recovery…
An Introductory Guide to Fano's Inequality with Applications in Statistical Estimation
Jonathan Scarlett, Volkan Cevher
Information theory plays an indispensable role in the development of algorithm-independent impossibility results, both for communication problems and for seemingly distinct areas s…
Noisy Non-Adaptive Group Testing: A (Near-)Definite Defectives Approach
Jonathan Scarlett, Oliver Johnson
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 applicatio…
Cross-Sender Bit-Mixing Coding
Steffen Bondorf, Binbin Chen, Jonathan Scarlett +2
Scheduling to avoid packet collisions is a long-standing challenge in networking, and has become even trickier in wireless networks with multiple senders and multiple receivers. In…