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

CREATORVedat Levi Alev, Uriya A. First
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE202 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-20039

Browse the full library · About the Tower of Babel