Hypergraph Samplers: Typical and Worst Case Behavior
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2601.20039
curl -X POST /api/v1/records/arxiv/2601.20039/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2601.20039/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'