We study the problem of low-bandwidth non-linear computation on Reed-Solomon encoded data. Given an [n,k] Reed-Solomon encoding of a message vector 𝐟 ∈ 𝔽_q^k, and a polynomial g ∈ 𝔽_q[X₁, X₂, …, X_k], a user wishing to evaluate g(𝐟) is given local query access to each codeword symbol. The query response is allowed to be the output of an arbitrary function evaluated locally on the codeword symbol, and the user’s aim is to minimize the total information downloaded in order to compute g(𝐟). This problem has been studied before for linear functions g; in this work we initiate the study of non-linear functions by starting with quadratic monomials. For q = p^e and distinct i,j ∈ [k], we show that any scheme evaluating the quadratic monomial g_{i,j} := X_i X_j must download at least 2 log₂(q-1) - 3 bits of information when p is an odd prime, and at least 2log₂(q-2) -4 bits when p = 2. When k = 2, our result shows that one cannot do significantly better than the naive bound of k log₂(q) bits, which is enough to recover all of 𝐟. This contrasts sharply with prior work for low-bandwidth evaluation of linear functions g(𝐟) over Reed-Solomon encoded data, for which it is possible to substantially improve upon this bound [Venkatesan Guruswami and Mary Wootters, 2016; Tamo et al., 2018; Shutty and Wootters, 2021; Kiah et al., 2024; Con and Tamo, 2022]. Some proofs have been omitted from this extended abstract; the full version can be found at [Keller Blackwell and Mary Wootters, 2025].

STOC ’25, Prague, Czechia

Robust Gray codes were introduced by (Lolck and Pagh, SODA 2024). Informally, a robust Gray code is a (binary) Gray code$\mathcal {G}$so that, given a noisy version of the encoding$\mathcal {G}(j)$of an integer j, one can recover$\hat {j}$that is close to j (with high probability over the noise). Such codes have found applications in differential privacy. In this work, we present near-optimal constructions of robust Gray codes. In more detail, we construct a Gray code$\mathcal {G}$of rate$1 - H_{2}(p) - \varepsilon $that is efficiently encodable, and that is robust in the following sense. Supposed that$\mathcal {G}(j)$is passed through the binary symmetric channel${\text {BSC}}_{p}$with cross-over probability p, to obtain x. We present an efficient decoding algorithm that, given x, returns an estimate$\hat {j}$so that$| j - \hat {j}|$is small with high probability.

The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $ε^2$ has relative distance at least $\frac{1}{2} - O(ε)$ with high probability. However, it is a major challenge to construct explicit codes with similar parameters. One hope to derandomize the Gilbert--Varshamov construction is with code concatenation: We begin with a (hopefully explicit) outer code ${C}_\mathrm{out}$ over a large alphabet, and concatenate that with a small binary random linear code ${C}_\mathrm{in}$. It is known that when we use independent small codes for each coordinate, then the result lies on the GV bound with high probability, but this still uses a lot of randomness. In this paper, we consider the question of whether code concatenation with a single random linear inner code ${C}_\mathrm{in}$ can lie on the GV bound; and if so what conditions on ${C}_\mathrm{out}$ are sufficient for this. We show that first, there do exist linear outer codes ${C}_\mathrm{out}$ that are "good" for concatenation in this sense (in fact, most linear codes codes are good). We also provide two sufficient conditions for ${C}_\mathrm{out}$, so that if ${C}_\mathrm{out}$ satisfies these, ${C}_\mathrm{out}\circ {C}_\mathrm{in}$ will likely lie on the GV bound. We hope that these conditions may inspire future work towards constructing explicit codes ${C}_\mathrm{out}$.

A Homomorphic Secret Sharing (HSS) scheme is a secret-sharing scheme that shares a secret $x$ among $s$ servers, and additionally allows an output client to reconstruct some function $f(x)$, using information that can be locally computed by each server. A key parameter in HSS schemes is download rate, which quantifies how much information the output client needs to download from each server. Recent work (Fosli, Ishai, Kolobov, and Wootters, ITCS 2022) established a fundamental limitation on the download rate of linear HSS schemes for computing low-degree polynomials, and gave an example of HSS schemes that meet this limit. In this paper, we further explore optimal-rate linear HSS schemes for polynomials. Our main result is a complete characterization of such schemes, in terms of a coding-theoretic notion that we introduce, termed optimal labelweight codes. We use this characterization to answer open questions about the amortization required by HSS schemes that achieve optimal download rate. In more detail, the construction of Fosli et al. required amortization over $\ell$ instances of the problem, and only worked for particular values of $\ell$. We show that -- perhaps surprisingly -- the set of $\ell$'s for which their construction works is in fact nearly optimal, possibly leaving out only one additional value of $\ell$. We show this by using our coding-theoretic characterization to prove a necessary condition on the $\ell$'s admitting optimal-rate linear HSS schemes. We then provide a slightly improved construction of optimal-rate linear HSS schemes, where the set of allowable $\ell$'s is optimal in even more parameter settings. Moreover, based on a connection to the MDS conjecture, we conjecture that our construction is optimal for all parameter regimes.

A robust Gray code, formally introduced by (Lolck and Pagh, SODA 2024), is a Gray code that additionally has the property that, given a noisy version of the encoding of an integer$j$, it is possible to reconstruct$\hat{j}$so that$\vert j-\hat{j}\vert$is small with high probability. That work presented a transformation that transforms a binary code$\mathcal{C}$of rate$R$to a robust Gray code with rate$\Omega(R)$, where the constant in the$\Omega(\cdot)$can be at most 1/4. We improve upon their construction by presenting a transformation from a (linear) binary code$\mathcal{C}$to a robust Gray code with similar robustness guarantees, but with rate that can approach$R/2$. A full version of this paper can be found in [1].

Quantum low-density parity-check (LDPC) codes, a class of quantum error correcting codes, are considered a blueprint for scalable quantum circuits. To use these codes, one needs efficient decoding algorithms. In the classical setting, there are multiple efficient decoding algorithms available, including Viderman's algorithm (Viderman, TOCT 2013). Viderman's algorithm for classical LDPC codes essentially reduces the error- correction problem to that of erasure-correction, by identifying a small envelope L that is guaranteed to contain the error set.

Abstract. This paper shows that there exist Reed–Solomon (RS) codes, over exponentially large finite fields in the code length, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving the list-decoding capacity. In particular, we show that for any [Formula: see text] there exist RS codes with rate [Formula: see text] that are list-decodable from radius of [Formula: see text]. We generalize this result to list-recovery, showing that there exist [Formula: see text]-list-recoverable RS codes with rate [Formula: see text]. Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. We also state a new conjecture that generalizes the tree packing theorem to hypergraphs and show that if this conjecture holds, then there would exist RS codes that are optimally (nonasymptotically) list-decodable.

We show that Gallager's ensemble of low-density parity-check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue toward truly linear-time list-decodable codes that achieve list-decoding capacity. Our result on list-decoding follows from a much more general result: any local property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords and include list-decodability, list-recoverability, and average-radius list-decodability. In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property $\mathcal{P}$, there is some $R^*$ so that random linear codes of rate slightly less than $R^*$ satisfy $\mathcal{P}$ with high probability, while random linear codes of rate slightly more than $R^*$, with high probability, do not. We also give a characterization of the threshold rate $R^*$.

