Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.08308 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910941329752064 |
|---|---|
| author | Burjons, Elisabet Rossmanith, Peter |
| author_facet | Burjons, Elisabet Rossmanith, Peter |
| contents | Given 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 uniform $(n,k)$-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_08308 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Uniform Universal Sets, Splitters, and Bisectors Burjons, Elisabet Rossmanith, Peter Data Structures and Algorithms Information Theory Given 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 uniform $(n,k)$-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. |
| title | Uniform Universal Sets, Splitters, and Bisectors |
| topic | Data Structures and Algorithms Information Theory |
| url | https://arxiv.org/abs/2505.08308 |