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
| CREATOR | Solon P. Pissis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 25 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-13014