Fast approximate counting of cycles

DOI10.4230/LIPICS.ICALP.2024.37MaRDI QIDQ6875169zbMATH OpenFDO

Authors Keren Censor-Hillel, Tomer Even, Virginia Vassilevska Williams

Publication date 14 January 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2024.37

zbMATH Keywords

fast rectangular matrix multiplicationapproximate triangle countingapproximate cycle counting fast matrix multiplication

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 2119719 (Why is no real title available?)
• Almost optimal bounds for sublinear-time sampling of k-cliques in bounded arboricity graphs
• Approximate triangle counting via sampling and fast matrix multiplication
• Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle
• Approximately counting triangles in sublinear time
• Clique-based lower bounds for parsing tree-adjoining grammars
• Color-coding
• Computing and Combinatorics
• Counting arbitrary subgraphs in data streams
• Counting stars and other small subgraphs in sublinear-time
• Counting triangles in massive graphs with MapReduce
• Detecting cliques in CONGEST networks
• Detecting short directed cycles using rectangular matrix multiplication and dynamic programming
• Deterministic Near-Optimal Distributed Listing of Cliques
• Deterministic distributed expander decomposition and routing with applications in distributed derandomization
• Finding Even Cycles Even Faster
• Finding and counting given length cycles
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• If the current clique algorithms are optimal, so is Valiant's parser
• Listing triangles
• Massively parallel algorithms for small subgraph counting
• Near-optimal Distributed Triangle Enumeration via Expander Decompositions
• New bounds for matrix multiplication: from alpha to omega
• On approximating the number of k-cliques in sublinear time
• Sparse matrix multiplication and triangle listing in the congested clique model
• Subcubic equivalences between path, matrix, and triangle problems
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Towards polynomial lower bounds for dynamic problems
• Triangle Finding and Listing in CONGEST Networks
• ``Tri, tri again: finding triangles and small subgraphs in a distributed setting (extended abstract)

This page was built for publication: Fast approximate counting of cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875169)