This paper presents two repair schemes for low-rate Reed-Solomon (RS) codes over prime fields that can repair any node by downloading a constant number of bits from each surviving node. The total bandwidth resulting from these schemes is greater than that incurred during trivial repair; however, this is particularly relevant in the context of leakage-resilient secret sharing. In that framework, our results provide attacks showing that k-out-of-n Shamir’s Secret Sharing over prime fields for small k is not leakage-resilient, even when the parties leak only a constant number of bits. To the best of our knowledge, these are the first such attacks. Our results are derived from a novel connection between exponential sums and the repair of RS codes. Specifically, we establish that non-trivial bounds on certain exponential sums imply the existence of explicit nonlinear repair schemes for RS codes over prime fields.

This paper presents several repair schemes for lowrate Reed Solomon (RS) codes over prime fields that can repair any node by downloading a constant number of bits from each surviving node. The resulting total bandwidth is higher than the bandwidth incurred during the trivial repair; however, this is still interesting in the context of leakage-resilient secret sharing. In that language, our results give attacks that show that k-out-of-n Shamir’s Secret Sharing over prime fields for small k is not leakage resilient, even if the parties only leak a constant number of bits. To the best of our knowledge, these are the first such attacks.As another application, we provide decoding schemes for RS codes over prime fields, where the entire RS codeword is recovered by transmitting a constant number of bits from each node.Our results follow from a novel connection between exponential sums and repair of RS codes. In particular, we show that nontrivial bounds on certain exponential sums imply the existence of efficient nonlinear repair schemes for RS codes over prime fields.

Abstract. We show new and improved list decoding properties of folded Reed–Solomon (RS) codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the source of recent advances in coding theory: folded RS codes were the first known explicit construction of capacity-achieving list decodable codes [V. Guruswami and A. Rudra, IEEE Trans. Inform. Theory, 54 (2008), pp. 135–150], and multiplicity codes were the first construction of high-rate locally decodable codes [S. Kopparty, S. Saraf, and S. Yekhanin, J. ACM, 61 (2014), 28]. In this work, we show that folded RS codes and multiplicity codes are in fact better than previously known in the context of list decoding and local list decoding. Our first main result shows that folded RS codes achieve list decoding capacity with constant list sizes, independent of the block length. Prior work with constant list sizes first obtained list sizes that are polynomial in the block length and relied on pre-encoding with subspace evasive sets to reduce the list sizes to a constant [V. Guruswami and C. Wang, IEEE Trans. Inform. Theory, 59 (2013), pp. 3257–3268], [Z. Dvir and S. Lovett, Proc. 44 th STOC, ACM, 2012, 351–358]. The list size we obtain is [Formula: see text] where [Formula: see text] is the gap to capacity, which matches the list size obtained by pre-encoding with subspace evasive sets. For our second main result, we observe that univariate multiplicity codes exhibit similar behavior, and we use this, together with additional ideas, to show that multivariate multiplicity codes are locally list decodable up to their minimum distance. By known reductions, this gives, in turn, capacity-achieving locally list decodable codes with query complexity [Formula: see text]. This improves on the tensor-based construction of [B. Hemenway, N. Ron-Zewi, and M. Wootters, SIAM J. Comput., 49 (2019), pp. 157–195], which gave capacity-achieving locally list decodable codes of query complexity [Formula: see text], and is close to the best known query complexity of [Formula: see text] for high-rate locally (uniquely) decodable codes [S. Kopparty et al., J. ACM, 64 (2017), 11].

We study asynchronous finite sum minimization in a distributed-data setting with a central parameter server. While asynchrony is well understood in parallel settings where the data is accessible by all machines—e.g., modifications of variance-reduced gradient algorithms like SAGA work well—little is known for the distributed-data setting. We develop an algorithm ADSAGA based on SAGA for the distributed-data setting, in which the data is partitioned between many machines. We show that with $m$ machines, under a natural stochastic delay model with an mean delay of $m$, ADSAGA converges in $\tilde{O}\left(\left(n + \sqrt{m}\kappa\right)\log(1/\epsilon)\right)$ iterations, where $n$ is the number of component functions, and $\kappa$ is a condition number. This complexity sits squarely between the complexity $\tilde{O}\left(\left(n + \kappa\right)\log(1/\epsilon)\right)$ of SAGA without delays and the complexity $\tilde{O}\left(\left(n + m\kappa\right)\log(1/\epsilon)\right)$ of parallel asynchronous algorithms where the delays are arbitrary (but bounded by $O(m)$), and the data is accessible by all. Existing asynchronous algorithms with distributed-data setting and arbitrary delays have only been shown to converge in $\tilde{O}(n^2\kappa\log(1/\epsilon))$ iterations. We empirically compare on least-squares problems the iteration complexity and wallclock performance of ADSAGA to existing parallel and distributed algorithms, including synchronous minibatch algorithms. Our results demonstrate the wallclock advantage of variance-reduced asynchronous approaches over SGD or synchronous approaches.

An error correcting code 𝒞 : Σ^k → Σⁿ is efficiently list-recoverable from input list size 𝓁 if for any sets ℒ₁, …, ℒ_n ⊆ Σ of size at most 𝓁, one can efficiently recover the list ℒ = {x ∈ Σ^k : ∀ j ∈ [n], 𝒞(x)_j ∈ ℒ_j}. While list-recovery has been well-studied in error correcting codes, all known constructions with "efficient" algorithms are not efficient in the parameter 𝓁. In this work, motivated by applications in algorithm design and pseudorandomness, we study list-recovery with the goal of obtaining a good dependence on 𝓁. We make a step towards this goal by obtaining it in the weaker case where we allow a randomized encoding map and a small failure probability, and where the input lists are derived from unions of codewords. As an application of our construction, we give a data structure for the heavy hitters problem in the strict turnstile model that, for some parameter regimes, obtains stronger guarantees than known constructions.

A homomorphic secret sharing (HSS) scheme is a secret sharing scheme that supports evaluating functions on shared secrets by means of a local mapping from input shares to output shares. We initiate the study of the download rate of HSS, namely, the achievable ratio between the length of the output shares and the output length when amortized over $\ell$ function evaluations. We obtain the following results. * In the case of linear information-theoretic HSS schemes for degree-$d$ multivariate polynomials, we characterize the optimal download rate in terms of the optimal minimal distance of a linear code with related parameters. We further show that for sufficiently large $\ell$ (polynomial in all problem parameters), the optimal rate can be realized using Shamir's scheme, even with secrets over $\mathbb{F}_2$. * We present a general rate-amplification technique for HSS that improves the download rate at the cost of requiring more shares. As a corollary, we get high-rate variants of computationally secure HSS schemes and efficient private information retrieval protocols from the literature. * We show that, in some cases, one can beat the best download rate of linear HSS by allowing nonlinear output reconstruction and $2^{-Ω(\ell)}$ error probability.

