NDLI: Advances in metric embedding theory

Please wait, while we are loading the content...

Explicit capacity-achieving list-decodable codes

The Santa Claus problem

Reducibility among equilibrium problems

Black-box constructions for secure computation

The changing face of web search: algorithms, auctions and advertising

On the solution-space geometry of random constraint satisfaction problems

Time-space tradeoffs for implementations of snapshots

Near-optimal algorithms for unique games

Finding a maximum weight triangle in $n^{3-Δ}$ time, with applications

The PCP theorem by gap amplification

A combinatorial characterization of the testable graph properties: it's all about regularity

Zero knowledge with efficient provers

A quasi-polynomial time approximation scheme for minimum weight triangulation

Conditional hardness for approximate coloring

Can every randomized algorithm be derandomized?

Finding small balanced separators

Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications

Pseudorandom walks on regular digraphs and the RL vs. L problem

Online trading algorithms and robust option pricing

Extractors for a constant number of polynomially small min-entropy independent sources

Logarithmic hardness of the directed congestion minimization problem

Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform

Bounded-error quantum state identification and exponential separations in communication complexity

Truthful randomized mechanisms for combinatorial auctions

2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction

A quasi-PTAS for unsplittable flow on line graphs

Gowers uniformity, influence of variables, and PCPs

On maximizing welfare when utility functions are subadditive

The complexity of computing a Nash equilibrium

Information-theoretically secure protocols and security under composition

Counting independent sets up to the tree threshold

Byzantine agreement in the full-information model in O(log n) rounds

New approximation guarantee for chromatic number

Time-space trade-offs for predecessor search

Graph limits and parameter testing

Zero-knowledge against quantum attacks

Building triangulations using ε-nets

Clique-width minimization is NP-hard

Graph partitioning using single commodity flows

A polynomial quantum algorithm for approximating the Jones polynomial

An efficient algorithm for solving word equations

On adequate performance measures for paging

Narrow proofs may be spacious: separating space and width in resolution

Hardness of cut problems in directed graphs

On the importance of idempotence

Limitations of quantum coset states for graph isomorphism

Fast convergence to Wardrop equilibria by adaptive sampling methods

Linear degree extractors and the inapproximability of max clique and chromatic number

Minimizing average flow time on related machines

Sub-constant error low degree test of almost-linear size

A randomized polynomial-time simplex algorithm for linear programming

New trade-offs in cost-sharing mechanisms

Private approximation of search problems

The DLT priority sampling is essentially optimal

Fast leader-election protocols with bounded cheaters' edge

Advances in metric embedding theory

Local zero knowledge

The distance trisector curve

Hardness of approximate two-level logic minimization and PAC learning with membership queries

Linear time low tree-width partitions and algorithmic consequences

On the fourier tails of bounded functions over the discrete cube

Integrality gaps for sparsest cut and minimum linear arrangement problems

Searching dynamic point sets in spaces with bounded doubling dimension

A new quantum lower bound method,: with applications to direct product theorems and time-space tradeoffs

Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree

Deterministic extractors for small-space sources

Provably near-optimal sampling-based algorithms for Stochastic inventory control models

The effect of collusion in congestion games

Optimal phylogenetic reconstruction

Pricing for fairness: distributed resource allocation for multiple objectives

Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs

Lattice problems and norm embeddings

On earthmover distance, metric labeling, and 0-extension

Learning a circuit by injecting values

New upper and lower bounds for randomized and quantum local search

On basing one-way functions on NP-hardness

A subset spanner for Planar graphs, with application to subset TSP

On the randomness complexity of efficient sampling

Edge-disjoint paths in Planar graphs with constant congestion

Advances in metric embedding theory

Content Provider	ACM Digital Library
Author	Neimany, Ofer Bartal, Yair Abraham, Ittai
Abstract	Metric Embedding plays an important role in a vast range of application areas such as computer vision, computational biology, machine learning, networking, statistics, and mathematical psychology, to name a few.The theory of metric embedding received much attention in recent years by mathematicians as well as computer scientists and has been applied in many algorithmic applications.A cornerstone of the field is a celebrated theorem of Bourgain which states that every finite metric space on n points embeds in Euclidean space with O(log n) distortion.Bourgain's result is best possible when considering the worst case distortion over all pairs of points in the metric space. Yet, it is possible that an embedding can do much better in terms of the average distortion.Indeed, in most practical applications of metric embedding the main criteria for the quality of an embedding is its average distortion over all pairs.In this paper we provide an embedding with constant average distortion for arbitrary metric spaces, while maintaining the same worst case bound provided by Bourgain's theorem.In fact, our embedding possesses a much stronger property. We define the $l_{q}-distortion$ of a uniformly distributed pair of points. Our embedding achieves the best possible $l_{q}-distortion$ for all 1 ≤ q ≤ ∞ simultaneously.These results have several algorithmic implications, e.g. an O(1) approximation for the unweighted uncapacitated quadratic assignment problem.The results are based on novel embedding methods which improve on previous methods in another important aspect: the dimension.The dimension of an embedding is of very high importance in particular in applications and much effort has been invested in analyzing it. However, no previous result improved the bound on the dimension which can be derived from Bourgain's embedding.We prove that any metric space on n points embeds into $L_{p}$ with distortion O(log n) in dimension O(log n). This provides an optimal bound on the dimension of the embedding.Somewhat surprisingly, we show that a further small improvement is possible at a small price in the distortion, obtaining an embedding with distortion $O(log^{1+θ}$ n) in optimal dimension $O(θ^{-1}$ log n/log log n), for any θ > 0. It is worth noting that with the small loss in the distortion this improves upon the best known embedding of arbitrary spaces into Euclidean space, where dimension reduction is used.Our techniques also allow to obtain the optimal distortion for embedding into $L_{p}$ with nearly tight dimension. For any 1 ≤ p ≤ ⊂ and any 1 ≤ k ≤ p, we give an embedding into $L_{p}$ with distortion O(⌈ log n/k ⌉) in dimension $2^{O(k)}log$ n.Underlying our results is a novel embedding method. Probabilistic metric decomposition techniques have played a central role in the field of finite metric embedding in recent years. Here we introduce a novel notion of probabilistic metric decompositions which comes particularly natural in the context of embedding. Our new methodology provides a unified approach to all known results on embedding of arbitrary metric spaces. Moreover, as described above, with some additional ideas they allow to get far stronger results. These metric decompositions seem of independent interest.
Starting Page	271
Ending Page	286
Page Count	16
File Format	PDF
ISBN	1595931341
DOI	10.1145/1132516.1132557
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2006-05-21
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Metric embedding
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in