We study certain combinatorial aspects of listdecoding, motivated by the exponential gap between the known upper bound (of O(1/γ)) and lower bound (of Ωp(log(1/γ))) for the list size needed to list decode up to error fraction p with rate γ away from capacity, i.e., 1 - h(p) - γ [here p E (0, 1/2) and γ > 0]. Our main result is that we prove that in any binary code C ⊆ (0, 1)nof rate 1 - h(p) - γ, there must exist a set l ⊂ C of p(1/√γ) codewords such that the average distance of the points in L from their centroid is at most pn. In other words, there must exist Ωp(1/√γ) codewords with low average radius. The standard notion of list decoding corresponds to working with the maximum distance of a collection of codewords from a center instead of average distance. The average radius form is in itself quite natural; for instance, the classical Johnson bound in fact implies average-radius list-decodability. The remaining results concern the standard notion of list-decoding, and help clarify the current state of affairs regarding combinatorial bounds for list-decoding as follows. First, we give a short simple proof, over all fixed alphabets, of the above-mentioned Ωp(log(1/γ)) lower bound. Earlier, this bound followed from a complicated, more general result of Blinovsky. Second, we show that one cannot improve the Ωp(log(1/γ)) lower bound via techniques based on identifying the zero-rate regime for list-decoding of constantweight codes [this is a typical approach for negative results in coding theory, including the Ωp(log(1/γ)) list-size lower bound]. On a positive note, our Ωp(1/√γ) lower bound for average radius list-decoding circumvents this barrier. Third, we exhibit a reverse connection between the existence of constant-weight and general codes for list-decoding, showing that the best possible list-size, as a function of the gap γ of the rate to the capacity limit, is the same up to constant factors for both constant-weight codes (with weight bounded away from p) and general codes. Fourth, we give simple second moment-based proofs that w.h.p. a list-size of Ωp(1/γ) is needed for list-decoding random codes from errors as well as erasures. For random linear codes, the corresponding list-size bounds are Ωp(1/γ) for errors and expΩp(log(1/γ)) for erasures.

We investigate the problem of estimating the cluster tree for a density $f$ supported on or near a smooth $d$-dimensional manifold $M$ isometrically embedded in $\mathbb{R}^D$. We study a $k$-nearest neighbor based algorithm recently proposed by Chaudhuri and Dasgupta. Under mild assumptions on $f$ and $M$, we obtain rates of convergence that depend on $d$ only but not on the ambient dimension $D$. We also provide a sample complexity lower bound for a natural class of clustering algorithms that use $D$-dimensional neighborhoods.

We present a construction of subspace codes along with an efficient algorithm for list decoding from both insertions and deletions, handling an information-theoretically maximum fraction of these with polynomially small rate. Our construction is based on a variant of the folded Reed-Solomon codes in the world of linearized polynomials, and the algorithm is inspired by the recent linear-algebraic approach to list decoding [4]. Ours is the first list decoding algorithm for subspace codes that can handle deletions; even one deletion can totally distort the structure of the basis of a subspace and is thus challenging to handle. When there are only insertions, we also present results for list decoding subspace codes that are the linearized analog of Reed-Solomon codes (proposed in [15, 8], and closely related to the Gabidulin codes for rank-metric coding), obtaining some improvements over similar results in [10].

Program Obfuscation that renders any given program essentially equivalent to a black box, while desirable, is impossible [4] in the general polynomial time adversary models. It is natural to search for positive results under restricted programs (e.g., point functions [20, 2] POBDDs [10], cryptographic primitives [17, 12, 13]. Here we study straight line arithmetic programs.