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 instances used by the papers mentioned above are based on recursive graph constructions. The papers of @cite_48 @cite_44 used the diamond graph, which has high doubling constant, but @cite_38 showed that their proof can be extended to the Laakso graph, yielding essentially the same result but for a subset of low doubling dimension. For the @math space, there are also strong lower bounds, For instance, the metric induced by an @math -point expander graph (which is in @math as any other finite metric), requires dimension at least @math in any @math distortion embedding. which are based on large girth graphs @cite_3 measure concentration @cite_24 and geometric arguments @cite_38 .
@cite_38 @cite_48 @cite_3 @cite_44 @cite_24
2036959865 2149463264 2167816765 2093171982
This paper addresses the basic question of how well a tree can approximate distances of a metric space or a graph. Given a graph, the problem of constructing a spanning tree in a graph which strongly preserves distances in the graph is a fundamental problem in network design. We present scaling distortion embeddings where the distortion scales as a function of @math , with the guarantee that for each @math simultaneously, the distortion of a fraction @math of all pairs is bounded accordingly. Quantitatively, we prove that any finite metric space embeds into an ultrametric with scaling distortion @math . For the graph setting, we prove that any weighted graph contains a spanning tree with scaling distortion @math . These bounds are tight even for embedding into arbitrary trees. These results imply that the average distortion of the embedding is constant and that the @math distortion is @math . For probabilistic embedding into spanning trees we prove a scaling distortion of @math , which implies constant @math -distortion for every fixed @math . Let @math be a 3-uniform hypergraph of order @math and size @math , and let @math be a subset of vertices of @math . The set @math is a strong transversal in @math if @math contains at least two vertices from every edge of @math . The strong transversal number @math of @math is the minimum size of a strong transversal in @math . We show that @math , and we characterize the hypergraphs that achieve equality in this bound. In particular, we show that the Fano plane is the only connected 3-uniform hypergraph @math of order @math and size @math that achieves equality in this bound. A set @math of vertices in a graph @math is a double total dominating set of @math if every vertex of @math is adjacent to at least two vertices in @math . The minimum cardinality of a double total dominating set of @math is the double total domination number @math of @math . Let @math be a connected graph of order @math with minimum degree at least three. As an application of our hypergraph results, we show that @math with equality if and only if @math is the Heawood graph (equivalently, the incidence bipartite graph of the Fano plane). Further if @math is not the Heawood graph, we show that @math , while if @math is a cubic graph different from the Heawood graph, we show that @math , and this bound is sharp. 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 . The greedy spanner is arguably the simplest and most well-studied spanner construction. Experimental results demonstrate that it is at least as good as any other spanner construction, in terms of both the size and weight parameters. However, a rigorous proof for this statement has remained elusive. In this work we fill in the theoretical gap via a surprisingly simple observation: The greedy spanner is (or existentially near-optimal) for several important graph families. Focusing on the weight parameter, the state-of-the-art spanner constructions for both general graphs (due to Chechik and Wulff-Nilsen [SODA'16]) and doubling metrics (due to Gottlieb [FOCS'15]) are complex. Plugging our observation on these results, we conclude that the greedy spanner achieves near-optimal weight guarantees for both general graphs and doubling metrics, thus resolving two longstanding conjectures in the area. Further, we observe that approximate-greedy algorithms are existentially near-optimal as well. Consequently, we provide an @math -time construction of @math -spanners for doubling metrics with constant lightness and degree. Our construction improves Gottlieb's construction, whose runtime is @math and whose number of edges and degree are unbounded, and remarkably, it matches the state-of-the-art Euclidean result (due to [SICOMP'02]) in all the involved parameters (up to dependencies on @math and the dimension). This paper gives a new way of showing that certain constant degree graphs are graph expanders. This is done by giving new proofs of expansion for three permutations of the Gabber-Galil expander. Our results give an expansion factor of @math for subgraphs of these three-regular graphs with @math inputs for @math prime. The proofs are not based on eigenvalue methods or higher algebra. The same methods show the expected number of probes for unsuccessful search in double hashing is bounded by @math , where a is the load factor. This assumes a double hashing scheme in which two hash functions are randomly and independently chosen from a specified uniform distribution. The result is valid regardless of the distribution of the inputs. This is analogous to Carter and Wegman’s result for hashing with chaining. This paper concludes by elaborating on how any sufficiently sized subset of inputs in any distribution expands in the subgraph of the Gabber-Galil graph expander of focus. This is related to any key distribution having expected @math probes for unsuccessful search for double hashing given the initial random, independent, and uniform choice of two universal hash functions. 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. 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 . The doubling constant of a metric space (X, d) is the smallest value spl lambda such that every ball in X can be covered by spl lambda balls of half the radius. The doubling dimension of X is then defined as dim (X) = log sub 2 spl lambda . A metric (or sequence of metrics) is called doubling precisely when its doubling dimension is bounded. This is a robust class of metric spaces which contains many families of metrics that occur in applied settings. We give tight bounds for embedding doubling metrics into (low-dimensional) normed spaces. We consider both general doubling metrics, as well as more restricted families such as those arising from trees, from graphs excluding a fixed minor, and from snowflaked metrics. Our techniques include decomposition theorems for doubling metrics, and an analysis of a fractal in the plane according to T. J. Laakso (2002). Finally, we discuss some applications and point out a central open question regarding dimensionality reduction in L sub 2 . A t-spanner is a graph on a set of points Swith the following property: Between any pair of points there is a path in the spanner whose total length is at most ttimes the actual distance between the points. In this paper, we consider points residing in a metric space equipped with doubling dimension i¾?, and show how to construct a dynamic (1 + i¾?)-spanner with degree i¾?i¾? O(i¾?)in @math update time. When i¾?and i¾?are taken as constants, the degree and update times are optimal. Given a finite metric, one can construct its tight span, a geometric object representing the metric. The dimension of a tight span encodes, among other things, the size of the space of explanatory trees for that metric; for instance, if the metric is a tree metric, the dimension of the tight span is one. We show that the dimension of the tight span of a generic metric is between @math and @math that both bounds are tight. A citing sentence is one that appears in a scientific article and cites previous work. Citing sentences have been studied and used in many applications. For example, they have been used in scientific paper summarization, automatic survey generation, paraphrase identification, and citation function classification. Citing sentences that cite multiple papers are common in scientific writing. This observation should be taken into consideration when using citing sentences in applications. For instance, when a citing sentence is used in a summary of a scientific paper, only the fragments of the sentence that are relevant to the summarized paper should be included in the summary. In this paper, we present and compare three different approaches for identifying the fragments of a citing sentence that are related to a given target reference. Our methods are: word classification, sequence labeling, and segment classification. Our experiments show that segment classification achieves the best results. This paper addresses two problems lying at the intersection of geometric analysis and theoretical computer science: The non-linear isomorphic Dvoretzky theorem and the design of good approximate distance oracles for large distortion. We introduce the notion of Ramsey partitions of a finite metric space, and show that the existence of good Ramsey partitions implies a solution to the metric Ramsey problem for large distortion (a.k.a. the non-linear version of the isomorphic Dvoretzky theorem, as introduced by Bourgain, Figiel, and Milman in BFM86 ). We then proceed to construct optimal Ramsey partitions, and use them to show that for every @math , every @math -point metric space has a subset of size @math which embeds into Hilbert space with distortion @math . This result is best possible and improves part of the metric Ramsey theorem of Bartal, Linial, Mendel and Naor BLMN05 , in addition to considerably simplifying its proof. We use our new Ramsey partitions to design approximate distance oracles with a universal constant query time, closing a gap left open by Thorup and Zwick in TZ05 . Namely, we show that for every @math point metric space @math , and @math , there exists an @math -approximate distance oracle whose storage requirement is @math , and whose query time is a universal constant. We also discuss applications of Ramsey partitions to various other geometric data structure problems, such as the design of efficient data structures for approximate ranking. We develop the notion of "double samplers", first introduced by Dinur and Kaufman [Proc. 58th FOCS, 2017], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders. We show how double samplers give a generic way of amplifying distance in a way that enables efficient list-decoding. There are many error correcting code constructions that achieve large distance by starting with a base code @math with moderate distance, and then amplifying the distance using a sampler, e.g., the ABNNR code construction [IEEE Trans. Inform. Theory, 38(2):509--516, 1992.]. We show that if the sampler is part of a larger double sampler then the construction has an efficient list-decoding algorithm and the list decoding algorithm is oblivious to the base code @math (i.e., it runs the unique decoder for @math in a black box way). Our list-decoding algorithm works as follows: it uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an expander, so we can solve unique games efficiently. These solutions are the output of the list decoder. This is a novel use of a unique games algorithm as a subroutine in a decoding procedure, as opposed to the more common situation in which unique games are used for demonstrating hardness results. Double samplers and high dimensional expanders are akin to pseudorandom objects in their utility, but they greatly exceed random objects in their combinatorial properties. We believe that these objects hold significant potential for coding theoretic constructions and view this work as demonstrating the power of double samplers in this context. A standard result in metric geometry is that every compact geodesic metric space can be approximated arbitrarily well by finite metric graphs in the Gromov-Hausdorff sense. It is well known that the first Betti number of the approximating graphs may blow up as the approximation gets finer. In our work, given a compact geodesic metric space @math , we define a sequence @math of non-negative real numbers by @math By construction, and the above result, this is a non-increasing sequence with limit @math . We study this sequence and its rates of decay with @math . We also identify a precise relationship between the sequence and the first Vietoris-Rips persistence barcode of @math . Furthermore, we specifically analyze @math and find upper and lower bounds based on hyperbolicity and other metric invariants. As a consequence of the tools we develop, our work also provides a Gromov-Hausdorff stability result for the Reeb construction on geodesic metric spaces with respect to the function given by distance to a reference point. Clustering problems are well-studied in a variety of fields such as data science, operations research, and computer science. Such problems include variants of centre location problems, @math -median, and @math -means to name a few. In some cases, not all data points need to be clustered; some may be discarded for various reasons. We study clustering problems with outliers. More specifically, we look at Uncapacitated Facility Location (UFL), @math -Median, and @math -Means. In UFL with outliers, we have to open some centres, discard up to @math points of @math and assign every other point to the nearest open centre, minimizing the total assignment cost plus centre opening costs. In @math -Median and @math -Means, we have to open up to @math centres but there are no opening costs. In @math -Means, the cost of assigning @math to @math is @math . We present several results. Our main focus is on cases where @math is a doubling metric or is the shortest path metrics of graphs from a minor-closed family of graphs. For uniform-cost UFL with outliers on such metrics we show that a multiswap simple local search heuristic yields a PTAS. With a bit more work, we extend this to bicriteria approximations for the @math -Median and @math -Means problems in the same metrics where, for any constant @math , we can find a solution using @math centres whose cost is at most a @math -factor of the optimum and uses at most @math outliers. We also show that natural local search heuristics that do not violate the number of clusters and outliers for @math -Median (or @math -Means) will have unbounded gap even in Euclidean metrics. Furthermore, we show how our analysis can be extended to general metrics for @math -Means with outliers to obtain a @math bicriteria. The traveling salesman problem (TSP) is a canonical NP-complete problem which is proved by Trevisan [SIAM J. Comput., 30 (2000), pp. 475--485] to be MAX-SNP hard even on high-dimensional Euclidean metrics. To circumvent this hardness, researchers have been developing approximation schemes for „simpler” instances of the problem. For instance, the algorithms of Arora and of Talwar show how to approximate TSP on low-dimensional metrics (for different notions of metric dimension). However, a feature of most current notions of metric dimension is that they are „local”: the definitions require every local neighborhood to be well-behaved. In this paper, we define a global notion of dimension that generalizes the popular notion of doubling dimension, but still allows some small dense regions; e.g., it allows some metrics that contain cliques of size @math . Given a metric with global dimension @math , we give a @math -approximation algorithm that runs in subexponential time, i.e., in $ (O(n^... In a document network such as a citation network of scientific documents, web-logs, etc., the content produced by authors exhibits their interest in certain topics. In addition some authors influence other authors' interests. In this work, we propose to model the influence of cited authors along with the interests of citing authors. Moreover, we hypothesize that apart from the citations present in documents, the context surrounding the citation mention provides extra topical information about the cited authors. However, associating terms in the context to the cited authors remains an open problem. We propose novel document generation schemes that incorporate the context while simultaneously modeling the interests of citing authors and influence of the cited authors. Our experiments show significant improvements over baseline models for various evaluation criteria such as link prediction between document and cited author, and quantitatively explaining unseen text. The Johnson--Lindenstrauss lemma shows that any n points in Euclidean space (i.e., ℝn with distances measured under the e 2 norm) may be mapped down to O((log n) e2) dimensions such that no pairwise distance is distorted by more than a (1 p e) factor. Determining whether such dimension reduction is possible in e 1 has been an intriguing open question. We show strong lower bounds for general dimension reduction in e 1 . We give an explicit family of n points in e 1 such that any embedding with constant distortion D requires nΩ(1 D2) dimensions. This proves that there is no analog of the Johnson--Lindenstrauss lemma for e 1 ; in fact, embedding with any constant distortion requires nΩ(1) dimensions. Further, embedding the points into e 1 with (1pe) distortion requires nh−O(e log(1 e)) dimensions. Our proof establishes this lower bound for shortest path metrics of series-parallel graphs. We make extensive use of linear programming and duality in devising our bounds. We expect that the tools and techniques we develop will be useful for future investigations of embeddings into e 1 . Oliveira conjectured that the order of the mixing time of the exclusion process with @math -particles on an arbitrary @math -vertex graph is at most that of the mixing-time of @math independent particles. We verify this up to a constant factor for @math -regular graphs when each edge rings at rate @math in various cases: (1) when @math or (2) when @math the spectral-gap of a single walk is @math and @math or (3) when @math for some constant @math . In these cases our analysis yields a probabilistic proof of a weaker version of Aldous' famous spectral-gap conjecture (resolved by ). We also prove a general bound which is at worst @math , which is within a @math factor from Oliveira's conjecture when @math . As applications we get new mixing bounds: (a) @math for expanders, (b) order @math for the hypercube @math and (c) order @math for vertex-transitive graphs of moderate growth and for supercritical percolation on a fixed dimensional torus. Abstract Documents in computer-readable form can be used to provide information about other documents, i.e. those they cite. To do this efficiently requires procedures for computer recognition of citing statements. This is not easy, especially for multi-sentence citing statements. Computer recognition procedures have been developed which are accurate to the following extent: 73 of the words in statements selected by computer procedures as being citing statements are words which are correctly attributable to the corresponding documents. The retrieval effectiveness of computer-recognized citing statements was tested in the following way. First, for eight retrieval requests in inorganiic chemistry, average recall by search of Chemical Abstracts Service indexing and Chemical Abstracts abstract text words was found to be 50 . Words from citing statements referring to the papers to be retrieved were then added to the index terms and abstract words as additional access points, and searching was repeated. Average recall increased to 70 . Only words from citing statements published within a year of the cited papers were used. The retrieval effect of citing statement words alone (published within a year) without index or abstract terms was the following: average recall was 40 . When just the words of the titles of the cited papers were added to those citing statement words, average recall increased to 50 .