We study the problem of efficiently computing on encoded data. More specifically, we study the question of low-bandwidth computation of functions $F:\mathbb{F}^k \to \mathbb{F}$ of some data $x \in \mathbb{F}^k$, given access to an encoding $c \in \mathbb{F}^n$ of $x$ under an error correcting code. In our model -- relevant in distributed storage, distributed computation and secret sharing -- each symbol of $c$ is held by a different party, and we aim to minimize the total amount of information downloaded from each party in order to compute $F(x)$. Special cases of this problem have arisen in several domains, and we believe that it is fruitful to study this problem in generality. Our main result is a low-bandwidth scheme to compute linear functions for Reed-Solomon codes, even in the presence of erasures. More precisely, let $ε> 0$ and let $\mathcal{C}: \mathbb{F}^k \to \mathbb{F}^n$ be a full-length Reed-Solomon code of rate $1 - ε$ over a field $\mathbb{F}$ with constant characteristic. For any $γ\in [0, ε)$, our scheme can compute any linear function $F(x)$ given access to any $(1 - γ)$-fraction of the symbols of $\mathcal{C}(x)$, with download bandwidth $O(n/(ε- γ))$ bits. In contrast, the naive scheme that involves reconstructing the data $x$ and then computing $F(x)$ uses $Θ(n \log n)$ bits. Our scheme has applications in distributed storage, coded computation, and homomorphic secret sharing.

An error correcting code exhibits the t-Disjoint Repair Group Property (t-DRGP) (for message symbols) if it is possible to recover a single symbol of a codeword (message) in t ways, each from a disjoint set of symbols of the codeword. Codes with the DRGP have found applications in private information retrieval (PIR) and distributed storage, and are related to several notions of locality in coding theory. In this work we prove an impossibility result for codes with the DRGP. We show that the redundancy of any code with the t-DRGP is ${{\Omega }}(\sqrt n )$ for all t ≥ 2. Our bound is tight, even including the leading constant, for t = 2, and is tight up to a constant factor for t = O(1). We also show an analogous result for binary codes with the t-DRGP for message symbols, which has applications to PIR.These results first appeared in 2016 and were never published. As our results have not yet been improved upon, and have been referenced by multiple works over the years, we are prompted to publish them now. We hope that publishing these results now will spur more work in the area, and in particular will lead to improved bounds.

Batch codes are a useful notion of locality for error correcting codes, originally introduced in the context of distributed storage and cryptography. Many constructions of batch codes have been given, but few lower bound (limitation) results are known, leaving gaps between the best known constructions and best known lower bounds. Towards determining the optimal redundancy of batch codes, we prove a new lower bound on the redundancy of batch codes. Specifically, we study (primitive, multiset) linear batch codes that systematically encode n information symbols, with the requirement that any multiset of k symbol requests can be obtained in disjoint ways. We show that such batch codes need $\Omega (\sqrt {nk} )$ symbols of redundancy, improving on the previous best lower bounds of $\Omega (\sqrt n + k)$ at all k = nεwith ε ∈ (0,1). Our proof follows from analyzing the dimension of the order-O(k) tensor of the batch code’s dual code.

Given a probability distribution D over the nonnegative integers, a D-repeat channel acts on an input symbol by repeating it a number of times distributed as D. For example, the binary deletion channel (D=Bernoulli) and the Poisson repeat channel (D=Poisson) are special cases. We say a D-repeat channel is square-integrable if D has finite first and second moments. In this paper, we construct explicit codes for all square-integrable D-repeat channels with rate arbitrarily close to the capacity, that are encodable and decodable in linear and quasi-linear time, respectively. We also consider possible extensions to the repeat channel model, and illustrate how our construction can be extended to an even broader class of channels capturing insertions, deletions, and substitutions.Our work offers an alternative, simplified, and more general construction to the recent work of Rubinstein [3], who attains similar results to ours in the cases of the deletion channel and the Poisson repeat channel. It also slightly improves the runtime and decoding failure probability of the polar codes constructions of Tal et al. [1] and of Pfister and Tal [2] for the deletion channel and certain insertion/deletion/substitution channels. Our techniques follow closely the approaches of Guruswami and Li [4] and Con and Shpilka [5]; what sets apart our work is that to obtain our result, we show that a capacity-achieving code for the channels in question can be assumed to have an "approximate balance" in the frequency of zeros and ones of all sufficiently long substrings of all codewords. This allows us to attain near-capacity-achieving codes in a general setting. We consider this "approximate balance" result to be of independent interest, as it can be cast in much greater generality than just repeat channels.A full version of this paper is available at https://arxiv.org/abs/2201.12746.

A family of error-correcting codes is list-decodable from error fraction$p$if, for every code in the family, the number of codewords in any Hamming ball of fractional radius$p$is less than some integer$L$. It is said to be list-recoverable for input list size$\ell $if for every sufficiently large subset of at least$L$codewords, there is a coordinate where the codewords take more than$\ell $values. In this work, we study the list size ofrandom linear codesfor both list-decoding and list-recovery as the rate approaches capacity. We show the following claims hold with high probability over the choice of the code (below$q$is the alphabet size, and$ \varepsilon > 0$is the gap to capacity). (1) A random linear code of rate$1 - \log _{q}(\ell) - \varepsilon $requires list size$L \ge \ell ^{\Omega (1/ \varepsilon)}$for list-recovery from input list size$\ell $. (2) A random linear code of rate$1 - h_{q}(p) - \varepsilon $requires list size$L \ge \left \lfloor{ {h_{q}(p)/ \varepsilon +0.99}}\right \rfloor $for list-decoding from error fraction$p$. (3) A randombinarylinear code of rate$1 - h_{2}(p) - \varepsilon $is list-decodable fromaverageerror fraction$p$with list size with$L \leq \left \lfloor{ {h_{2}(p)/ \varepsilon }}\right \rfloor + 2$. Our lower bounds follow by exhibiting an explicit subset of codewords so that this subset—or some symbol-wise permutation of it—lies in a random linear code with high probability. Our upper bound follows by strengthening a result of (Li, Wootters, 2018).

Suppose that$\mathcal {P}$is a property that may be satisfied by a random code$C \subset \Sigma ^{n}$. For example, for some$p \in (0,1)$,$\mathcal {P}$might be the property that there exist three elements of$C$that lie in some Hamming ball of radius$pn$. We say that$R^{\ast}$is thethreshold ratefor$\mathcal {P}$if a random code of rate$R^{\ast} + \varepsilon $is very likely to satisfy$\mathcal {P}$, while a random code of rate$R^{\ast} - \varepsilon $is very unlikely to satisfy$\mathcal {P}$. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably “symmetric.” For properties in this class, we show that the threshold rate is in factequalto the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property$\mathcal {P}$above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates forlist-recoveryin general.

This paper shows that there exist Reed-Solomon (RS) codes, over large finite fields, that are combinatorially list-decodable well beyond the Johnson radius, in fact almost achieving list-decoding capacity. In particular, we show that for any ε E (0,1] there exist RS codes with rate$\Omega(\frac{\varepsilon}{1\not\varepsilon(1/_{\in})+1})$that are list-decodable from radius of 1-ε. We generalize this result to list-recovery, showing that there exist$(1-\varepsilon,\ell, O(\ell/\varepsilon))$-list-recoverable RS codes with rate$\Omega\left(\frac{\varepsilon}{\sqrt{\ell}(\log(1/\varepsilon)+1)}\right)$. Along the way we use our techniques to give a new proof of a result of Blackburn on optimal linear perfect hash matrices, and strengthen it to obtain a construction of strongly perfect hash matrices. To derive the results in this paper we show a surprising connection of the above problems to graph theory, and in particular to the tree packing theorem of Nash-Williams and Tutte. We also state a new conjecture that generalizes the tree-packing theorem to hypergraphs, and show that if this conjecture holds, then there would exist RS codes that are optimally (non-asymptotically) list-decodable.11A full version of this paper is available online at https://arxiv.org/abs/2011.04453.

