CCF-BSF: AF: Small: Metric Embeddings and Partitioning for Minor-Closed Graph Families

Ini the first year of the project, together with Kunal Talwar and Cyril Gaviolle, we refined our joined STOC paper on padded decomposition for minor free graphs, establishing the result also for bounded pathwidth graphs, and published it in SICOMP, on of the top TCS journals.

In the second year of the project, together with my graduate student Arnold Filtser, we wrote a paper that was accepted to STOC 2018, about embedding metrics with bounded shortest path decompositions (SPD) into normed spaces. In particular, we show that every graph of pathwidth k embeds into l1 with distortion establishing one of our research goals.

In Addition, Arnold Filtser also obtained a O(log distortion for the Steiner Point Removal (SPR) problem in general graphs, it was recently published in SODA 2018.

Each of the PI also worked on related problems in metric embedding and graph algorithms, e. g. I had several results with Michael Elking and Arnold Filtser on hopsets, spanners in high dimensional norms, and routing, that were published in PODc, ESA, SODA, etc.