Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate k k -clique counts faster
Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams · 2025
Read Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate k k -clique counts faster by Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams (2025) 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-2503-21655.txt.
Introduction
Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams speed up approximate counting for problems like counting k-cliques in a graph. Their 2025 paper builds on a known reduction that turns counting into a few calls to an oracle that only answers whether a small piece of an implicit hypergraph holds an edge. The new version is output sensitive: its running time shrinks as the true count grows.
The oracle is now called only on pieces of small measure. By building such oracles for colorful independence sets, the team gets faster counting for k-clique, k-dominating set, and k-sum. For graphs dense in cliques the gain over prior work is substantial, even under optimistic matrix multiplication bounds.
Catalog record
| CREATOR | Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 275 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-21655