# CSAIL Event Calendar: Previous Series

 Talk: On Multiplicative Approximations and Some Geometric ApplicationsSpeaker: Ilan Newman , University of HaifaDate: August 14 2012 Time: 2:00PM to 3:00PM Location: 32-G449 (kiva)Host: Ronitt Rubinfeld, MITContact: Joanne Hanley, 3-6054, joanne@csail.mit.eduRelevant URL: Abstract: Let $F$ be a set system over an underlying finite set $X$, and let $\mu$ be a measure on $X$, inducing to a measure on $F$: $\mu(S)=\sum_{x\in S} \mu(x)$. A measure $\mu^*$ on $X$ is a {\em multiplicative ${\lambda}$-approximation} of $\mu$ if for every $S\in F$ $\mu(S) \leq \mu^*(S) \leq (1+\epsilon) \mu(S)$. The central question raised in this work is about the existence of meaningful structural properties of $F$ implying that for any $\mu$ on $X$ there exists an ${{1+\epsilon}$-approximation $\mu^*$ that is supported on a small subset of $X$. It turns out that the parameter that governs the support size of a multiplicative approximation is the {\em triangular rank} of $F$. It is defined as the maximal length of a sequence of sets $S_1, \ldots ,S_t$ in $F$ such that $S_i \not\subseteq \cup_{ji=2,...,t$. We show that for any $\mu$ on $X$ and $0<\epsilon<1$, there is measure $\mu^*$ that ${{1+\epsilon}$-approximates $\mu$ and has support of size $O(\trk(F) \cdot \vcdim(F)/ \epsilon^2)$, where $\vcdim(F)$ and $trk(F)$ are the VC-dimension and triangular rank of $F$ respectively (and the later upper-bounds the former). We also present some alternative constructions which in some cases improve upon this bound. Conversely, we show that for any $\epsilon < 1$ there exists a $\mu$ on $X$ that cannot be ${{1+\epsilon}$-approximated by any $\mu^*$ with support smaller than $\trk(F)$. As an application we show a new dimension-reduction result for $\ell_1$ metrics: Any $\ell_1$-metric on $n$ points can be (efficiently) embedded with ${{1+\epsilon}$-distortion into $\R^{O(n/\epsilon^2)}$ equipped with the $\ell_1$ norm. This improves over the best previously known bound of $O(n \log n /\poly(\epsilon))$ on dimension, due to Schechtman. This is a joint work with Yuri Rabinovich.See other events that are part of See other events happening in August 2012