HD-Combinatorics: Special day on sparsification (by Ilan Newman and Yuri Rabinovich)


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

Date: 

Mon, 18/06/2018 (All day)

Location: 

Eilat Hall, Feldman Building, Givat Ram