Hypergraph Samplers: Typical and Worst Case Behavior
Vedat Levi Alev, Uriya A. First · 2026
Read Hypergraph Samplers: Typical and Worst Case Behavior by Vedat Levi Alev, Uriya A. First (2026) 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-2601-20039.txt.
Introduction
Vedat Levi Alev and Uriya A. First study hypergraph samplers, a tool for cutting the error of randomized algorithms. The setup uses uniform hypergraphs whose number of vertices is not too large compared with the edge size. Samplers let an algorithm repeat a weak test in a structured way so that the overall error drops.
The authors examine both typical and worst-case behavior of these samplers. The question covers decision problems with one-sided or two-sided error. Knowing where samplers help, and where they fail, guides the design of fast randomized methods in computer science theory.
Catalog record
| CREATOR | Vedat Levi Alev, Uriya A. First |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 202 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-20039