Uniform Universal Sets, Splitters, and Bisectors
Elisabet Burjons, Peter Rossmanith · 2025
Read Uniform Universal Sets, Splitters, and Bisectors by Elisabet Burjons, Peter Rossmanith (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-2505-08308.txt.
Description
Elisabet Burjons and Peter Rossmanith wrote a computer science paper in two thousand twenty-five on tools for finding small hidden sets in huge universes. A random method halves the universe again and again; a given small set survives each halving with a tiny chance, so many rounds are needed. The authors build deterministic stand-ins called bisectors that mimic the halving.
Their bisectors reach near-optimal size, with one use in removing randomness from reductions between problem classes. They also build uniform universal sets that double as bisectors. The construction runs in linear time using mainly modular arithmetic and refined brute-force search.
Catalog record
| CREATOR | Elisabet Burjons, Peter Rossmanith |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-08308