We show that every n-point tree metric admits a (1+eps)-embedding into a C(eps) log n-dimensional L_1 space, for every eps > 0, where C(eps) = O((1 eps)^4 log(1 eps)). This matches the natural volume lower bound up to a factor depending only on eps. Previously, it was unknown whether even complete binary trees on n nodes could be embedded in O(log n) dimensions with O(1) distortion. For complete d-ary trees, our construction achieves C(eps) = O(1 eps^2).
Unfortunately, the use of the Local Lemma does not extend well to the more difficult setting of arbitrary trees. For the general case, we employ an idea of Schulman @cite_7 based on re-randomization . To see the idea in our simple setting, consider @math to be composed of a root @math , under which lie two copies of @math , which we call @math and @math , having roots @math and @math , respectively.
@cite_7
2115551261
Let the input to a computation problem be split between two processors connected by a communication link; and let an interactive protocol spl pi be known by which, on any input, the processors can solve the problem using no more than T transmissions of bits between them, provided the channel is noiseless in each direction. We study the following question: if in fact the channel is noisy, what is the effect upon the number of transmissions needed in order to solve the computation problem reliably? Technologically this concern is motivated by the increasing importance of communication as a resource in computing, and by the tradeoff in communications equipment between bandwidth, reliability, and expense. We treat a model with random channel noise. We describe a deterministic method for simulating noiseless-channel protocols on noisy channels, with only a constant slowdown. This is an analog for general, interactive protocols of Shannon's coding theorem, which deals only with data transmission, i.e., one-way protocols. We cannot use Shannon's block coding method because the bits exchanged in the protocol are determined only one at a time, dynamically, in the course of the interaction. Instead, we describe a simulation protocol using a new kind of code, explicit tree codes.