3 papers
cs.DS2025
Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate -clique counts faster
Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams
Dell, Lapinskas and Meeks [DLM SICOMP 2022] presented a general reduction from approximate counting to decision for a class of fine-grained problems that can be viewed as hyperedge…
cs.DC2025
When MIS and Maximal Matching are Easy in the Congested Clique
Keren Censor-Hillel, Tomer Even, Maxime Flin +1
Two of the most fundamental distributed symmetry-breaking problems are that of finding a maximal independent set (MIS) and a maximal matching (MM) in a graph. It is a major open qu…
cs.DS2024
Fast Approximate Counting of Cycles
Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams
We consider the problem of approximate counting of triangles and longer fixed length cycles in directed graphs. For triangles, Tětek [ICALP'22] gave an algorithm that returns a $(1…