BIU theory seminar 2025-2026 Kickoff - Wednesday Oct 29: Arnold Filtser (BIU) - How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs.
Arnold Filtser
Dear friends and colleagues,
We are excited to begin another year of our Theory Seminar!
The seminar will take place on Wednesdays at 12:00, in CS Building 503, Room 226.
We have an excellent lineup of speakers this semester and look forward to many exciting talks.
You can find the list of speakers and additional information on the seminar webpage: https://theory.cs.biu.ac.il/
To receive future updates about the seminar, please join our mailing list (Google Group): https://groups.google.com/a/cs.biu.ac.il/g/biu-theory-seminar
You can also add the seminar schedule to your calendar, including all upcoming talks: Google Calendar link
I will give the first talk of the semester on October 29 (next Wednesday at 12:00).
Details appear below.
Looking forward to seeing you all there!
Best regards,
Arnold
Speaker: Arnold Filtser (BIU)
Title: How to Protect Yourself from Threatening Skeletons: Optimal Padded Decompositions for Minor-Free Graphs.
Abstract: 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.
-minor-free graph has a padding parameter of  "O(\log r)")
(which is also tight). This resolves a long-standing open question and exponentially improves the previous bound.