In this work, we design an interactive coding scheme that converts any two party interactive protocol \Pi into another interactive protocol \Pi', such that even if errors are introduced during the execution of \Pi', the parties are able to determine what the outcome of running \Pi would be in an ... more >>>

Given a Boolean circuit C, we wish to convert it to a circuit C' that computes the same function as C even if some of its gates suffer from adversarial short circuit errors, i.e., their output is replaced by the value of one of their inputs [KLM97]. Can we ... more >>>

We show that Gallager's ensemble of Low-Density Parity Check (LDPC) codes achieve list-decoding capacity. These are the first graph-based codes shown to have this property. Previously, the only codes known to achieve list-decoding capacity were completely random codes, random linear codes, and codes constructed by algebraic (rather than combinatorial) techniques. ... more >>>

We continue the study of list recovery properties of high-rate tensor codes, initiated by Hemenway, Ron-Zewi, and Wootters (FOCS'17). In that work it was shown that the tensor product of an efficient (poly-time) high-rate globally list recoverable code is {\em approximately} locally list recoverable, as well as globally list recoverable ... more >>>

For a vector space \mathbb{F}^n over a field \mathbb{F}, an (\eta,\beta)-dimension expander of degree d is a collection of d linear maps \Gamma_j : \mathbb{F}^n \to \mathbb{F}^n such that for every subspace U of \mathbb{F}^n of dimension at most \eta n, the image of U under all the maps, $\sum_{j=1}^d ... more >>>