Publications (29)
Faster Algorithms for Dual-Failure Replacement Paths
Shiri Chechik, Tianyi Zhang
Given a simple weighted directed graph on vertices as well as two designated terminals , our goal is to compute the shortest path from to av…
Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem
Shiri Chechik, Ofer Magen
In the Single Source Replacement Paths (SSRP) problem we are given a graph , and a shortest paths tree rooted at a node , and the goal is to output for…
Improved Streaming Edge Coloring
Shiri Chechik, Hongyi Chen, Tianyi Zhang
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…
Secluded Connectivity Problems
Shiri Chechik, M. P. Johnson, Merav Parter +1
Consider a setting where possibly sensitive information sent over a path in a network is visible to every {neighbor} of the path, i.e., every neighbor of some node on the path, thu…
Constant Girth Approximation for Directed Graphs in Subquadratic Time
Shiri Chechik, Yang P. Liu, Omer Rotem +1
In this paper we provide a time algorithm that computes a -multiplicative approximation of the girth of a -node -edge directed graph with non-negati…
Low-distortion Inference of Latent Similarities from a Multiplex Social Network
Ittai Abraham, Shiri Chechik, David Kempe +1
Much of social network analysis is - implicitly or explicitly - predicated on the assumption that individuals tend to be more similar to their friends than to strangers. Thus, an o…
Ãptimal Fault-Tolerant Reachability Labeling in Planar Graphs
Shiri Chechik, Shay Mozes, Oren Weimann
We show how to assign labels of size to the vertices of a directed planar graph , such that from the labels of any three vertices we can deduce in $\tilde…
Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano +2
Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especiall…
Simpler and Improved Replacement Path Coverings
Davide Bilò, Shiri Chechik, Keerti Choudhary +2
An important tool in the design of fault-tolerant graph data structures are -replacement path coverings (RPCs). An RPC is a family of subgraphs of a given grap…
Ramsey Spanning Trees and their Applications
Ittai Abraham, Shiri Chechik, Michael Elkin +2
The metric Ramsey problem asks for the largest subset of a metric space that can be embedded into an ultrametric (more generally into a Hilbert space) with a given distortion.…
Improved Distance Oracles and Spanners for Vertex-Labeled Graphs
Shiri Chechik
Consider an undirected weighted graph G=(V,E) with |V|=n and |E|=m, where each vertex v is assigned a label from a set L of \ell labels. We show how to construct a compact distance…
Faster Deterministic Streaming Vertex Coloring
Shiri Chechik, Hongyi Chen, Tianyi Zhang
Graph coloring is a fundamental problem in computer science. In the semi-streaming model, an input graph on vertices and maximum degree is presented as a stream of edg…
Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs
Davide Bilò, Shiri Chechik, Keerti Choudhary +3
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 wi…
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time
Shiri Chechik, Tianyi Zhang
In the fully dynamic maximal independent set (MIS) problem our goal is to maintain an MIS in a given graph while edges are inserted and deleted from the graph. The first non-tr…
Dynamic Decremental Approximate Distance Oracles with stretch
Ittai Abraham, Shiri Chechik
We provide a decremental approximate Distance Oracle that obtains stretch of multiplicative and 2 additive and has total cost (where notation su…
Clustering Small Samples with Quality Guarantees: Adaptivity with One2all pps
Edith Cohen, Shiri Chechik, Haim Kaplan
Clustering of data points is a fundamental tool in data analysis. We consider points in a relaxed metric space, where the triangle inequality holds within a constant factor. Th…
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees
Shiri Chechik, Edith Cohen, Haim Kaplan
The average distance from a node to all other nodes in a graph, or from a query point in a metric space to a set of points, is a fundamental quantity in data analysis. The inverse…
Girth Approximations in the CONGEST Model
Shiri Chechik, Gur Lifshitz, Doron Mukhtar
This paper advances the state of the art in girth approximation within the CONGEST model. Manoharan and Ramachandran [PODC '24] provided the first significant improvement in girth…
Ãptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
Itai Boneh, Shiri Chechik, Shay Golan +2
We present a labeling scheme that assigns labels of size to the vertices of a directed weighted planar graph , such that for any fixed from the lab…
Approximate Distance Sensitivity Oracles in Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary +4
An -edge fault-tolerant distance sensitive oracle (-DSO) with stretch is a data structure that preprocesses a given undirected, unweighted graph with vertic…
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
Noga Alon, Shiri Chechik, Sarel Cohen
In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the random…
Improved Distance (Sensitivity) Oracles with Subquadratic Space
Davide Bilò, Shiri Chechik, Keerti Choudhary +3
A distance oracle (DO) with stretch for a graph is a data structure that, when queried with vertices and , returns a value such that $d(s,t…
Reachability and Shortest Paths in the Broadcast CONGEST Model
Shiri Chechik, Doron Mukhtar
In this paper we study the time complexity of the single-source reachability problem and the single-source shortest path problem for directed unweighted graphs in the Broadcast CON…
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms
Moab Arar, Shiri Chechik, Sarel Cohen +2
We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this redu…
Streaming Edge Coloring with Subquadratic Palette Size
Shiri Chechik, Doron Mukhtar, Tianyi Zhang
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 -node graph arrive in an arbitrary order…
Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model
Shiri Chechik, Doron Mukhtar
In this paper, we consider distributed coloring for planar graphs with a small number of colors. We present an optimal (up to a constant factor) time algorithm for 6-c…
Robust Fault Tolerant uncapacitated facility location
Shiri Chechik, David Peleg
In the uncapacitated facility location problem, given a graph, a set of demands and opening costs, it is required to find a set of facilities R, so as to minimize the sum of the co…
Fully dynamic all-pairs shortest paths with worst-case update-time revisited
Ittai Abraham, Shiri Chechik, Sebastian Krinninger
We revisit the classic problem of dynamically maintaining shortest paths between all pairs of nodes of a directed weighted graph. The allowed updates are insertions and deletions o…
Approximate Distance Oracle with Constant Query Time
Shiri Chechik
An approximate distance oracle is a succinct data structure that provides fast answers to distance queries between any two nodes. In this paper we consider approximate distance ora…