Maximal Palindromes in MPC: Simple and Optimal
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 \(\mathcal{O}(1)\) rounds using \(\widetilde{\mathcal O}(n)\) total memory, with \(\widetilde{\mathcal O}(n^{1-\epsilon})\) memory per machine, for any \(\epsilon \in (0,0.5]\).
Fields of Study & Subjects
Algorithms and Data Compression
DNA and Biological Computing
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 431–437
- Publication date
- 1 January 2026
- Language
- EN