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 E N there exists an explicit bijection ψ: {0, 1}n→ {x E {0, 1}n+1 : |x| > n/2} such that for every x ≠ y E {0, 1}n+1it holds that 1/5 ≤ dist(ψ(x), ψ(y)) ≤ 4 5 - dist(x, y) where dist(·, ·) denotes the Hamming distance. In particular, this implies that the Hamming ball is bi-Lipschitz transitive. This result gives a strong negative answer to an open problem of Lovett and Viola [CC 2012], who raised the question in the context of sampling distributions in low-level complexity classes. The conceptual implication is that the problem of proving lower bounds in the context of sampling distributions requires ideas beyond the sensitivity-based structural results of Boppana [IPL 97]. We study the mapping ψ further and show that it (and its inverse) are computable in DLOGTIME-uniform TC°, but not in AC°. Moreover, we prove that ψ is “approximately local” in the sense that all but the last output bit of ψ are essentially determined by a single input bit.

We define the following parameter of connected graphs. For a given graph $G = (V,E)$ we place one agent in each vertex $v \in V$. Every pair of agents sharing a common edge is declared to be acquainted. In each round we choose some matching of $G$ (not necessarily a maximal matching), and for each edge in the matching the agents on this edge swap places. After the swap, again, every pair of agents sharing a common edge become acquainted, and the process continues. We define the acquaintance time of a graph $G$, denoted by $\mathcal{AC}(G)$, to be the minimal number of rounds required until every two agents are acquainted. We first study the acquaintance time for some natural families of graphs including the path, expanders, the binary tree, and the complete bipartite graph. We also show that for all $n \in {\mathbb N}$ and for all positive integers $k \leq n^{1.5}$ there exists an $n$-vertex graph $G$ such that $k/c \leq \mathcal{AC}(G) \leq c \cdot k$ for some universal constant $c \geq 1$. We also prove that for all $n$-vertex connected graphs $G$ we have $\mathcal{AC}(G) = O(\frac{n^2}{\log(n)/\log\log(n)})$, thus improving the trivial upper bound of $O(n^2)$ achieved by sequentially letting each agent perform depth-first search along some spanning tree of $G$. Studying the computational complexity of this problem, we prove that for any constant $t \geq 1$ the problem of deciding that a given graph $G$ has $\mathcal{AC}(G) \leq t$ or $\mathcal{AC}(G) \geq 2t$ is $\mathcal{NP}$-complete. That is, $\mathcal{AC}(G)$ is $\mathcal{NP}$-hard to approximate within multiplicative factor of 2, as well as within any additive constant factor. On the algorithmic side, we give a deterministic algorithm that given an $n$-vertex graph $G$ with $\mathcal{AC}(G)=1$ finds a strategy for acquaintance that consists of $\lceil{n/c}\rceil$ matchings in time $n^{c+O(1)}$. We also design a randomized polynomial time algorithm that given an $n$-vertex graph $G$ with $\mathcal{AC}(G)=1$ finds with high probability an $O(\log(n))$-rounds strategy for acquaintance.

One of the fundamental problems in distributed computing is how to efficiently perform routing in a faulty network in which each link fails with some probability. This paper investigates how big the failure probability can be, before the capability to efficiently find a path in the network is lost. Our main results show tight upper and lower bounds for the failure probability which permits routing, both for the hypercube and for the d-dimensional mesh. We use tools from percolation theory to show that in the d-dimensional mesh, once a giant component appears --- efficient routing is possible. A different behavior is observed when the hypercube is considered. In the hypercube there is a range of failure probabilities in which short paths exist with high probability, yet finding them must involve querying essentially the entire network. Thus the routing complexity of the hypercube shows an asymptotic phase transition. The critical probability with respect to routing complexity lies in a different location then that of the critical probability with respect to connectivity. Finally we show that an oracle access to links (as opposed to local routing) may reduce significantly the complexity of the routing problem. We demonstrate this fact by providing tight upper and lower bounds for the complexity of routing in the random graph Gn,p.

A Boolean function of n bits is balanced if it takes the value 1 with probability 1⁄2. We exhibit a balanced Boolean function with a randomized evaluation procedure (with probability 0 of making a mistake) so that on uniformly random inputs, no input bit is read with probability more than Θ(n-1/2√ log n). We construct a balanced monotone Boolean function and a randomized algorithm computing it for which each bit is read with probability Θ(n-1⁄3 log n). We then show that for any randomized algorithm for evaluating a balanced Boolean function, when the input bits are uniformly random, there is some input bit that is read with probability at least Θ(n-1𔊪). For balanced monotone Boolean functions, there is some input bit that is read with probability at least Θ(n-1𔊫).

We observe a certain random process on a graph "locally", i.e., in the neighborhood of a node, and would like to derive information about "global" properties of the graph. For example, what can we know about a graph based on observing the returns of a random walk to a given node? Our main result concerns a graph embedded in an orientable surface with genus g, and a process, consisting of random excitations of edges and random balancing around nodes and faces. It is shown how to obtain the genus of the surface in polynomial time from local observations of the process restricted to a connected subgraph whose size is (essentially) O(g/sup 2/).