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

CREATORElisabet Burjons, Peter Rossmanith
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE72 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-08308

Browse the full library · About the Tower of Babel