Parallel Play Saves Quantifiers
<|reference_start|>Parallel Play Saves Quantifiers: The number of quantifiers needed to express first-order properties is captured by two-player combinatorial games called multi-structural (MS) games. We play these games on linear orders and strings, and introduce a technique we call "parallel play", that dramatically reduces the number of quantifiers needed in many cases. Linear orders and strings are the most basic representatives of ordered structures -- a class of structures that has historically been notoriously difficult to analyze. Yet, in this paper, we provide upper bounds on the number of quantifiers needed to characterize different-sized subsets of these structures, and prove that they are tight up to constant factors, including, in some cases, up to a factor of $1+\varepsilon$, for arbitrarily small $\varepsilon$.<|reference_end|>
@article{carmosino2024parallel,
    title={Parallel Play Saves Quantifiers},
    author={Marco Carmosino, Ronald Fagin, Neil Immerman, Phokion Kolaitis,
  Jonathan Lenchner, Rik Sengupta, and Ryan Williams},
    journal={arXiv preprint arXiv:2402.10293},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.10293},
    primaryClass={cs.LO cs.CC}
}