Finite Volume Spaces and Sparsification

Understand

We introduce and study finite $d$-volumes - the high dimensional generalization of finite metric spaces.

• Having developed a suitable combinatorial machinery, we define $\ell_1$-volumes and show that they contain Euclidean volumes and hypertree volumes.
• We show that they can approximate any $d$-volume with $O(n^d)$ multiplicative distortion.
• On the other hand, contrary to Bourgain's theorem for $d=1$, there exists a $2$-volume that on $n$ vertices that cannot be approximated by any $\ell_1$-volume with distortion smaller than $\tilde{\Omega}(n^{1/5})$.