{"id":"arxiv/2601.20039","url":"https://arxiv.org/abs/2601.20039","tags":["cs.DS","cs.CC","math.CO"],"score":0,"title":"Hypergraph Samplers: Typical and Worst Case Behavior","domain":"cs.DS","source":"arxiv","authors":["Vedat Levi Alev","Uriya A. First"],"reviews":0,"subject":"cs.DS","summary":"We study the utility and limitations of using $k$-uniform hypergraphs $H = ([n], E)$ ($n \\ge \\mathrm{poly}(k)$) in the context of error reduction for randomized algorithms for decision problems with one- or two-sided error. Our error reduction idea is sampling a uniformly random hyperedge of $H$, and repeating the algorithm $k$ times using the hyperedge vertices as seeds. This is a general paradigm, which captures every pseudorandom method generating $k$ seeds without repetition. We show two results which imply a gap between the typical and the worst-case behavior of using $H$ for…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-01-27","reactions":{}}