In this work, we give the first construction of {\em 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 {\em capacity-achieving} locally list-decodable ... more >>>

We investigate the parameters in terms of which the complexity of sublinear-time algorithms should be expressed. Our goal is to find input parameters that are tailored to the combinatorics of the specific problem being studied and design algorithms that run faster when these parameters are small. This direction enables us ... more >>>

We provide an overview of the doubly-efficient interactive proof systems of Reingold, Rothblum, and Rothblum (STOC, 2016).
Recall that by their result, any set that is decidable in polynomial-time by an algorithm of space complexity $s(n)\leq n^{0.499}$, has a constant-round interactive proof system
in which the prover runs polynomial time ... more >>>