אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

A metric space has padding parameter   if, roughly, for any scale  , it admits a stochastic decomposition into clusters of diameter at most  , such that any ball of radius   is contained within a single cluster with probability at least  . The padding parameter is an important characteristic of metric spaces with vast algorithmic implications.
This talk will begin by surveying different classic constructions of padded decompositions. We will then discuss the main ideas in our recent proof that the shortest path metric of every  -minor-free graph has a padding parameter of   (which is also tight). This resolves a long-standing open question and exponentially improves the previous bound.

A joint work with Jonathan Conroy.