Maximal Palindromes in MPC: Simple and Optimal
Speaker: Solon Pissis (CWI)
Abstract:
In the classical longest palindromic substring (LPS) problem, we are given a string S of length n, and the task is to output a longest palindromic substring in S. Gilbert, Hajiaghayi, Saleh, and Seddighin [SPAA 2023] showed how to solve the LPS problem in the Massively Parallel Computation (MPC) model in O(1) rounds using O(n polylog(n)) total memory, with O(n^{1-ε}) memory per machine, for any ε in (0,0.5].
We will present a simple and optimal algorithm to solve the LPS problem in the MPC model in O(1) rounds. The total time and memory are O(n), with O(n^{1-ε}) memory per machine, for any ε in (0,0.5]. A key attribute of our algorithm is its ability to compute all maximal palindromes in the same complexities. Both our algorithm and the one proposed by Gilbert et al. for the LPS problem are randomized and succeed with high probability.
The talk is based on the paper: https://arxiv.org/abs/2511.13014 [SOSA 2026]
