Shiri Chechik

I am a faculty member in the Department of Computer Science at Tel-Aviv University.
My main research interests are in the design and analysis of combinatorial algorithms, and theory of computing in general.

Selected Publications

• Faster Deterministic Streaming Vertex Coloring.
  Hongyi Chen, Shiri Chechik, Tianyi Zhang.
  To appear in Proceedings of the 53rd International Colloquium on Automata, Languages and Programming (ICALP 2026).
• Simpler and Improved Replacement Path Coverings.
  Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Martin Schirneck.
  To appear in Proceedings of the 53rd International Colloquium on Automata, Languages and Programming (ICALP 2026).
• Girth Approximations in the CONGEST Model.
  Shiri Chechik, Gur Lifshitz, Doron Mukhtar.
  To appear in Proceedings of the 45th ACM Symposium on Principles of Distributed Computing (PODC 2026).
• (\alpha,\beta) Spanners and Hybrid Spanners with Nearly Tight Bounds.
  Shiri Chechik, Gur Lifshitz.
  In Proceedings of the 37th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026).
• Improved Streaming Edge Coloring.
  Shiri Chechik, Hongyi Chen, Tianyi Zhang.
  In Proceedings of the 52nd International Colloquium on Automata, Languages and Programming (ICALP 2025).
• Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs.
  Ittai Boneh, Shiri Chechik, Shay Golan, Shay Mozes, Oren Weimann.
  In Proceedings of the 57th ACM Symposium on Theory of Computing (STOC 2025).
• New Approximation Algorithms and Reductions for n-Pairs Shortest Paths and All-Nodes Shortest Cycles.
  Shiri Chechik, Itay Hoch, Gur Lifshitz.
  In Proceedings of the 36th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2025).
• Approximate Distance Sensitivity Oracles in Subquadratic Space.
  Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, Martin Schirneck.
  TheoretiCS 3: Article 15 (2024).
  Preliminary version in Proceedings of the 55th ACM Symposium on Theory of Computing (STOC 2023).
• Path-Reporting Distance Oracles with Logarithmic Stretch and Linear Size.
  Shiri Chechik, Tianyi Zhang.
  In Proceedings of the 51st International Colloquium on Automata, Languages and Programming (ICALP 2024).
• Faster Algorithms for Dual-Failure Replacement Paths.
  Shiri Chechik, Tianyi Zhang.
  In Proceedings of the 51st International Colloquium on Automata, Languages and Programming (ICALP 2024).
• Streaming Edge Coloring with Subquadratic Palette Size.
  Shiri Chechik, Doron Mukhtar, Tianyi Zhang.
  In Proceedings of the 51st International Colloquium on Automata, Languages and Programming (ICALP 2024).
• Improved Distance (Sensitivity) Oracles with Subquadratic Space.
  Davide Bilò, Shiri Chechik, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Martin Schirneck.
  In Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2024).
• Nearly Optimal Approximate Dual-Failure Replacement Paths.
  Shiri Chechik, Tianyi Zhang.
  In Proceedings of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024).
• Faster Deterministic Worst-Case Fully Dynamic All-Pairs Shortest Paths via Decremental Hop-Restricted Shortest Paths.
  Shiri Chechik, Tianyi Zhang.
  In Proceedings of the 34th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2023).
• Single-source shortest paths in the CONGEST model with improved bounds.
  Shiri Chechik, Doron Mukhtar.
  Distributed Computing 35(4): 357-374, 2022.
  Preliminary version in Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC 2020).
• Constant Approximation of Min-Distances in Near-Linear Time.
  Shiri Chechik, Tianyi Zhang.
  In Proceedings of the 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2022).
• Constant-Round Near-Optimal Spanners in Congested Clique.
  Shiri Chechik, Tianyi Zhang.
  In Proceedings of the 41st ACM Symposium on Principles of Distributed Computing (PODC 2022).
• Nearly 2-Approximate Distance Oracles in Subquadratic Time.
  Shiri Chechik, Tianyi Zhang.
  In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022).
• Incremental Single Source Shortest Paths in Sparse Digraphs.
  Shiri Chechik, Tianyi Zhang.
  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).
• Optimal Girth Approximation for Dense Directed Graphs.
  Shiri Chechik, Gur Lifshitz.
  In Proceedings of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021).
• Ramsey Spanning Trees and Their Applications.
  Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman.
  ACM Transactions on Algorithms 16(2): 19:1-19:21, 2020.
  Preliminary version in SODA 2018.
• Distance sensitivity oracles with subcubic preprocessing time and fast query time.
  Shiri Chechik, Sarel Cohen.
  In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC 2020).
