Exact Depth-Two and Large-Depth Guarantees for Recursive Rejection Sampling
Proves the optimized uniform/dead binary witness is strictly suboptimal for every fixed draft count at sufficiently large depth. A subtree deletion improves it by an explicitly bounded exponential amount.
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-17
- DOI
- https://doi.org/10.5281/zenodo.24329448
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- preprint