Suppose that 𝒫 is a property that may be satisfied by a random code C ⊂ Σⁿ. For example, for some p ∈ (0,1), 𝒫 might be the property that there exist three elements of C that lie in some Hamming ball of radius pn. We say that R^* is the threshold rate for 𝒫 if a random code of rate R^* + ε is very likely to satisfy 𝒫, while a random code of rate R^* - ε is very unlikely to satisfy 𝒫. While random codes are well-studied in coding theory, even the threshold rates for relatively simple properties like the one above are not well understood. We characterize threshold rates for a rich class of properties. These properties, like the example above, are defined by the inclusion of specific sets of codewords which are also suitably "symmetric." For properties in this class, we show that the threshold rate is in fact equal to the lower bound that a simple first-moment calculation obtains. Our techniques not only pin down the threshold rate for the property 𝒫 above, they give sharp bounds on the threshold rate for list-recovery in several parameter regimes, as well as an efficient algorithm for estimating the threshold rates for list-recovery in general.

In distributed optimization problems, a technique called gradient coding, which involves replicating data points, has been used to mitigate the effect of straggling machines. Recent work has studied approximate gradient coding, which concerns coding schemes where the replication factor of the data is too low to recover the full gradient exactly. Our work is motivated by the challenge of creating approximate gradient coding schemes that simultaneously work well in both the adversarial and stochastic models. To that end, we introduce novel approximate gradient codes based on expander graphs, in which each machine receives exactly two blocks of data points. We analyze the decoding error both in the random and adversarial straggler setting, when optimal decoding coefficients are used. We show that in the random setting, our schemes achieve an error to the gradient that decays exponentially in the replication factor. In the adversarial setting, the error is nearly a factor of two smaller than any existing code with similar performance in the random setting. We show convergence bounds both in the random and adversarial setting for gradient descent under standard assumptions using our codes. In the random setting, our convergence rate improves upon block-box bounds. In the adversarial setting, we show that gradient descent can converge down to a noise floor that scales linearly with the adversarial error to the gradient. We demonstrate empirically that our schemes achieve near-optimal error in the random setting and converge faster than algorithms which do not use the optimal decoding coefficients.

We define wedge-lifted codes, a variant of lifted codes, and we study their locality properties. We show that (taking the trace of) wedge-lifted codes yields binary codes with the$t$-disjoint repair property ($t$-DRGP). When$t= N^{1/2d}$, where$N$is the block length of the code and$d\geq 2$is any integer, our codes give improved trade-offs between redundancy and locality among binary codes.

In the emerging field of DNA storage, data is encoded as DNA sequences and stored. The data is read out again by sequencing the stored DNA. Nanopore sequencing is a new sequencing technology that has many advantages over other methods; in particular, it is cheap, portable, and can support longer reads. While several practical coding schemes have been developed for DNA storage with nanopore sequencing, the theory is not well understood. Towards that end, we study a highly abstracted (deterministic) version of the nanopore sequencer, which highlights key features that make its analysis difficult. We develop methods and theory to understand the capacity of our abstracted model, and we propose efficient coding schemes and algorithms.

We analyze greedy algorithms for the Hierarchical Aggregation (HAG) problem, a strategy introduced in [Jia et al., KDD 2020] for speeding up learning on Graph Neural Networks (GNNs). The idea of HAG is to identify and remove redundancies in computations performed when training GNNs. The associated optimization problem is to identify and remove the most redundancies. Previous work introduced a greedy approach for the HAG problem and claimed a 1-1/e approximation factor. We show by example that this is not correct, and one cannot hope for better than a 1/2 approximation factor. We prove that this greedy algorithm does satisfy some (weaker) approximation guarantee, by showing a new connection between the HAG problem and maximum matching problems in hypergraphs. We also introduce a second greedy algorithm which can out-perform the first one, and we show how to implement it efficiently in some parameter regimes. Finally, we introduce some greedy heuristics that are much faster than the above greedy algorithms, and we demonstrate that they perform well on real-world graphs. A full version of this paper is accessible at: https://arxiv.org/abs/2102.01730

In this paper, we construct codes for local recovery of erasures with high availability and constant-bounded rate from the Hermitian curve. These new codes, called Hermitian-lifted codes, are evaluation codes with evaluation set being the set of $\mathbb{F}_{q^2}$-rational points on the affine curve. The novelty is in terms of the functions to be evaluated; they are a special set of monomials which restrict to low degree polynomials on lines intersected with the Hermitian curve. As a result, the positions corresponding to points on any line through a given point act as a recovery set for the position corresponding to that point.

We study the matrix completion problem when the observation pattern is deterministic and possibly non-uniform. We propose a simple and efficient debiased projection scheme for recovery from noisy observations and analyze the error under a suitable weighted metric. We introduce a simple function of the weight matrix and the sampling pattern that governs the accuracy of the recovered matrix. We derive theoretical guarantees that upper bound the recovery error and nearly matching lower bounds that showcase optimality in several regimes. Our numerical experiments demonstrate the computational efficiency and accuracy of our approach, and show that debiasing is essential when using non-uniform sampling patterns.

Lifted Reed-Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in the context of locally correctable and testable codes. They are multivariate polynomials whose restriction to any line is a codeword of a Reed-Solomon code. We consider a generalization of their construction, which we calllifted multiplicity codes. These are multivariate polynomial codes whose restriction to any line is a codeword of a multiplicity code (Kopparty, Saraf, Yekhanin 2014). We show that lifted multiplicity codes have a better trade-off between redundancy and a notion of locality called the$t$-disjoint-repair-group property than previously known constructions. As a corollary, they also give better tradeoffs for PIR codes in the same parameter regimes. More precisely, we show that, for$t\le \sqrt {N}$, lifted multiplicity codes with length$N$and redundancy$O(t^{0.585} \sqrt {N})$have the property that any symbol of a codeword can be reconstructed in$t$different ways, each using a disjoint subset of the other coordinates. This gives the best known trade-off for this problem for any super-constant$t < \sqrt {N}$. We also give an alternative analysis of lifted Reed-Solomon codes using dual codes, which may be of independent interest.

There has been a great deal of work establishing that random linear codes are as list-decodable as uniformly random codes, in the sense that a random linear binary code of rate 1- H(p)- ∈ is (p, O(1/∈))-list-decodable with high probability. In this work, we show that such codes are (p, H(p)/∈ + 2)list-decodable with high probability, for any p ∈ (0, 1/2) and ∈ > 0. In addition to improving the constant in known list-size bounds, our argument-which is quite simple-works simultaneously for all values of p, while previous works obtaining L = O(1/∈) patched together different arguments to cover different parameter regimes. Our approach is to strengthen an existential argument of (Guruswami, Håstad, Sudan and Zuckerman, IEEE Trans. IT, 2002) to hold with high probability. To complement our upper bound for random linear codes, we also improve an argument of (Guruswami, Narayanan, IEEE Trans. IT, 2014) to obtain an essentially tight lower bound of 1/∈ on the list size of uniformly random codes; this implies that random linear codes are in fact more list-decodable than uniformly random codes, in the sense that the list sizes are strictly smaller. To demonstrate the applicability of these techniques, we use them to (a) obtain more information about the distribution of list sizes of random linear codes and (b) to prove a similar result for random linear rank-metric codes.

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes shown to have this property. This result opens up a potential avenue towards truly linear-time list-decodable codes that achieve list-decoding capacity. Our result on list decoding follows from a much more general result: any local property satisfied with high probability by a random linear code is also satisfied with high probability by a random LDPC code from Gallager's distribution. Local properties are properties characterized by the exclusion of small sets of codewords, and include list-decoding, list-recovery and average-radius list-decoding. In order to prove our results on LDPC codes, we establish sharp thresholds for when local properties are satisfied by a random linear code. More precisely, we show that for any local property P, there is some R* so that random linear codes of rate slightly less than R* satisfy P with high probability, while random linear codes of rate slightly more than R* with high probability do not. We also give a characterization of the threshold rate R*. This is an extended abstract. The full version is available at https://arxiv.org/abs/1909.06430