• Constant girth approximation for directed graphs in subquadratic time.
  Shiri Chechik, Yang P. Liu, Omer Rotem, Aaron Sidford.
  In Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC 2020).
• Dynamic Low-Stretch Spanning Trees in Subpolynomial Time.
  Shiri Chechik, Tianyi Zhang.
  In Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2020).
• Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem.
  Shiri Chechik, Ofer Magen.
  In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP 2020).
• Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs.
  Shiri Chechik, Moran Nechushtan.
  In Proceedings of the 47th International Colloquium on Automata, Languages and Programming (ICALP 2020).
• Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time.
  Shiri Chechik, Tianyi Zhang.
  In Proceedings of the 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019).
• Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles.
  Noga Alon, Shiri Chechik, Sarel Cohen.
  In Proceedings of the 46th International Colloquium on Automata, Languages and Programming (ICALP 2019).
• Reachability and Shortest Paths in the Broadcast CONGEST model.
  Shiri Chechik, Doron Mukhtar.
  In Proceedings of the 33rd International Symposium on Distributed Computing (DISC 2019).
• Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model.
  Shiri Chechik, Doron Mukhtar.
  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).
• Near Optimal Algorithms For The Single Source Replacement Paths Problem.
  Shiri Chechik, Sarel Cohen.
  In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019).
• Near-Optimal Light Spanners.
  Shiri Chechik, Christian Wulff-Nilsen.
  ACM Transactions on Algorithms 14(3): 33:1-33:15, 2018.
  Preliminary version in SODA 2016. * Best paper award.
• Near-Optimal Approximate Decremental All Pairs Shortest Paths.
  Shiri Chechik.
  In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018).
• Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms.
  Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein and David Wajc.
  In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP 2018).
• Incremental Topological Sort and Cycle Detection in Expected Total Time.
  Aaron Bernstein, Shiri Chechik.
  In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018).
• Clustering Small Samples With Quality Guarantees: Adaptivity With One2all PPS.
  Edith Cohen, Shiri Chechik, Haim Kaplan.
  In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI 2018).
• Secluded Connectivity Problems.
  Shiri Chechik, Matthew P. Johnson, Merav Parter, David Peleg.
  Algorithmica 79(3): 708-741, 2017.
  Preliminary version in ESA 2013.
• Fully dynamic all-pairs shortest paths with worst-case update-time revisited.
  Ittai Abraham, Shiri Chechik and Sebastian Krinninger.
  In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).
• Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs.
  Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Veronika Loitzenbauer and Nikos Parotsidis.
  In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).
• (1+\epsilon)-Approximate f-Sensitive Distance Oracles.
  Shiri Chechik, Sarel Cohen, Amos Fiat and Haim Kaplan.
  In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).
• Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs.
  Aaron Bernstein and Shiri Chechik.
  In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017).
• Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension.
  Ittai Abraham, Shiri Chechik, Cyril Gavoille, David Peleg.
  ACM Transactions on Algorithms 12(2): 22:1-22:17, 2016.
  Preliminary version in PODC 2010.
• Decremental Single-Source Reachability and Strongly Connected Components in $O(m\sqrt{n \log n})$.
  Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano, Jakub Lacki, and Nikos Parotsidis.
  In Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016).
• Deterministic decremental single source shortest paths: beyond the o(mn) bound.
  Aaron Bernstein, and Shiri Chechik.
  In Proceedings of the 48th ACM Symposium on Theory of Computing (STOC 2016).
• On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs.
  Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew Goldberg, and Renato Werneck.
  In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016).
• Bottleneck Paths and Trees and Deterministic Graphical Games.
  Shiri Chechik, Haim Kaplan, Mikkel Thorup, Or Zamir, Uri Zwick.
  In Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016).
• Fault tolerant additive and (\mu, \alpha)-spanners.
  Gilad Braunschvig, Shiri Chechik, David Peleg, Adam Sealfon.
  Theoretical Computer Science 580: 94-100, 2015.
  Preliminary version in WG 2012.
• The fault-tolerant capacitated K-center problem.
  Shiri Chechik, David Peleg.
  Theoretical Computer Science 566: 12-25, 2015.
  Preliminary version in SIROCCO 2012.
• Low-Distortion Inference of Latent Similarities from a Multiplex Social Network.
  Ittai Abraham, Shiri Chechik, David Kempe, Aleksandrs Slivkins.
  SIAM Journal on Computing (SICOMP) 44(3): 617-668, 2015.
  Preliminary version in SODA 2013.
• Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees.
  Shiri Chechik, Edith Cohen, and Haim Kaplan.
  In Proceedings of the 19th International Workshop on Randomization and Computation (RANDOM 2015).
