We introduce pseudo-deterministic interactive proofs (psdAM): interactive proof systems for search problems where
the verifier is guaranteed with high probability to output the same output on different executions.
As in the case with classical interactive proofs,
the verifier is a probabilistic polynomial time algorithm interacting with an untrusted powerful prover.

... more >>>

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 >>>