It has long been known that the existence of certain superquantum nonlocal correlations would cause communication complexity to collapse. The absurdity of a world in which any function could be evaluated by two players with a constant amount of communication in turn provides a tantalizing way to distinguish quantum mechanics from incorrect theories of physics; the statement “communication complexity is nontrivial” has even been conjectured to be a concise information-theoretic axiom for characterizing quantum mechanics. We directly address the viability of that perspective with two results. First, we exhibit a nonlocal game such that communication complexity collapses in any physical theory whose maximal winning probability exceeds the quantum value. Second, we consider the venerable CHSH game that initiated this line of inquiry. In that case, the quantum value is about 0.85 but it is known that a winning probability of approximately 0.91 would collapse communication complexity. We show that the 0.91 result is the best possible using a large class of proof strategies, suggesting that the communication complexity axiom is insufficient for characterizing CHSH correlations. Both results build on new insights about reliable classical computation. The first exploits our formalization of an equivalence between amplification and reliable computation, while the second follows from a rigorous determination of the threshold for reliable computation with formulas of noise-free XOR gates and noisy AND gates.

In this paper we consider the following sparse recovery problem. We have query access to a vector 𝐱 ∈ ℝ^N such that x̂ = 𝐅 𝐱 is k-sparse (or nearly k-sparse) for some orthogonal transform 𝐅. The goal is to output an approximation (in an 𝓁₂ sense) to x̂ in sublinear time. This problem has been well-studied in the special case that 𝐅 is the Discrete Fourier Transform (DFT), and a long line of work has resulted in sparse Fast Fourier Transforms that run in time O(k ⋅ polylog N). However, for transforms 𝐅 other than the DFT (or closely related transforms like the Discrete Cosine Transform), the question is much less settled. In this paper we give sublinear-time algorithms - running in time poly(k log(N)) - for solving the sparse recovery problem for orthogonal transforms 𝐅 that arise from orthogonal polynomials. More precisely, our algorithm works for any 𝐅 that is an orthogonal polynomial transform derived from Jacobi polynomials. The Jacobi polynomials are a large class of classical orthogonal polynomials (and include Chebyshev and Legendre polynomials as special cases), and show up extensively in applications like numerical analysis and signal processing. One caveat of our work is that we require an assumption on the sparsity structure of the sparse vector, although we note that vectors with random support have this property with high probability. Our approach is to give a very general reduction from the k-sparse sparse recovery problem to the 1-sparse sparse recovery problem that holds for any flat orthogonal polynomial transform; then we solve this one-sparse recovery problem for transforms derived from Jacobi polynomials. Frequently, sparse FFT algorithms are described as implementing such a reduction; however, the technical details of such works are quite specific to the Fourier transform and moreover the actual implementations of these algorithms do not use the 1-sparse algorithm as a black box. In this work we give a reduction that works for a broad class of orthogonal polynomial families, and which uses any 1-sparse recovery algorithm as a black box.

As magnetization and semiconductor based storage technologies approach their limits, bio-molecules, such as DNA, have been identified as promising media for future storage systems, due to their high storage density (petabytes/gram) and long-term durability (thousands of years). Furthermore, nanopore DNA sequencing enables high-throughput sequencing using devices as small as a USB thumb drive and thus is ideally suited for DNA storage applications. Due to the high insertion/deletion error rates associated with base-called nanopore reads, current approaches rely heavily on consensus among multiple reads and thus incur very high reading costs. We propose a novel approach which overcomes the high error rates in basecalled sequences by integrating a Viterbi error correction decoder with the basecaller, enabling the decoder to exploit the soft information available in the deep learning based basecaller pipeline. Using convolutional codes for error correction, we experimentally observed 3x lower reading costs than the state-of-the-art techniques at comparable writing costs.The code, data and Supplementary Material is available at https://github.com/shubhamchandak94/nanopore_dna_storage.

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let r > 0 be any integer. Given an inner codeC0of length d, and a d-regular bipartite expander graph G with n vertices on each side, we give an algorithm to list-decode the codeC=C(G,C0) of length nd from approximately δδrnd erasures in time n·poly (d2r/δ), where δ and δrare the relative distance and the r'th generalized relative distance ofC0, respectively. To the best of our knowledge, this is the first linear-time algorithm that can list-decode expander codes from erasures beyond their (designed) distance of approximately δ2nd. To obtain our results, we show that an approach similar to that of (Hemenway and Wootters, Information and Computation, 2018) can be used to obtain such an erasure-list-decoding algorithm with an exponentially worse dependence of the running time on r and δ; then we show how to improve the dependence of the running time on these parameters.

What combinatorial properties are satisfied by a random subspace over a finite field? For example, is it likely that not too many points lie in any Hamming ball? What about any cube? In this talk, I will discuss the answer to these questions, along with a more general characterization of the properties that are likely to be satisfied by a random subspace. The motivation for this characterization comes from error correcting codes. I will discuss how to use this characterization to make progress on the questions of list-decoding and list-recovery for random linear codes, and also to establish the list-decodability of random Low Density Parity-Check (LDPC) codes. This talk is based on the works [Mosheiff et al., 2019] and [Guruswami et al., 2020], which are joint works with Venkatesan Guruswami, Ray Li, Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, and Shashwat Silas.

We show that the tensor product of a high-rate globally list recoverable code is (approximately) locally list recoverable. List recovery has been a useful building block in the design of list decodable codes, and our motivation is to use the tensor construction as such a building block. In particular, instantiating this construction with known constructions of high-rate globally list recoverable codes, and using appropriate transformations, we obtain the first capacity-achieving locally list decodable codes (over a large constant size alphabet), and the first capacity-achieving globally list decodable codes with nearly linear time list decoding algorithms. Our techniques are inspired by an approach of Gopalan, Guruswami, and Raghavendra [ SIAM J. Comput., 40 (2011), pp. 1432--1462] for list decoding tensor codes.

Lifted Reed Solomon Codes (Guo, Kopparty, Sudan 2013) were introduced in the context of locally correctable and testable codes. They are multivariate polynomials whose restriction to any line is a codeword of a Reed-Solomon code. We consider a generalization of their construction, which we call lifted multiplicity codes. These are multivariate polynomial codes whose restriction to any line is a codeword of a multiplicity code (Kopparty, Saraf, Yekhanin 2014). We show that lifted multiplicity codes have a better trade-off between redundancy and a notion of locality called the $t$-disjoint-repair-group property than previously known constructions. More precisely, we show that lifted multiplicity codes with length $N$ and redundancy $O(t^{0.585} \sqrt{N})$ have the property that any symbol of a codeword can be reconstructed in $t$ different ways, each using a disjoint subset of the other coordinates. This gives the best known trade-off for this problem for any super-constant $t < \sqrt{N}$. We also give an alternative analysis of lifted Reed Solomon codes using dual codes, which may be of independent interest.

