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

CREATORKeren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE275 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-21655

Browse the full library · About the Tower of Babel