Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR08-010 | 17th January 2008
Itai Benjamini, Oded Schramm, Asaf Shapira

Every Minor-Closed Property of Sparse Graphs is Testable

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

ISSN 1433-8092 | Imprint