In probabilistic nonadaptive group testing (PGT), we aim to characterize the number of pooled tests necessary to identify a random k-sparse vector of defectives with high probability. Recent work has shown that$n$tests are necessary when$k$=$w$($n$/ log n). It is also known that O (k log n) tests are necessary and sufficient in other regimes. This leaves open the important sparsity regime where the probability of a defective item is~ 1/ log$n$(or$k$= 8 ($n$/ log n)) where the number of tests required is linear in n. In this work we aim to exactly characterize the number of tests in this sparsity regime. In particular, we seek to determine the number of defectives λ ($a$)$n$/ log$n$that can be identified if the number of tests is an. In the process, we give upper and lower bounds on the exact point at which individual testing becomes suboptimal, and the use of a carefully constructed pooled test design is beneficial.

One-bit compressed sensing (1bCS) is a method of signal acquisition under extreme measurement quantization that gives important insights on the limits of signal compression and analog-to-digital conversion. The setting is also equivalent to the problem of learning a sparse hyperplane-classifier. In this paper, we propose a generic approach for signal recovery in nonadaptive 1bCS that leads to improved sample complexity for approximate recovery for a variety of signal models, including nonnegative signals and binary signals. We construct 1bCS matrices that are universal - i.e. work for all signals under a model - and at the same time recover very general random sparse signals with high probability. In our approach, we divide the set of samples (measurements) into two parts, and use the first part to recover the superset of the support of a sparse vector. The second set of measurements is then used to approximate the signal within the superset. While support recovery in 1bCS is well-studied, recovery of superset of the support requires fewer samples, which then leads to an overall reduction in sample complexity for approximate recovery.

Index coding, a source coding problem over broadcast channels, has been a subject of both theoretical and practical interests since its introduction (by Birk and Kol, 1998). In short, the problem can be defined as follows: there is an input P (p1,⋯,pn), a set of n clients who each desire a single entry pi of the input, and a broadcaster whose goal is to send as few messages as possible to all clients so that each one can recover its desired entry. Additionally, each client has some predetermined “side information,” corresponding to the certain entries of the input P, which we represent as the “side information graph” G. The graph G has a vertex vifor client i and a directed edge (vi, vj), indicating that client i knows the jth entry of the input. Given a fixed side information graph G, we are interested in determining or approximating the “broadcast rate” of index coding on the graph, i.e., the least number of messages the broadcaster can transmit so that every client recovers its desired information. The complexity of determining this broadcast rate in the most general case is open, and the best-known approximations are barely better than the trivial O(n)-approximation corresponding to sending each client their information directly without performing any coding. Using index coding schemes based on linear programs (LPs), we take a two-pronged approach to approximating the broadcast rate. First, extending earlier work on planar graphs, we focus on approximating the broadcast rate for special graph families, such as graphs with the small chromatic number and disk graphs. In certain cases, we are able to show that simple LP-based schemes give constant-factor approximations of the broadcast rate, which seem extremely difficult to obtain in the general case. Second, we provide several LP-based schemes for the general case, which are not constant-factor approximations, but which strictly improve on the best-known schemes. These can be viewed as both a strengthening of the constant-factor approximations proven for special graph families (as these schemes strictly improve on those which we prove are good approximations), as well as another tool that can be used either in practice or in future theoretical analyses.

We consider several related problems of estimating the `sparsity' or number of nonzero elements d in a length n vector x by observing only b = M ⊙ x, where M is a predesigned test matrix independent of x, and the operation ⊙ varies between problems. We aim to provide a Δ-approximation of sparsity for some constant Δ with a minimal number of measurements (rows of M). This framework generalizes multiple problems, such as estimation of sparsity in group testing and compressed sensing. We use techniques from coding theory as well as probabilistic methods to show that O(D log D log n) rows are sufficient when the operation ⊙ is logical OR (i.e., group testing), and nearly this many are necessary, where D is a known upper bound on d. When instead the operation ⊙ is multiplication over R or a finite field, we show that respectively Θ(D) and Θ(D log n/D) measurements are necessary and sufficient.