In network tomography, one goal is to identify a small set of failed links in a network using as little information as possible. One way of setting up this problem is called graph-constrained group testing. Graph-constrained group testing is a variant of the classical combinatorial group testing problem, where the tests that one is allowed are additionally constrained by a graph. In this case, the graph is given by the underlying network topology. The main contribution of this work is to show that for most graphs, the constraints imposed by the graph are no constraint at all. That is, the number of tests required to identify the failed links in graph-constrained group testing is near-optimal even for the corresponding group testing problem with no graph constraints. Our approach is based on a simple randomized construction of tests. To analyze our construction, we prove new results about the size of giant components in randomly sparsified graphs. Finally, we provide empirical results which suggest that our connected-subgraph tests perform better not just in theory but also in practice, and in particular perform better on a real-world network topology.

This paper describes an architecture for the massively parallel digitization of neural action potentials. The scheme achieves simultaneous data compression and channel multiplexing through wired-OR interactions within an array of single-slope A/D converters. The achieved compression is lossy but effective at retaining the critical samples belonging to action potential spikes. Simulation results using ex-vivo experimental data from a 512-channel array show compression rates up to ~73x while maintaining ≥90% reconstruction coverage for parasol cells in the primate retina.

We consider distributed gradient descent in the presence of stragglers. Recent work on gradient coding and approximate gradient coding have shown how to add redundancy in distributed gradient descent to guarantee convergence even if some workers are slow or non-responsive. In this work we propose a new type of approximate gradient coding which we call Stochastic Gradient Coding (SGC). The idea of SGC is very simple: we distribute data points redundantly to workers according to a good combinatorial design. We prove that the convergence rate of SGC mirrors that of batched Stochastic Gradient Descent (SGD) for the l2loss function, and show how the convergence rate can improve with the redundancy. We show empirically that SGC requires a small amount of redundancy to handle a large number of stragglers and that it can outperform existing approximate gradient codes when the number of stragglers is large.

Motivated by applications in distributed storage and distributed computation, we introduce embedded index coding (EIC). EIC is a type of distributed index coding in which nodes in a distributed system act as both broadcast senders and receivers of information. We show how linear embedded index coding is related to linear index coding in general, and give characterizations and bounds on the communication costs of optimal embedded index codes. We also define task-based EIC, in which there is only one sender node responsible for transmitting a block to a particular receiving node. Task-based EIC is more computationally tractable and has advantages in applications such as distributed storage, in which senders may complete their broadcasts at different times. Finally, we give heuristic algorithms for approximating optimal linear embedded index codes, and demonstrate empirically that these algorithms perform well.

The world's appetite for analyzing massive amounts of structured and unstructured data has grown dramatically. The computational demands of these abundant-data applications, such as deep learning, far exceed the capabilities of today's computing systems and are unlikely to be met with isolated improvements in transistor or memory technologies, or integrated circuit architectures alone. To achieve unprecedented functionality, speed, and energy efficiency, one must create transformative nanosystems whose architectures are based on the salient properties of the underlying nanotechnologies. Our Nano-Engineered Computing Systems Technology (N3XT) approach makes such nanosystems possible through new computing system architectures leveraging emerging device (logic and memory) nanotechnologies and their dense 3-D integration with fine-grained connectivity to immerse computing in memory and new logic devices (such as carbon nanotube field-effect transistors for implementing high-speed and low-energy logic circuits) as well as high-density nonvolatile memory (such as resistive memory), and amenable to ultradense (monolithic) 3-D integration of thin layers of logic and memory devices that are fabricated at low temperature. In addition, we explore the use of several device and integration technologies in the N3XT beyond the specific ones mentioned earlier that are also used in our main nanosystem prototypes. We also present an efficient resiliency technique to overcome endurance challenges in certain resistive memory technologies. N3XT hardware prototypes demonstrate the practicality of our architectures. We evaluate the benefits of the N3XT using a simulation framework calibrated using experimental measurements. System-level energy-delay product of common implementations of abundant-data workloads improves by three orders of magnitude in the N3XT compared with conventional architectures. These improvements impact a broad range of application workloads and architecture configurations, from embedded systems to the cloud.

We consider the probabilistic group testing problem where d random defective items in a large population of N items are identified with high probability by applying binary tests. It is known that the Θ(d log N) tests are necessary and sufficient to recover the defective set with vanishing probability of error when d = O(Nα) for some α ∈ (0, 1). However, to the best of our knowledge, there is no explicit (deterministic) construction achieving Θ(d log N) tests in general. In this paper, we show that a famous construction introduced by Kautz and Singleton for the combinatorial group testing problem (which is known to be suboptimal for combinatorial group testing for moderate values of d) achieves the order optimal Θ(d log N) tests in the probabilistic group testing problem when d = Ω(log2N). This provides a strongly explicit construction achieving the order optimal result in the probabilistic group testing setting for a wide range of values of d. To prove the order-optimality of Kautz and Singleton's construction in the probabilistic setting, we provide a novel analysis of the probability of a non-defective item being covered by a random defective set directly, rather than arguing from combinatorial properties of the underlying code, which has been the main approach in the literature. Furthermore, we use a recursive technique to convert this construction into one that can also be efficiently decoded with only a log-log factor increase in the number of tests.

In distributed storage, erasure codes (like Reed-Solomon Codes) are often employed to provide reliability. In this setting, it is desirable to be able to repair one or more failed nodes while minimizing the repair bandwidth. In this paper, motivated by Reed-Solomon codes, we study the problem of repairing multiple failed nodes in a scalar MDS code. We extend the framework of (Guruswami and Wootters, 2017) to give a framework for constructing repair schemes for multiple failures in general scalar MDS codes in the centralized repair model. We then specialize our framework to Reed-Solomon codes, and also extend and improve upon recent results of (Dau et al., 2017).

We present an algorithm that efficiently performs blind decoding of MIMO signals. That is, given no channel state information (CSI) at either the transmitter or the receiver, our algorithm takes a block of samples and returns an estimate of the underlying data symbols. In prior work, the problem of blind decoding was formulated as a non-convex optimization problem. In this paper, we present an algorithm that efficiently solves this non-convex problem in practical settings. This algorithm leverages the concepts of linear and mixed-integer linear programming. Empirically, we show that our technique has an error performance close to that of zero-forcing with perfect CSI at the receiver. Initial estimates of the run time of the algorithm presented in this paper suggest that the real-time blind decoding of MIMO signals is possible for even modest-sized MIMO systems.

There has been a great deal of work establishing that random linear codes are as list-decodable as uniformly random codes, in the sense that a random linear binary code of rate 1 - H(p) - epsilon is (p,O(1/epsilon))-list-decodable with high probability. In this work, we show that such codes are (p, H(p)/epsilon + 2)-list-decodable with high probability, for any p in (0, 1/2) and epsilon > 0. In addition to improving the constant in known list-size bounds, our argument - which is quite simple - works simultaneously for all values of p, while previous works obtaining L = O(1/epsilon) patched together different arguments to cover different parameter regimes. Our approach is to strengthen an existential argument of (Guruswami, Håstad, Sudan and Zuckerman, IEEE Trans. IT, 2002) to hold with high probability. To complement our upper bound for random linear binary codes, we also improve an argument of (Guruswami, Narayanan, IEEE Trans. IT, 2014) to obtain a tight lower bound of 1/epsilon on the list size of uniformly random binary codes; this implies that random linear binary codes are in fact more list-decodable than uniformly random binary codes, in the sense that the list sizes are strictly smaller. To demonstrate the applicability of these techniques, we use them to (a) obtain more information about the distribution of list sizes of random linear binary codes and (b) to prove a similar result for random linear rank-metric codes.

