Maximal Palindromes in MPC: Simple and Optimal

Solon P. Pissis · 2025

Read Maximal Palindromes in MPC: Simple and Optimal by Solon P. Pissis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-13014.txt.

Description

Solon P. Pissis finds every maximal palindrome in a huge string, in parallel, with a simpler algorithm than the problem previously had. A palindrome reads the same backward and forward. The longest palindromic substring problem asks for the longest one hidden in a string, a task with uses from text processing to genome analysis. In the massively parallel computation model, where many machines each hold a slice of memory, an earlier team solved it in a constant number of rounds with near-linear total memory.

Pissis matches those bounds with linear total time and memory, and the same procedure also returns all maximal palindromes at no extra cost. His insights also remove a restriction on per-machine memory in the adaptive variant of the model. The algorithms are randomized and succeed with high probability. Simplicity matters here: a cleaner parallel algorithm is easier to implement correctly on real clusters.

Catalog record

CREATORSolon P. Pissis
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-13014

Browse the full library · About the Tower of Babel