Hypergraph Samplers: Typical and Worst Case Behavior
arXiv:2601.20039v1 Announce Type: new Abstract: 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. […]