In this work, we show new and improved error-correcting properties of folded Reed-Solomon codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the sources of recent advances in coding theory. Folded Reed-Solomon codes were the first explicit constructions of codes known to achieve list-decoding capacity; multivariate multiplicity codes were the first constructions of high-rate locally correctable codes; and univariate multiplicity codes are also known to achieve list-decoding capacity. However, previous analyses of the error-correction properties of these codes did not yield optimal results. In particular, in the list-decoding setting, the guarantees on the list-sizes were polynomial in the block length, rather than constant; and for multivariate multiplicity codes, local list-decoding algorithms could not go beyond the Johnson bound. In this paper, we show that Folded Reed-Solomon codes and multiplicity codes are in fact better than previously known in the context of list decoding and local list-decoding. More precisely, we first show that Folded RS codes achieve list-decoding capacity with constant list sizes, independent of the block length; and that high-rate univariate multiplicity codes can also be list-recovered with constant list sizes. Using our result on univariate multiplicity codes, we show that multivariate multiplicity codes are high-rate, locally list-recoverable codes. Finally, we show how to combine the above results with standard tools to obtain capacity achieving locally list decodable codes with query complexity significantly lower than was known before.

We introduce load-balanced fractional repetition (LBFR) codes, which are a strengthening of fractional repetition (FR) codes. LBFR codes have the additional property that multiple node failures can be sequentially repaired by downloading no more than one block from any other node. This allows for better use of the network, and can additionally reduce the number of disk reads necessary to repair multiple nodes. We characterize LBFR codes in terms of their adjacency graphs, and use this characterization to present explicit constructions of LBFR codes with storage capacity comparable to existing FR codes. Surprisingly, in some parameter regimes, our constructions of LBFR codes match the parameters of the best constructions of FR codes.

In most notions of locality in error correcting codes-notably locally recoverable codes (LRCs) and locally decodable codes (LDCs)-a decoder seeks to learn a single symbol of a message while looking at only a few symbols of the corresponding codeword. However, suppose that one wants to recover r > 1 symbols of the message. The two extremes are repeating the single-query algorithm r times (this is the intuition behind LRCs with availability, primitive multiset batch codes, and PIR codes) or simply running a global decoding algorithm to recover the whole thing. In this paper, we investigate what can happen in between these two extremes: at what value of r does repetition stop being a good idea? In order to begin to study this question we introduce robust batch codes, which seek to find r symbols of the message using m queries to the codeword, in the presence of erasures. We focus on the case where r = m, which can be seen as a generalization of the MDS property. Surprisingly, we show that for this notion of locality, repetition is optimal even up to very large values of r = Ω(k).

We analyze the list-decodability, and related notions, of random linear codes. This has been studied extensively before: there are many different parameter regimes and many different variants. Previous works have used complementary styles of arguments---which each work in their own parameter regimes but not in others---and moreover have left some gaps in our understanding of the list-decodability of random linear codes. In particular, none of these arguments work well for list-recovery, a generalization of list-decoding that has been useful in a variety of settings. In this work, we present a new approach, which works across parameter regimes and further generalizes to list-recovery. In particular, our argument provides better results for list-decoding and list-recovery over large fields; improved (quasipolynomial) list sizees for high-rate list-recovery of random linear codes; improved algorithmic results for list-decoding; and optimal average-radius list-decoding over constant-sized alphabets.

In error-correcting codes, locality refers to several different ways of quantifying how easily a small amount of information can be recovered from encoded data. In this work, we study a notion of locality called the s-Disjoint-Repair-Group Property (s-DRGP). This notion can interpolate between two very different settings in coding theory: that of Locally Correctable Codes (LCCs) when s is large---a very strong guarantee---and Locally Recoverable Codes (LRCs) when s is small---a relatively weaker guarantee. This motivates the study of the s-DRGP for intermediate s, which is the focus of our paper. We construct codes in this parameter regime which have a higher rate than previously known codes. Our construction is based on a novel variant of the lifted codes of Guo, Kopparty and Sudan. Beyond the results on the s-DRGP, we hope that our construction is of independent interest, and will find uses elsewhere.

In this work, we give the first construction of high-rate locally list-recoverable codes. List-recovery has been an extremely useful building block in coding theory, and our motivation is to use these codes as such a building block. In particular, our construction gives the first capacity-achieving locally list-decodable codes (over constant-sized alphabet); the first capacity achieving globally list-decodable codes with nearly linear time list decoding algorithm (once more, over constant-sized alphabet); and a randomized construction of binary codes on the Gilbert-Varshamov bound that can be uniquely decoded in near-linear-time, with higher rate than was previously known. Our techniques are actually quite simple, and are inspired by an approach of Gopalan, Guruswami, and Raghavendra (Siam Journal on Computing, 2011) for list-decoding tensor codes. We show that tensor powers of (globally) list-recoverable codes are `approximately' locally list-recoverable, and that the `approximately' modifier may be removed by pre-encoding the message with a suitable locally decodable code. Instantiating this with known constructions of high-rate globally list-recoverable codes and high-rate locally decodable codes finishes the construction.

We propose a method for multiple-input multiple-output (MIMO) decoding when channel-state information (CSI) is unknown to both the transmitter and receiver. The proposed method requires some structure in the transmitted signal for the decoding to be effective, in particular that the underlying sources are drawn from a hypercubic space. Our proposed technique fits a minimum volume parallelepiped to the received samples. This problem can be expressed as a non-convex optimization problem that can be solved with high probability by gradient descent. Our blind decoding algorithm can be used when communicating over unknown MIMO wireless channels using either binary phase-shift keying or MPAM modulation. We apply our technique to jointly estimate MIMO-channel gain matrices and decode the underlying transmissions with only knowledge of the transmitted constellation and without the use of pilot symbols. Our results provide theoretical guarantees that the proposed algorithm is correct when applied to MIMO systems with four or fewer transmit antennas. Empirical results show small sample size requirements, making this algorithm suitable for block-fading channels with coherence times typically seen in practice. Our approach has a loss of less than 3 dB compared to zero forcing with perfect CSI, imposing a similar performance penalty as space-time coding techniques without the loss of rate incurred by those techniques.

