A major open problem in the field of metric embedding is the existence of dimension reduction for @math -point subsets of Euclidean space, such that both distortion and dimension depend only on the doubling constant of the pointset, and not on its cardinality. In this paper, we negate this possibility for @math spaces with @math . In particular, we introduce an @math -point subset of @math with doubling constant O(1), and demonstrate that any embedding of the set into @math with distortion @math must have @math .
The first impossibility result on dimension reduction in @math is due to @cite_48 , who showed that there exists an @math -point subset of @math that requires @math for any @math -distortion embedding to @math . Following their work, there have been many different proofs and extensions of this result, using various techniques. The original @cite_48 argument was based on linear programming and duality, then @cite_44 gave a geometric proof. For the @math distortion regime, @cite_20 used combinatorial techniques to show that the dimension must be at least @math (and also gave a different proof of the original result). Recently @cite_39 applied an information theoretic argument to reprove the results of @cite_48 @cite_20 . As for linear dimension reductions, @cite_38 showed a strong lower bound for @math with @math .
@cite_38 @cite_48 @cite_39 @cite_44 @cite_20
2036959865 2149463264 2045745231 2001085501
Given a set of @math points in @math , how many dimensions are needed to represent all pair wise distances within a specific distortion? This dimension-distortion tradeoff question is well understood for the @math norm, where @math dimensions suffice to achieve @math distortion. In sharp contrast, there is a significant gap between upper and lower bounds for dimension reduction in @math . A recent result shows that distortion @math can be achieved with @math dimensions. On the other hand, the only lower bounds known are that distortion @math requires @math dimensions and that distortion @math requires @math dimensions. In this work, we show the first near linear lower bounds for dimension reduction in @math . In particular, we show that @math distortion requires at least @math dimensions. Our proofs are combinatorial, but inspired by linear programming. In fact, our techniques lead to a simple combinatorial argument that is equivalent to the LP based proof of Brinkman-Charikar for lower bounds on dimension reduction in @math . We investigate the minimization of Newton's functional for the problem of the body of minimal resistance with maximal height @math cite butt in the class of convex developable functions defined in a disc. This class is a natural candidate to find a (non-radial) minimizer in accordance with the results of cite lrp2. We prove that the minimizer in this class has a minimal set in the form of a regular polygon with @math sides centered in the disc, and numerical experiments indicate that the natural number @math is a non-decreasing function of @math . The corresponding functions all achieve a lower value of the functional than the optimal radially symmetric function with the same height @math . Given a linear code @math , one can define the @math -th power of @math as the span of all componentwise products of @math elements of @math . A power of @math may quickly fill the whole space. Our purpose is to answer the following question: does the square of a code "typically" fill the whole space? We give a positive answer, for codes of dimension @math and length roughly @math or smaller. Moreover, the convergence speed is exponential if the difference @math is at least linear in @math . The proof uses random coding and combinatorial arguments, together with algebraic tools involving the precise computation of the number of quadratic forms of a given rank, and the number of their zeros. We show that the greedy spanner algorithm constructs a @math -spanner of weight @math for a point set in metrics of doubling dimension @math , resolving an open problem posed by Gottlieb. Our result generalizes the result by Narasimhan and Smid who showed that a point set in @math -dimension Euclidean space has a @math -spanner of weight at most @math . Our proof only uses the packing property of doubling metrics and thus implies a much simpler proof for the same result in Euclidean space. A set @math is called an antichain (resp. antichain) if it does not contain two distinct elements @math and @math satisfying @math (resp. @math ) for all @math . We show that the Hausdorff dimension of a weak antichain @math in the @math -dimensional unit cube @math is at most @math and that the @math -dimensional Hausdorff measure of @math is at most @math , which are the best possible bounds. This result is derived as a corollary of the following projection inequality , which may be of independent interest: The @math -dimensional Hausdorff measure of a (weak) antichain @math cannot exceed the sum of the @math -dimensional Hausdorff measures of the @math orthogonal projections of @math onto the facets of the unit @math -cube containing the origin. For the proof of this result we establish a discrete variant of the projection inequality applicable to weak antichains in @math and combine it with ideas from geometric measure theory.