Parikshit Gopalan, Salil Vadhan, Yuan Zhou

We give two new characterizations of ($\F_2$-linear) locally testable error-correcting codes in terms of Cayley graphs over $\F_2^h$:

\begin{enumerate}

\item A locally testable code is equivalent to a Cayley graph over $\F_2^h$ whose set of generators is significantly larger than $h$ and has no short linear dependencies, but yields a ...
more >>>

Itai Benjamini, Oded Goldreich

We introduce the notion of pseudo-mixing time of a graph define as the number of steps in a random walk that suffices for generating a vertex that looks random to any polynomial-time observer, where, in addition to the tested vertex, the observer is also provided with oracle access to the ... more >>>