Binary measurements arise naturally in a variety of statistics and engineering applications. They may be inherent to the problem-for example, in determining the relationship between genetics and the presence or absence of a disease-or they may be a result of extreme quantization. A recent influx of literature has suggested that using prior signal information can greatly improve the ability to reconstruct a signal from binary measurements. This is exemplified by one-bit compressed sensing, which takes the compressed sensing model but assumes that only the sign of each measurement is retained. It has recently been shown that the number of one-bit measurements required for signal estimation mirrors that of unquantized compressed sensing. Indeed, s-sparse signals in Rn can be estimated (up to normalization) from Ω(slog (n/s)) one-bit measurements. Nevertheless, controlling the precise accuracy of the error estimate remains an open challenge. In this paper, we focus on optimizing the decay of the error as a function of the oversampling factor λ := m/(s log(n/s)), where m is the number of measurements. It is known that the error in reconstructing sparse signals from standard one-bit measurements is bounded below by Ω(λ-1). Without adjusting the measurement procedure, reducing this polynomial error decay rate is impossible. However, we show that an adaptive choice of the thresholds used for quantization can lower the error rate to e-Ω(λ). This improves upon guarantees for other methods of adaptive thresholding, such as sigma- delta quantization. We develop a general recursive strategy to achieve this exponential decay and two specific polynomial-time algorithms, which fall into this framework, one based on convex programming and one on hard thresholding. Our work bridges the one-bit compressed sensing model, in which the engineer controls the measurement procedure, to sigma-delta and successive approximation quantization. Moreover, the principle is extendable to signal reconstruction problems in a variety of binary statistical models as well as statistical estimation problems like logistic regression.

A fundamental fact about polynomial interpolation is that k evaluations of a degree-(k-1) polynomial f are sufficient to determine f. This is also necessary in a strong sense: given k-1 evaluations, we learn nothing about the value of f on any k'th point. In this paper, we study a variant of the polynomial interpolation problem. Instead of querying entire evaluations of f (which are elements of a large field F), we are allowed to query partial evaluations; that is, each evaluation delivers a few elements from a small subfield of F, rather than a single element from F. We show that in this model, one can do significantly better than in the traditional setting, in terms of the amount of information required to determine the missing evaluation. More precisely, we show that only O(k) bits are necessary to recover a missing evaluation. In contrast, the traditional method of looking at k evaluations requires Omega(k log(k)) bits. We also show that our result is optimal for linear methods, even up to the leading constants. Our motivation comes from the use of Reed-Solomon (RS) codes for distributed storage systems, in particular for the exact repair problem. The traditional use of RS codes in this setting is analogous to the traditional interpolation problem. Each node in a system stores an evaluation of f, and if one node fails we can recover it by reading k other nodes. However, each node is free to send less information, leading to the modified problem above. The quickly-developing field of regenerating codes has yielded several codes which take advantage of this freedom. However, these codes are not RS codes, and RS codes are still often used in practice; in 2011, Dimakis et al. asked how well RS codes could perform in this setting. Our results imply that RS codes can also take advantage of this freedom to download partial symbols. In some parameter regimes---those with small levels of sub-packetization---our scheme for RS codes outperforms all known regenerating codes. Even with a high degree of sub-packetization, our methods give non-trivial schemes, and we give an improved repair scheme for a specific (14,10)-RS code used in the Facebook Hadoop Analytics cluster.

Machine learning relies on the assumption that unseen test instances of a classification problem follow the same distribution as observed training data. However, this principle can break down when machine learning is used to make important decisions about the welfare (employment, education, health) of strategic individuals. Knowing information about the classifier, such individuals may manipulate their attributes in order to obtain a better classification outcome. As a result of this behavior -- often referred to as gaming -- the performance of the classifier may deteriorate sharply. Indeed, gaming is a well-known obstacle for using machine learning methods in practice; in financial policy-making, the problem is widely known as Goodhart's law. In this paper, we formalize the problem, and pursue algorithms for learning classifiers that are robust to gaming.

In this work, we introduce a framework to study the effect of random operations on the combinatorial list decodability of a code. The operations we consider correspond to row and column operations on the matrix obtained from the code by stacking the codewords together as columns. This captures many natural transformations on codes, such as puncturing, folding, and taking subcodes; we show that many such operations can improve the list-decoding properties of a code. There are two main points to this. First, our goal is to advance our (combinatorial) understanding of list-decodability, by understanding what structure (or lack thereof) is necessary to obtain it. Second, we use our more general results to obtain a few interesting corollaries for list decoding.

We give the first algorithm for Matrix Completion that achieves running time and sample complexity that is polynomial in the rank of the unknown target matrix, \emphlinear in the dimension of the matrix, and \emphlogarithmic in the condition number of the matrix. To the best of our knowledge, all previous algorithms either incurred a quadratic dependence on the condition number of the unknown matrix or a quadratic dependence on the dimension of the matrix. Our algorithm is based on a novel extension of Alternating Minimization which we show has theoretical guarantees under standard assumptions even in the presence of noise.

In this paper, we present novel constructions of matrices with the restricted isometry property (RIP) that support fast matrix-vector multiplication. Our guarantees are the best known, and can also be used to obtain the best known guarantees for fast Johnson Lindenstrauss transforms. In compressed sensing, the restricted isometry property is a sufficient condition for the efficient reconstruction of a nearly k-sparse vector x ∊ ℂd from m linear measurements Φx. It is desirable for m to be small, and further it is desirable for Φ to support fast matrix-vector multiplication. Among other applications, fast multiplication improves the runtime of iterative recovery algorithms which repeatedly multiply by Φ or Φ*. The main contribution of this work is a novel randomized construction of RIP matrices Φ ∊ ℂm×d, preserving the ℓ2 norms of all k-sparse vectors with distortion 1 + ∊, where the matrix-vector multiply Φx can be computed in nearly linear time. The number of rows m is on the order of ∊−2klogd log2(klogd), an improvement on previous analyses by a logarithmic factor. Our construction, together with a connection between RIP matrices and the Johnson-Lindenstrauss lemma in [Krahmer-Ward, SIAM. J. Math. Anal. 2011], also implies fast Johnson-Lindenstrauss embeddings with asymptotically fewer rows than previously known. Our construction is actually a recipe for improving any existing family of RIP matrices. Briefly, we apply an appropriate sparse hash matrix with sign flips to any suitable family of RIP matrices. We show that the embedding properties of the original family are maintained, while at the same time improving the number of rows. The main tool in our analysis is a recent bound for the supremum of certain types of Rademacher chaos processes in [Krahmer-Mendelson-Rauhut, Comm. Pure Appl. Math. to appear].

We show that any q-ary code with sufficiently good distance can be randomly punctured to obtain, with high probability, a code that is list decodable up to radius 1 --- 1/q --- ε with near-optimal rate and list sizes.

In this paper we consider the problem of 1-bit matrix completion, where instead of observing a subset of the real-valued entries of a matrix M, we obtain a small number of binary (1-bit) measurements generated according to a probability distribution determined by the real-valued entries of M. The central question we ask is whether or not it is possible to obtain an accurate estimate of M from this data. In general this would seem impossible, however, it has recently been shown in [1] that under certain assumptions it is possible to recover M by optimizing a simple convex program. In this paper we provide lower bounds showing that these estimates are near-optimal.

It is well known that a random q-ary code of rate Ω(ε2) is list decodable up to radius (1 - 1/q - ε) with list sizes on the order of 1/ε2, with probability 1 - o(1). However, until recently, a similar statement about random linear codes has until remained elusive. In a recent paper, Cheraghchi, Guruswami, and Velingker show a connection between list decodability of random linear codes and the Restricted Isometry Property from compressed sensing, and use this connection to prove that a random linear code of rate Ω( ε2 /log3(1/ε)) achieves the list decoding properties above, with constant probability. We improve on their result to show that in fact we may take the rate to be Ω(ε2), which is optimal, and further that the success probability is 1 - o(1), rather than constant. As an added benefit, our proof is relatively simple. Finally, we extend our methods to more general ensembles of linear codes. As an example, we show that randomly punctured Reed-Muller codes have the same list decoding properties as the original codes, even when the rate is improved to a constant.