Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > METRIC EMBEDDINGS:
Reports tagged with metric embeddings:
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$:

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

TR13-138 | 5th October 2013
Itai Benjamini, Gil Cohen, Igor Shinkar

#### Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

Revisions: 1

We construct a bi-Lipschitz bijection from the Boolean cube to the Hamming ball of equal volume. More precisely, we show that for all even $n \in {\mathbb N}$ there exists an explicit bijection $\psi \colon \{0,1\}^n \to \left\{ x \in \{0,1\}^{n+1} \colon |x| > n/2 \right\}$ such that for every ... more >>>

ISSN 1433-8092 | Imprint