Shiri Chechik

Publication Activity (10 Years)

Years Active: 2009-2024
Publications (10 Years): 59

Top Topics

Strongly Connected Components

Top Venues

Publications

Shiri Chechik, Tianyi Zhang
Faster Algorithms for Dual-Failure Replacement Paths. CoRR (2024)
Shiri Chechik, Doron Mukhtar, Tianyi Zhang
Streaming Edge Coloring with Subquadratic Palette Size. ICALP (2024)
Shiri Chechik, Tianyi Zhang
Nearly Optimal Approximate Dual-Failure Replacement Paths. SODA (2024)
Shiri Chechik, Tianyi Zhang
Faster Algorithms for Dual-Failure Replacement Paths. ICALP (2024)
Shiri Chechik, Tianyi Zhang
Path-Reporting Distance Oracles with Logarithmic Stretch and Linear Size. ICALP (2024)
Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck
Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs. CoRR (2023)
Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck
Approximate Distance Sensitivity Oracles in Subquadratic Space. STOC (2023)
Shiri Chechik, Doron Mukhtar, Tianyi Zhang
Streaming Edge Coloring with Subquadratic Palette Size. CoRR (2023)
Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck
Approximate Distance Sensitivity Oracles in Subquadratic Space. CoRR (2023)
Shiri Chechik, Shay Mozes, Oren Weimann
Õptimal Fault-Tolerant Reachability Labeling in Planar Graphs. CoRR (2023)
Shiri Chechik, Tianyi Zhang
Faster Deterministic Worst-Case Fully Dynamic All-Pairs Shortest Paths via Decremental Hop-Restricted Shortest Paths. SODA (2023)
Shiri Chechik, Tianyi Zhang
Constant-Round Near-Optimal Spanners in Congested Clique. PODC (2022)
Shiri Chechik, Tianyi Zhang
Constant Approximation of Min-Distances in Near-Linear Time. FOCS (2022)
Aaron Bernstein, Shiri Chechik, Sebastian Forster, Tsvi Kopelowitz, Yasamin Nazari, Nicole Wein
Dynamic Graph Algorithms (Dagstuhl Seminar 22461). Dagstuhl Reports 12 (11) (2022)
Shiri Chechik, Doron Mukhtar
Single-source shortest paths in the CONGEST model with improved bounds. Distributed Comput. 35 (4) (2022)
Shiri Chechik, Tianyi Zhang
Nearly 2-Approximate Distance Oracles in Subquadratic Time. SODA (2022)
Shiri Chechik, Gur Lifshitz
Optimal Girth Approximation for Dense Directed Graphs. SODA (2021)
Shiri Chechik, Tianyi Zhang
Incremental Single Source Shortest Paths in Sparse Digraphs. SODA (2021)
Shiri Chechik, Moran Nechushtan
Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs. ICALP (2020)
Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman
Ramsey Spanning Trees and Their Applications. ACM Trans. Algorithms 16 (2) (2020)
Shiri Chechik, Sarel Cohen
Distance sensitivity oracles with subcubic preprocessing time and fast query time. STOC (2020)
Shiri Chechik, Ofer Magen
Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem. ICALP (2020)
Shiri Chechik, Ofer Magen
Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem. CoRR (2020)
Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford
Constant girth approximation for directed graphs in subquadratic time. STOC (2020)
Shiri Chechik, Doron Mukhtar
Single-Source Shortest Paths in the CONGEST Model with Improved Bound. PODC (2020)
Shiri Chechik, Tianyi Zhang
Dynamic Low-Stretch Spanning Trees in Subpolynomial Time. SODA (2020)
Noga Alon, Shiri Chechik, Sarel Cohen
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. CoRR (2019)
Shiri Chechik, Sarel Cohen
Near Optimal Algorithms For The Single Source Replacement Paths Problem. SODA (2019)
Shiri Chechik, Doron Mukhtar
Reachability and Shortest Paths in the Broadcast CONGEST Model. CoRR (2019)
Shiri Chechik, Doron Mukhtar
Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model. SODA (2019)
Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford
Improved Girth Approximation and Roundtrip Spanners. CoRR (2019)
Shiri Chechik, Ronen Shaltiel
Special Issue: APPROX-RANDOM 2016: Guest Editors' Foreword. Theory Comput. 15 (2019)
Shiri Chechik, Tianyi Zhang
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time. CoRR (2019)
Noga Alon, Shiri Chechik, Sarel Cohen
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles. ICALP (2019)
Shiri Chechik, Tianyi Zhang
Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time. FOCS (2019)
Shiri Chechik, Doron Mukhtar
Reachability and Shortest Paths in the Broadcast CONGEST Model. DISC (2019)
Aaron Bernstein, Shiri Chechik
Incremental Topological Sort and Cycle Detection in Expected Total Time. SODA (2018)
Shiri Chechik, Christian Wulff-Nilsen
Near-Optimal Light Spanners. ACM Trans. Algorithms 14 (3) (2018)
Edith Cohen, Shiri Chechik, Haim Kaplan
Clustering Small Samples With Quality Guarantees: Adaptivity With One2all PPS. AAAI (2018)
Shiri Chechik, Doron Mukhtar
Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model. CoRR (2018)
Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, David Wajc
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms. ICALP (2018)
Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman
Ramsey Spanning Trees and their Applications. SODA (2018)
Shiri Chechik
Near-Optimal Approximate Decremental All Pairs Shortest Paths. FOCS (2018)
Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein, David Wajc
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms. CoRR (2017)
Shiri Chechik, Matthew P. Johnson, Merav Parter, David Peleg
Secluded Connectivity Problems. Algorithmica 79 (3) (2017)
Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, Nikos Parotsidis
Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs. SODA (2017)
Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman
Ramsey Spanning Trees and their Applications. CoRR (2017)
Shiri Chechik, Sarel Cohen, Amos Fiat, Haim Kaplan
-Sensitive Distance Oracles. SODA (2017)
Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer, Nikos Parotsidis
Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs. CoRR (2017)
Ittai Abraham, Shiri Chechik, Sebastian Krinninger
Fully dynamic all-pairs shortest paths with worst-case update-time revisited. SODA (2017)
Edith Cohen, Shiri Chechik, Haim Kaplan
Clustering over Multi-Objective Samples: The one2all Sample. CoRR (2017)
Aaron Bernstein, Shiri Chechik
Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs. SODA (2017)
Ittai Abraham, Shiri Chechik, Sebastian Krinninger
Fully dynamic all-pairs shortest paths with worst-case update-time revisited. CoRR (2016)
Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, Nikos Parotsidis
Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time. FOCS (2016)
Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, Uri Zwick
Bottleneck Paths and Trees and Deterministic Graphical Games. STACS (2016)
Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew V. Goldberg, Renato F. Werneck
On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs. SODA (2016)
Ittai Abraham, Shiri Chechik, Cyril Gavoille, David Peleg
Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension. ACM Trans. Algorithms 12 (2) (2016)
Aaron Bernstein, Shiri Chechik
Deterministic decremental single source shortest paths: beyond the o(mn) bound. STOC (2016)
Shiri Chechik, Christian Wulff-Nilsen
Near-Optimal Light Spanners. SODA (2016)
Shiri Chechik, Edith Cohen, Haim Kaplan
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees. CoRR (2015)
Ittai Abraham, Shiri Chechik, Robert Krauthgamer, Udi Wieder
Approximate Nearest Neighbor Search in Metrics of Planar Graphs. APPROX-RANDOM (2015)
Shiri Chechik
Approximate Distance Oracles with Improved Bounds. STOC (2015)
Shiri Chechik, Edith Cohen, Haim Kaplan
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees. APPROX-RANDOM (2015)
Shiri Chechik, David Peleg
The fault-tolerant capacitated K-center problem. Theor. Comput. Sci. 566 (2015)
Gilad Braunschvig, Shiri Chechik, David Peleg, Adam Sealfon
Fault tolerant additive and (μ, α)-spanners. Theor. Comput. Sci. 580 (2015)
Ittai Abraham, Shiri Chechik, David Kempe, Aleksandrs Slivkins
Low-Distortion Inference of Latent Similarities from a Multiplex Social Network. SIAM J. Comput. 44 (3) (2015)
Ittai Abraham, Shiri Chechik
Distance Labels with Optimal Local Stretch. ICALP (1) (2014)
Ittai Abraham, Shiri Chechik, Kunal Talwar
Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier. APPROX-RANDOM (2014)
Shiri Chechik, David Peleg
Robust fault tolerant uncapacitated facility location. Theor. Comput. Sci. 543 (2014)
Shiri Chechik
Approximate distance oracles with constant query time. STOC (2014)
Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, Virginia Vassilevska Williams
Better Approximation Algorithms for the Graph Diameter. SODA (2014)
Ittai Abraham, Shiri Chechik, David Kempe, Aleksandrs Slivkins
Low-distortion Inference of Latent Similarities from a Multiplex Social Network. SODA (2013)
Shiri Chechik
New Additive Spanners. SODA (2013)
Shiri Chechik
Fault-tolerant compact routing schemes for general graphs. Inf. Comput. 222 (2013)
Shiri Chechik
Approximate Distance Oracle with Constant Query Time CoRR (2013)
Shiri Chechik, Matthew P. Johnson, Merav Parter, David Peleg
Secluded Connectivity Problems. ESA (2013)
Shiri Chechik
Compact routing schemes with improved stretch. PODC (2013)
Ittai Abraham, Shiri Chechik
Dynamic Decremental Approximate Distance Oracles with (1+ε, 2) stretch. CoRR (2013)
Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty
f-Sensitivity Distance Oracles and Routing Schemes. Algorithmica 63 (4) (2012)
Shiri Chechik, Yuval Emek, Boaz Patt-Shamir, David Peleg
Sparse reliable graph backbones. Inf. Comput. 210 (2012)
Shiri Chechik, Quentin Godfroy, David Peleg
Multipath Spanners via Fault-Tolerant Spanners. MedAlg (2012)
Ittai Abraham, Shiri Chechik, Cyril Gavoille
Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. STOC (2012)
Shiri Chechik, Matthew P. Johnson, Merav Parter, David Peleg
Secluded Connectivity Problems CoRR (2012)
Shiri Chechik, David Peleg
The Fault Tolerant Capacitated k-Center Problem. SIROCCO (2012)
Ittai Abraham, Shiri Chechik, David Kempe, Aleksandrs Slivkins
Low-distortion Inference of Latent Similarities from a Multiplex Social Network CoRR (2012)
Gilad Braunschvig, Shiri Chechik, David Peleg
Fault Tolerant Additive Spanners. WG (2012)
Shiri Chechik
Improved Distance Oracles and Spanners for Vertex-Labeled Graphs. ESA (2012)
Shiri Chechik
Fault-Tolerant Compact Routing Schemes for General Graphs. ICALP (2) (2011)
Shiri Chechik
Improved Distance Oracles for Vertex-Labeled Graphs CoRR (2011)
Shiri Chechik, David Peleg
Robust Fault Tolerant Uncapacitated Facility Location. STACS (2010)
Shiri Chechik, Yuval Emek, Boaz Patt-Shamir, David Peleg
Sparse Reliable Graph Backbones. ICALP (2) (2010)
Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty
-Sensitivity Distance Oracles and Routing Schemes. ESA (1) (2010)
Ittai Abraham, Shiri Chechik, Cyril Gavoille, David Peleg
Forbidden-set distance labels for graphs of bounded doubling dimension. PODC (2010)
Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty
Fault Tolerant Spanners for General Graphs. SIAM J. Comput. 39 (7) (2010)
Shiri Chechik, David Peleg
Low-Port Tree Representations. WG (2009)
Shiri Chechik, David Peleg
Robust Fault Tolerant uncapacitated facility location CoRR (2009)
Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty
Fault-tolerant spanners for general graphs. STOC (2009)