More Like this

1. Fast Approximate Counting of Cycles

   https://doi.org/10.4230/LIPIcs.ICALP.2024.37  

   Censor-Hillel, Keren; Even, Tomer; Vassilevska_Williams, Virginia (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bringmann, Karl; Grohe, Martin; Puppis, Gabriele; Svensson, Ola (Ed.)

   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±ε)-approximation in Õ(n^ω/t^{ω-2}) time, where t is the unknown number of triangles in the given n node graph and ω < 2.372 is the matrix multiplication exponent. We obtain an improved algorithm whose running time is, within polylogarithmic factors the same as that for multiplying an n× n/t matrix by an n/t × n matrix. We then extend our framework to obtain the first nontrivial (1± ε)-approximation algorithms for the number of h-cycles in a graph, for any constant h ≥ 3. Our running time is Õ(MM(n,n/t^{1/(h-2)},n)), the time to multiply n × n/(t^{1/(h-2)}) by n/(t^{1/(h-2)) × n matrices. Finally, we show that under popular fine-grained hypotheses, this running time is optimal. 

   more » « less
2. Witness-Sensitive Detection of Induced Diamonds

   https://doi.org/10.4230/lipics.icalp.2026.52  

   Censor-Hillel, Keren; Even, Tomer; Vassilevska_Williams, Virginia; Wallheimer, Nathan (July 2026, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Bhattacharya, Sayan; Nanongkai, Danupon; Benedikt, Michael; Puppis, Gabriele (Ed.)

   Abstract: We provide a fast witness-sensitive algorithm for detecting an induced diamond (a K₄ minus an edge) in an n-vertex graph containing t induced diamonds. Our algorithm runs in time Õ(min(n^2.425/t^0.25 + n², n^ω)) with high probability, improving upon the prior state of the art (witness-oblivious) algorithm that runs in time O(n^ω log n) [Vassilevska Williams, Wang, Williams, Yu, SODA 2014] whenever t ≥ n^{(3-ω)/3}, where ω < 2.372 is the matrix multiplication exponent. Our key insight is that the size of a clique containing one of the triangles of an induced diamond plays a crucial role in detecting such a diamond. We say that a diamond is r-heavy if this size is at least r, and we provide a fast detection algorithm for r-heavy diamonds in Õ(r⋅(n/r)^ω + (n/r)³+ nr) time. When there are no r-heavy diamonds, we provide a different fast detection algorithm in Õ(MM(n,n,n√{r/t})) time, where MM(a,b,c) denotes the time to multiply an a × b matrix by a b × c matrix, which is conditionally optimal for r = Õ(1). Our main technical contribution is in designing a refinement framework for sampling vectors, which allows sampling vertices for detecting diamonds in a manner that is adaptive to the structure of graphs with no r-heavy diamonds. We establish that our technique is of a wide applicability, by showing how it also allows for faster witness-sensitive algorithms for 4-SUM and for a special case of 4-cycles. 

   more » « less
3. Efficient Catalytic Graph Algorithms

   Cook, James; Pyne, Edward (January 2026, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026))

   We give fast, simple, and implementable catalytic logspace algorithms for two fundamental graph problems. First, a randomized catalytic algorithm for s → t connectivity running in Õ(nm) time, and a deterministic catalytic algorithm for the same running in Õ(n³ m) time. The former algorithm is the first algorithmic use of randomization in CL. The algorithm uses one register per vertex and repeatedly "pushes" values along the edges in the graph. Second, a deterministic catalytic algorithm for simulating random walks which in Õ(m T² / ε) time estimates the probability a T-step random walk ends at a given vertex within ε additive error. The algorithm uses one register for each vertex and increments it at each visit to ensure repeated visits follow different outgoing edges. Prior catalytic algorithms for both problems did not have explicit runtime bounds beyond being polynomial in n. 

   more » « less
4. Space Complexity of Minimum Cut Problems in Single-Pass Streams

   https://doi.org/10.4230/LIPIcs.ITCS.2025.43  

   Ding, Matthew; Garces, Alexandro; Li, Jason; Lin, Honghao; Nelson, Jelani; Shah, Vihan; Woodruff, David P (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   We consider the problem of finding a minimum cut of a weighted graph presented as a single-pass stream. While graph sparsification in streams has been intensively studied, the specific application of finding minimum cuts in streams is less well-studied. To this end, we show upper and lower bounds on minimum cut problems in insertion-only streams for a variety of settings, including for both randomized and deterministic algorithms, for both arbitrary and random order streams, and for both approximate and exact algorithms. One of our main results is an Õ(n/ε) space algorithm with fast update time for approximating a spectral cut query with high probability on a stream given in an arbitrary order. Our result breaks the Ω(n/ε²) space lower bound required of a sparsifier that approximates all cuts simultaneously. Using this result, we provide streaming algorithms with near optimal space of Õ(n/ε) for minimum cut and approximate all-pairs effective resistances, with matching space lower-bounds. The amortized update time of our algorithms is Õ(1), provided that the number of edges in the input graph is at least (n/ε²)^{1+o(1)}. We also give a generic way of incorporating sketching into a recursive contraction algorithm to improve the post-processing time of our algorithms. In addition to these results, we give a random-order streaming algorithm that computes the exact minimum cut on a simple, unweighted graph using Õ(n) space. Finally, we give an Ω(n/ε²) space lower bound for deterministic minimum cut algorithms which matches the best-known upper bound up to polylogarithmic factors. 

   more » « less
5. Adversarially Robust Coloring for Graph Streams

   Chakrabarti, Amit; Ghosh, Prantar; Stoeckl, Manuel (January 2022, Leibniz international proceedings in informatics)

   A streaming algorithm is considered to be adversarially robust if it provides correct outputs with high probability even when the stream updates are chosen by an adversary who may observe and react to the past outputs of the algorithm. We grow the burgeoning body of work on such algorithms in a new direction by studying robust algorithms for the problem of maintaining a valid vertex coloring of an n-vertex graph given as a stream of edges. Following standard practice, we focus on graphs with maximum degree at most Δ and aim for colorings using a small number f(Δ) of colors. A recent breakthrough (Assadi, Chen, and Khanna; SODA 2019) shows that in the standard, non-robust, streaming setting, (Δ+1)-colorings can be obtained while using only Õ(n) space. Here, we prove that an adversarially robust algorithm running under a similar space bound must spend almost Ω(Δ²) colors and that robust O(Δ)-coloring requires a linear amount of space, namely Ω(nΔ). We in fact obtain a more general lower bound, trading off the space usage against the number of colors used. From a complexity-theoretic standpoint, these lower bounds provide (i) the first significant separation between adversarially robust algorithms and ordinary randomized algorithms for a natural problem on insertion-only streams and (ii) the first significant separation between randomized and deterministic coloring algorithms for graph streams, since deterministic streaming algorithms are automatically robust. We complement our lower bounds with a suite of positive results, giving adversarially robust coloring algorithms using sublinear space. In particular, we can maintain an O(Δ²)-coloring using Õ(n √Δ) space and an O(Δ³)-coloring using Õ(n) space. 

   more » « less