All reports by Author Itai Benjamini:

__
TR13-138
| 5th October 2013
__

Itai Benjamini, Gil Cohen, Igor Shinkar#### Bi-Lipschitz Bijection between the Boolean Cube and the Hamming Ball

Revisions: 1

__
TR08-010
| 17th January 2008
__

Itai Benjamini, Oded Schramm, Asaf Shapira#### Every Minor-Closed Property of Sparse Graphs is Testable

Itai Benjamini, Gil Cohen, Igor Shinkar

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

Itai Benjamini, Oded Schramm, Asaf Shapira

Testing a property P of graphs in the bounded degree model deals with the following problem: given a graph G of bounded degree d we should distinguish (with probability 0.9, say) between the case that G satisfies P and the case that one should add/remove at least \epsilon d n ... more >>>