15 września 2026 09:45
[Seminarium ZOK] Kyungjin Cho: Deterministic Distance Approximation in MPC via Improved Hitting Sets
Random sampling is a fundamental ingredient in many fast parallel
graph algorithms. In particular, several recent algorithms for graph
distance approximation use random samples to select a small set of
representative vertices, which are then used to build sparse
structures such as graph spanners or approximate shortest-path data
structures. While these sampling steps are simple and highly
parallelizable, obtaining comparable guarantees deterministically is
much less straightforward.
In this talk, I will discuss how such random sampling procedures can
be replaced by deterministic ones in the Massively Parallel
Computation (MPC) model. I will first introduce the MPC model and
illustrate the role of random sampling through a simple dominating-set
example. I will then explain the main derandomization ideas, based on
the conditional expectation method and limited independence.
These techniques yield the first deterministic sublogarithmic-round
MPC algorithms for several distance-approximation problems, with round
complexities essentially matching those of the corresponding
randomized algorithms.
Joint work with Michal Dory, Yannic Maus and Tijn de Vos.
Presented at SPAA 2026.