Uniform Universal Sets, Splitters, and Bisectors
E Burjons, P Rossmanith - arXiv preprint arXiv:2505.08308, 2025 - arxiv.org
E Burjons, P Rossmanith
arXiv preprint arXiv:2505.08308, 2025•arxiv.orgGiven a subset of size $ k $ of a very large universe a randomized way to find this subset
could consist of deleting half of the universe and then searching the remaining part. With a
probability of $2^{-k} $ one will succeed. By probability amplification, a randomized
algorithm needs about $2^ k $ rounds until it succeeds. We construct bisectors that
derandomize this process and have size~ $2^{k+ o (k)} $. One application is
derandomization of reductions between average case complexity classes. We also construct …
could consist of deleting half of the universe and then searching the remaining part. With a
probability of $2^{-k} $ one will succeed. By probability amplification, a randomized
algorithm needs about $2^ k $ rounds until it succeeds. We construct bisectors that
derandomize this process and have size~ $2^{k+ o (k)} $. One application is
derandomization of reductions between average case complexity classes. We also construct …
Given a subset of size of a very large universe a randomized way to find this subset could consist of deleting half of the universe and then searching the remaining part. With a probability of one will succeed. By probability amplification, a randomized algorithm needs about rounds until it succeeds. We construct bisectors that derandomize this process and have size~. One application is derandomization of reductions between average case complexity classes. We also construct uniform -universal sets that generalize universal sets in such a way that they are bisectors at the same time. This construction needs only linear time and produces families of asymptotically optimal size without using advanced combinatorial constructions as subroutines, which previous families did, but are basedmainly on modulo functions and refined brute force search.
arxiv.org