• Approximate Nearest Neighbor Search in Metrics of Planar Graphs.
  Ittai Abraham, Shiri Chechik, Robert Krauthgamer, and Udi Wieder.
  In Proceedings of the 18th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2015).
• Approximate Distance Oracles with Improved Bounds.
  Shiri Chechik.
  In Proceedings of the 47th ACM Symposium on Theory of Computing (STOC 2015).
• Robust fault tolerant uncapacitated facility location.
  Shiri Chechik, David Peleg.
  Theoretical Computer Science 543: 9-23, 2014.
  Preliminary version in STACS 2010.
• Fully Dynamic All-Pairs Shortest Paths: Breaking the $O(n)$ Barrier.
  Ittai Abraham, Shiri Chechik, and Kunal Talwar.
  In Proceedings of the 17th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2014).
• Distance Labels with Optimal Local Stretch.
  Ittai Abraham, and Shiri Chechik.
  In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014).
• Approximate Distance Oracles with Constant Query Time.
  Shiri Chechik.
  In Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014).
• Better Approximation Algorithms for the Graph Diameter.
  Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert E. Tarjan, and Virginia Vassilevska Williams.
  In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014).
• Fault-Tolerant Compact Routing Schemes for General Graphs.
  Shiri Chechik.
  Information and Computation (I&C) 222: 36-44, 2013.
  Preliminary version in ICALP 2011. * Best student paper award.
• Compact Routing Schemes with Improved Stretch.
  Shiri Chechik.
  In Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing (PODC 2013). * Best paper award. Invited to JACM.
• New Additive Spanners.
  Shiri Chechik.
  In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013). * Best student paper award.
• f-Sensitivity Distance Oracles and Routing Schemes.
  Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty.
  Algorithmica 63(4): 861-882, 2012.
  Preliminary version in ESA 2010.
• Sparse Reliable Graph Backbones.
  Shiri Chechik, Yuval Emek, Boaz Patt-Shamir, David Peleg.
  Information and Computation (I&C) 210: 31-39, 2012.
  Preliminary version in ICALP 2010.
• Improved Distance Oracles and Spanners for Vertex-Labeled Graphs.
  Shiri Chechik.
  In Proceedings of the 20th Annual European Symposium on Algorithms (ESA 2012).
• Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels.
  Ittai Abraham, Shiri Chechik and Cyril Gavoille.
  In Proceedings of the 44th ACM Symposium on Theory of Computing (STOC 2012).
• Multipath Spanners via Fault-Tolerant Spanners.
  Shiri Chechik, Quentin Godfroy, David Peleg.
  In Proceedings of the 1st Mediterranean Conference on Algorithms (MedAlg 2012).
• Fault-tolerant spanners for general graphs.
  Shiri Chechik, Michael Langberg, David Peleg, Liam Roditty.
  SIAM Journal on Computing (SICOMP) 39(7): 3403-3423, 2010.
  Preliminary version in STOC 2009.
• Low-Port Tree Representations.
  Shiri Chechik and David Peleg.
  In Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009).

Conferences Program Committees

• SODA 2027
• STOC 2026
• FOCS 2025
• ICALP 2025
• FOCS 2023
• ESA 2022 (Program Chair)
• STOC 2022
• SOSA 2022
• SODA 2020
• DISC 2019
• STOC 2019
• FOCS 2017
• ICALP 2017
• APPROX 2016
• SSS 2016
• ESA 2016
• PODC 2016
• ICALP 2015
• SODA 2015
• DISC 2014
• ICDCN 2012

Prizes and Awards

• Appointed to The Raymond and Beverly Sackler Career Development Chair, Faculty of Exact Sciences, Tel Aviv University, 2018.
• Krill Prize, 2017.
• SODA 2016 - Best paper award. "Near-Optimal Light Spanners."
• Alon Fellowship for Outstanding Young Researchers, 2015.
• The Principles of Distributed Computing Doctoral Dissertation Award, 2013.
• PODC 2013 - Best paper award. "Compact Routing Schemes with Improved Stretch."
• SODA 2013 - Best student paper award. "New Additive Spanners."
• The Dimitris N. Chorafas Prize, Weizmann Institute of Science, 2012.
• The Shimon Even Prize in Theoretical Computer Science, Weizmann Institute of Science, 2012.
• ICALP 2011 - Best student paper award. "Fault-Tolerant Compact Routing Schemes for General Graphs."
• Dean’s lists, B.A studies, Tel-Aviv University, 2001-2003.

Contact Information

Department of Computer Science
Tel-Aviv University
Tel Aviv 69978 Israel
e-mail: first "DOT" last "AT" gmail "DOT" com