Witness-Sensitive Detection of Induced Diamonds

Keren Censor-Hillel, Tomer Even, Virginia Vasillevska Williams, Nathan Wallheimer · 2026

Read Witness-Sensitive Detection of Induced Diamonds by Keren Censor-Hillel, Tomer Even, Virginia Vasillevska Williams, Nathan Wallheimer (2026) 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-2605-09006.txt.

Introduction

Keren Censor-Hillel, Tomer Even, Virginia Vasillevska Williams, and Nathan Wallheimer present a faster way to find a small pattern called an induced diamond inside a large graph. A diamond is a group of four linked points with one link missing. Their 2026 paper makes the running time depend on how many such patterns the graph contains, so graphs rich in diamonds are searched faster than before.

The key idea sorts diamonds by the size of the tight group of points that holds one of their triangles. Heavy and light cases get different search methods, and a new sampling scheme adapts to the graph at hand. The same sampling idea also speeds up two related problems, a sum problem and a special case of finding four-cycles.

Catalog record

CREATORKeren Censor-Hillel, Tomer Even, Virginia Vasillevska Williams, Nathan Wallheimer
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE209 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.09006

Browse the full library · About the Tower of Babel