Date:
Mon, 18/06/2018
Location:
Eilat Hall, Feldman Building, Givat Ram
Special day on sparsification
Speakers: Ilan Newman and Yuri Rabinovich.
Part I: 10:30 - 12:30
Part II: 14:00 - 15:50
Abstract for the day:
Time permitting, we plan to discuss the following topics (in this order):
1.
* Additive Sparsification and VC dimension
* Multiplicative Sparsification
* Examples: cut weights, cut-dimension of L_1 metrics, general metrics,
and their high-dimensional analogues
2.
* Multiplicative Sparsification and Triangular Rank;
* Karger-Benczur sparsification of cuts weights
3.
* Batson-Spielman-Srivastava sparsification
* L_1 dimension reduction
4.
* Higher dimensional implications of [BSS]
* (?) Higher dimensional spanners