SCShiri Chechik
Shiri Chechik
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Shiri Chechik has a total of 22 co-authors. Here are the top co-authors by number of shared publications:
- Doron Mukhtar
Tel Aviv University
4 shared publications - Tianyi Zhang
Tel Aviv University
2 shared publications - Aaron Sidford
Stanford University
1 shared publication - Davide Bilò
University of L'Aquila
1 shared publication - Doron Mukhtar
Tel Aviv University, Tel Aviv, Israel
1 shared publication - Gur Lifshitz
Tel Aviv University, Tel Aviv, Israel
1 shared publication
Latest Publications
- Open Access
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 14-24
Girth Approximations in the CONGEST Model
- 6 July 2026
- Published by Association for Computing Machinery (ACM)
- p. 14-24
Open AccessGirth Approximations in the CONGEST Model
- Open Access
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2249-2256
Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
- 15 June 2025
- Published by Association for Computing Machinery (ACM)
- p. 2249-2256
Open AccessÕptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
- Open Access
Improved Streaming Edge Coloring
Given a graph, an edge coloring assigns colors to edges so that no pairs of adjacent edges share the same color. We are interested in edge coloring algorithms under the W-streaming model. In this model, the algorithm does not have enough memory to hold the entire graph, so the edges of the input graph are read from a data stream one by one in an unknown order, and the algorithm needs to print a valid edge coloring in an output stream. The performance of the algorithm is measured by the amount of space and the number of different colors it uses. This streaming edge coloring problem has been studied by several works in recent years. When the input graph contains $n$ vertices and has maximum vertex degree $Δ$, it is known that in the W-streaming model, an $O(Δ^2)$-edge coloring can be computed deterministically with $\tilde{O}(n)$ space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an $O(Δ^{1.5})$-edge coloring can be computed by a $\tilde{O}(n)$-space randomized algorithm [Behnezhad, Saneian, 2024] [Chechik, Mukhtar, Zhang, 2024]. In this paper, we achieve polynomial improvement over previous results. Specifically, we show how to improve the number of colors to $\tilde{O}(Δ^{4/3+ε})$ using space $\tilde{O}(n)$ deterministically, for any constant $ε> 0$. This is the first deterministic result that bypasses the quadratic bound on the number of colors while using near-linear space.Open AccessImproved Streaming Edge Coloring
Given a graph, an edge coloring assigns colors to edges so that no pairs of adjacent edges share the same color. We are interested in edge coloring algorithms under the W-streaming model. In this model, the algorithm does not have enough memory to hold the entire graph, so the edges of the input graph are read from a data stream one by one in an unknown order, and the algorithm needs to print a valid edge coloring in an output stream. The performance of the algorithm is measured by the amount of space and the number of different colors it uses. This streaming edge coloring problem has been studied by several works in recent years. When the input graph contains $n$ vertices and has maximum vertex degree $Δ$, it is known that in the W-streaming model, an $O(Δ^2)$-edge coloring can be computed deterministically with $\tilde{O}(n)$ space [Ansari, Saneian, and Zarrabi-Zadeh, 2022], or an $O(Δ^{1.5})$-edge coloring can be computed by a $\tilde{O}(n)$-space randomized algorithm [Behnezhad, Saneian, 2024] [Chechik, Mukhtar, Zhang, 2024]. In this paper, we achieve polynomial improvement over previous results. Specifically, we show how to improve the number of colors to $\tilde{O}(Δ^{4/3+ε})$ using space $\tilde{O}(n)$ deterministically, for any constant $ε> 0$. This is the first deterministic result that bypasses the quadratic bound on the number of colors while using near-linear space. - Open Access
Faster Algorithms for Dual-Failure Replacement Paths
Given a simple weighted directed graph $G = (V, E, ω)$ on $n$ vertices as well as two designated terminals $s, t\in V$, our goal is to compute the shortest path from $s$ to $t$ avoiding any pair of presumably failed edges $f_1, f_2\in E$, which is a natural generalization of the classical replacement path problem which considers single edge failures only. This dual failure replacement paths problem was recently studied by Vassilevska Williams, Woldeghebriel and Xu [FOCS 2022] who designed a cubic time algorithm for general weighted digraphs which is conditionally optimal; in the same paper, for unweighted graphs where $ω\equiv 1$, the authors presented an algebraic algorithm with runtime $\tilde{O}(n^{2.9146})$, as well as a conditional lower bound of $n^{8/3-o(1)}$ against combinatorial algorithms. However, it was unknown in their work whether fast matrix multiplication is necessary for a subcubic runtime in unweighted digraphs. As our primary result, we present the first truly subcubic combinatorial algorithm for dual failure replacement paths in unweighted digraphs. Our runtime is $\tilde{O}(n^{3-1/18})$. Besides, we also study algebraic algorithms for digraphs with small integer edge weights from $\{-M, -M+1, \cdots, M-1, M\}$. As our secondary result, we obtained a runtime of $\tilde{O}(Mn^{2.8716})$, which is faster than the previous bound of $\tilde{O}(M^{2/3}n^{2.9144} + Mn^{2.8716})$ from [Vassilevska Williams, Woldeghebriela and Xu, 2022].Open AccessFaster Algorithms for Dual-Failure Replacement Paths
Given a simple weighted directed graph $G = (V, E, ω)$ on $n$ vertices as well as two designated terminals $s, t\in V$, our goal is to compute the shortest path from $s$ to $t$ avoiding any pair of presumably failed edges $f_1, f_2\in E$, which is a natural generalization of the classical replacement path problem which considers single edge failures only. This dual failure replacement paths problem was recently studied by Vassilevska Williams, Woldeghebriel and Xu [FOCS 2022] who designed a cubic time algorithm for general weighted digraphs which is conditionally optimal; in the same paper, for unweighted graphs where $ω\equiv 1$, the authors presented an algebraic algorithm with runtime $\tilde{O}(n^{2.9146})$, as well as a conditional lower bound of $n^{8/3-o(1)}$ against combinatorial algorithms. However, it was unknown in their work whether fast matrix multiplication is necessary for a subcubic runtime in unweighted digraphs. As our primary result, we present the first truly subcubic combinatorial algorithm for dual failure replacement paths in unweighted digraphs. Our runtime is $\tilde{O}(n^{3-1/18})$. Besides, we also study algebraic algorithms for digraphs with small integer edge weights from $\{-M, -M+1, \cdots, M-1, M\}$. As our secondary result, we obtained a runtime of $\tilde{O}(Mn^{2.8716})$, which is faster than the previous bound of $\tilde{O}(M^{2/3}n^{2.9144} + Mn^{2.8716})$ from [Vassilevska Williams, Woldeghebriela and Xu, 2022]. - Open Access
Streaming Edge Coloring with Subquadratic Palette Size
In this paper, we study the problem of computing an edge-coloring in the (one-pass) W-streaming model. In this setting, the edges of an $n$-node graph arrive in an arbitrary order to a machine with a relatively small space, and the goal is to design an algorithm that outputs, as a stream, a proper coloring of the edges using the fewest possible number of colors. Behnezhad et al. [Behnezhad et al., 2019] devised the first non-trivial algorithm for this problem, which computes in $\tilde{O}(n)$ space a proper $O(Δ^2)$-coloring w.h.p. (here $Δ$ is the maximum degree of the graph). Subsequent papers improved upon this result, where latest of them [Ansari et al., 2022] shows that it is possible to deterministically compute an $O(Δ^2/s)$-coloring in $O(ns)$ space. However, none of the improvements, succeeded in reducing the number of colors to $O(Δ^{2-ε})$ while keeping the same space bound of $\tilde{O}(n)$. In particular, no progress was made on the question of whether computing an $O(Δ)$-coloring is possible with roughly $O(n)$ space, which was stated in [Behnezhad et al., 2019] to be a major open problem. In this paper we bypass the quadratic bound by presenting a new randomized $\tilde{O}(n)$-space algorithm that uses $\tilde{O}(Δ^{1.5})$ colors.Open AccessStreaming Edge Coloring with Subquadratic Palette Size
In this paper, we study the problem of computing an edge-coloring in the (one-pass) W-streaming model. In this setting, the edges of an $n$-node graph arrive in an arbitrary order to a machine with a relatively small space, and the goal is to design an algorithm that outputs, as a stream, a proper coloring of the edges using the fewest possible number of colors. Behnezhad et al. [Behnezhad et al., 2019] devised the first non-trivial algorithm for this problem, which computes in $\tilde{O}(n)$ space a proper $O(Δ^2)$-coloring w.h.p. (here $Δ$ is the maximum degree of the graph). Subsequent papers improved upon this result, where latest of them [Ansari et al., 2022] shows that it is possible to deterministically compute an $O(Δ^2/s)$-coloring in $O(ns)$ space. However, none of the improvements, succeeded in reducing the number of colors to $O(Δ^{2-ε})$ while keeping the same space bound of $\tilde{O}(n)$. In particular, no progress was made on the question of whether computing an $O(Δ)$-coloring is possible with roughly $O(n)$ space, which was stated in [Behnezhad et al., 2019] to be a major open problem. In this paper we bypass the quadratic bound by presenting a new randomized $\tilde{O}(n)$-space algorithm that uses $\tilde{O}(Δ^{1.5})$ colors. - Open Access
Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
Despite extensive research on distance oracles, there are still large gaps between the best constructions for spanners and distance oracles. Notably, there exist sparse spanners with a multiplicative stretch of $1+\varepsilon$ plus some additive stretch. A fundamental open problem is whether such a bound is achievable for distance oracles as well. Specifically, can we construct a distance oracle with multiplicative stretch better than 2, along with some additive stretch, while maintaining subquadratic space complexity? This question remains a crucial area of investigation, and finding a positive answer would be a significant step forward for distance oracles. Indeed, such oracles have been constructed for sparse graphs. However, in the more general case of dense graphs, it is currently unknown whether such oracles exist. In this paper, we contribute to the field by presenting the first distance oracles that achieve a multiplicative stretch of $1+\varepsilon$ along with a small additive stretch while maintaining subquadratic space complexity. Our results represent an advancement particularly for constructing efficient distance oracles for dense graphs. In addition, we present a whole family of oracles that, for any positive integer $k$, achieve a multiplicative stretch of $2k-1+\varepsilon$ using $o(n^{1+1/k})$ space.Open AccessImproved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
Despite extensive research on distance oracles, there are still large gaps between the best constructions for spanners and distance oracles. Notably, there exist sparse spanners with a multiplicative stretch of $1+\varepsilon$ plus some additive stretch. A fundamental open problem is whether such a bound is achievable for distance oracles as well. Specifically, can we construct a distance oracle with multiplicative stretch better than 2, along with some additive stretch, while maintaining subquadratic space complexity? This question remains a crucial area of investigation, and finding a positive answer would be a significant step forward for distance oracles. Indeed, such oracles have been constructed for sparse graphs. However, in the more general case of dense graphs, it is currently unknown whether such oracles exist. In this paper, we contribute to the field by presenting the first distance oracles that achieve a multiplicative stretch of $1+\varepsilon$ along with a small additive stretch while maintaining subquadratic space complexity. Our results represent an advancement particularly for constructing efficient distance oracles for dense graphs. In addition, we present a whole family of oracles that, for any positive integer $k$, achieve a multiplicative stretch of $2k-1+\varepsilon$ using $o(n^{1+1/k})$ space. - 27 November 2021
- Published by Springer Nature in Distributed Computing
- Vol. 35 (4) , 357-374
Single-source shortest paths in the CONGEST model with improved bounds
- 27 November 2021
- Published by Springer Nature in Distributed Computing
- Vol. 35 (4) , 357-374
Single-source shortest paths in the CONGEST model with improved bounds
- Open Access
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
In the fully dynamic maximal independent set (MIS) problem our goal is to maintain an MIS in a given graph $G$ while edges are inserted and deleted from the graph. The first non-trivial algorithm for this problem was presented by Assadi, Onak, Schieber, and Solomon [STOC 2018] who obtained a deterministic fully dynamic MIS with $O(m^{3/4})$ update time. Later, this was independently improved by Du and Zhang and by Gupta and Khan [arXiv 2018] to $\tilde{O}(m^{2/3})$ update time. Du and Zhang [arXiv 2018] also presented a randomized algorithm against an oblivious adversary with $\tilde{O}(\sqrt{m})$ update time. The current state of art is by Assadi, Onak, Schieber, and Solomon [SODA 2019] who obtained randomized algorithms against oblivious adversary with $\tilde{O}(\sqrt{n})$ and $\tilde{O}(m^{1/3})$ update times. In this paper, we propose a dynamic randomized algorithm against oblivious adversary with expected worst-case update time of $O(\log^4n)$. As a direct corollary, one can apply the black-box reduction from a recent work by Bernstein, Forster, and Henzinger [SODA 2019] to achieve $O(\log^6n)$ worst-case update time with high probability. This is the first dynamic MIS algorithm with very fast update time of poly-log.Open AccessFully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
In the fully dynamic maximal independent set (MIS) problem our goal is to maintain an MIS in a given graph $G$ while edges are inserted and deleted from the graph. The first non-trivial algorithm for this problem was presented by Assadi, Onak, Schieber, and Solomon [STOC 2018] who obtained a deterministic fully dynamic MIS with $O(m^{3/4})$ update time. Later, this was independently improved by Du and Zhang and by Gupta and Khan [arXiv 2018] to $\tilde{O}(m^{2/3})$ update time. Du and Zhang [arXiv 2018] also presented a randomized algorithm against an oblivious adversary with $\tilde{O}(\sqrt{m})$ update time. The current state of art is by Assadi, Onak, Schieber, and Solomon [SODA 2019] who obtained randomized algorithms against oblivious adversary with $\tilde{O}(\sqrt{n})$ and $\tilde{O}(m^{1/3})$ update times. In this paper, we propose a dynamic randomized algorithm against oblivious adversary with expected worst-case update time of $O(\log^4n)$. As a direct corollary, one can apply the black-box reduction from a recent work by Bernstein, Forster, and Henzinger [SODA 2019] to achieve $O(\log^6n)$ worst-case update time with high probability. This is the first dynamic MIS algorithm with very fast update time of poly-log. - Open Access
Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem
In the Single Source Replacement Paths (SSRP) problem we are given a graph $G = (V, E)$, and a shortest paths tree $\widehat{K}$ rooted at a node $s$, and the goal is to output for every node $t \in V$ and for every edge $e$ in $\widehat{K}$ the length of the shortest path from $s$ to $t$ avoiding $e$. We present an $\tilde{O}(m\sqrt{n} + n^2)$ time randomized combinatorial algorithm for unweighted directed graphs. Previously such a bound was known in the directed case only for the seemingly easier problem of replacement path where both the source and the target nodes are fixed. Our new upper bound for this problem matches the existing conditional combinatorial lower bounds. Hence, (assuming these conditional lower bounds) our result is essentially optimal and completes the picture of the SSRP problem in the combinatorial setting. Our algorithm extends to the case of small, rational edge weights. We strengthen the existing conditional lower bounds in this case by showing that any $O(mn^{1/2-\epsilon})$ time (combinatorial or algebraic) algorithm for some fixed $\epsilon >0$ yields a truly subcubic algorithm for the weighted All Pairs Shortest Paths problem (previously such a bound was known only for the combinatorial setting).Open AccessNear Optimal Algorithm for the Directed Single Source Replacement Paths Problem
In the Single Source Replacement Paths (SSRP) problem we are given a graph $G = (V, E)$, and a shortest paths tree $\widehat{K}$ rooted at a node $s$, and the goal is to output for every node $t \in V$ and for every edge $e$ in $\widehat{K}$ the length of the shortest path from $s$ to $t$ avoiding $e$. We present an $\tilde{O}(m\sqrt{n} + n^2)$ time randomized combinatorial algorithm for unweighted directed graphs. Previously such a bound was known in the directed case only for the seemingly easier problem of replacement path where both the source and the target nodes are fixed. Our new upper bound for this problem matches the existing conditional combinatorial lower bounds. Hence, (assuming these conditional lower bounds) our result is essentially optimal and completes the picture of the SSRP problem in the combinatorial setting. Our algorithm extends to the case of small, rational edge weights. We strengthen the existing conditional lower bounds in this case by showing that any $O(mn^{1/2-\epsilon})$ time (combinatorial or algebraic) algorithm for some fixed $\epsilon >0$ yields a truly subcubic algorithm for the weighted All Pairs Shortest Paths problem (previously such a bound was known only for the combinatorial setting). - Open Access
Constant Girth Approximation for Directed Graphs in Subquadratic Time
In this paper we provide a $\tilde{O}(m\sqrt{n})$ time algorithm that computes a $3$-multiplicative approximation of the girth of a $n$-node $m$-edge directed graph with non-negative edge lengths. This is the first algorithm which approximates the girth of a directed graph up to a constant multiplicative factor faster than All-Pairs Shortest Paths (APSP) time, i.e. $O(mn)$. Additionally, for any integer $k \ge 1$, we provide a deterministic algorithm for a $O(k\log\log n)$-multiplicative approximation to the girth in directed graphs in $\tilde{O}(m^{1+1/k})$ time. Combining the techniques from these two results gives us an algorithm for a $O(k\log k)$-multiplicative approximation to the girth in directed graphs in $\tilde{O}(m^{1+1/k})$ time. Our results naturally also provide algorithms for improved constructions of roundtrip spanners, the analog of spanners in directed graphs. The previous fastest algorithms for these problems either ran in All-Pairs Shortest Paths (APSP) time, i.e. $O(mn)$, or were due Pachocki et al. (PRSTV18) which provided a randomized algorithm that for any integer $k \ge 1$ in time $\tilde{O}(m^{1+1/k})$ computed with high probability a $O(k\log n)$ multiplicative approximation of the girth. Our first algorithm constitutes the first sub-APSP-time algorithm for approximating the girth to constant accuracy, our second removes the need for randomness and improves the approximation factor in Pachocki et al. (PRSTV18), and our third is the first time versus quality trade-off for obtaining constant approximations.Open AccessConstant Girth Approximation for Directed Graphs in Subquadratic Time
In this paper we provide a $\tilde{O}(m\sqrt{n})$ time algorithm that computes a $3$-multiplicative approximation of the girth of a $n$-node $m$-edge directed graph with non-negative edge lengths. This is the first algorithm which approximates the girth of a directed graph up to a constant multiplicative factor faster than All-Pairs Shortest Paths (APSP) time, i.e. $O(mn)$. Additionally, for any integer $k \ge 1$, we provide a deterministic algorithm for a $O(k\log\log n)$-multiplicative approximation to the girth in directed graphs in $\tilde{O}(m^{1+1/k})$ time. Combining the techniques from these two results gives us an algorithm for a $O(k\log k)$-multiplicative approximation to the girth in directed graphs in $\tilde{O}(m^{1+1/k})$ time. Our results naturally also provide algorithms for improved constructions of roundtrip spanners, the analog of spanners in directed graphs. The previous fastest algorithms for these problems either ran in All-Pairs Shortest Paths (APSP) time, i.e. $O(mn)$, or were due Pachocki et al. (PRSTV18) which provided a randomized algorithm that for any integer $k \ge 1$ in time $\tilde{O}(m^{1+1/k})$ computed with high probability a $O(k\log n)$ multiplicative approximation of the girth. Our first algorithm constitutes the first sub-APSP-time algorithm for approximating the girth to constant accuracy, our second removes the need for randomness and improves the approximation factor in Pachocki et al. (PRSTV18), and our third is the first time versus quality trade-off for obtaining constant approximations.