Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Caylay graphs:
TR13-114 | 24th August 2013
Parikshit Gopalan, Salil Vadhan, Yuan Zhou

Locally Testable Codes and Cayley Graphs

Revisions: 1

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

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

TR19-078 | 1st June 2019
Itai Benjamini, Oded Goldreich

Pseudo-Mixing Time of Random Walks

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

ISSN 1433-8092 | Imprint