Embedding Probability Distributions into Low Dimensional ${\ell }_1$: Tree Ising Models via Truncated Metrics

Moses Charikar, Spencer Compton, Chirag Pabbaraju

Given an arbitrary set of high dimensional points in ${\ell }_1$, there are known negative results that preclude the possibility of always mapping them to a low dimensional ${\ell }_1$ s…