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

Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model.
Shiri Chechik, Doron Mukhtar.
Submitted
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms.
Moab Arar, Shiri Chechik, Sarel Cohen, Cliff Stein and David Wajc.
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)
Ramsey Spanning Trees and their Applications.
Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman.
In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018)
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)
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)
Near-Optimal Light Spanners.
Shiri Chechik, and Christian Wulff-Nilsen.
Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)

* Best paper award.

On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs.
Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew Goldberg, and Renato Werneck.
Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees..
Shiri Chechik, Edith Cohen, and Haim Kaplan.
Proceedings of the 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.
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)
Fully Dynamic All-Pairs Shortest Paths: Breaking the $O(n)$ Barrier.
Ittai Abraham, Shiri Chechik, and Kunal Talwar.
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.
Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP 2014)
Approximate Distance Oracles with Constant Query Time.
Shiri Chechik.
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.
Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
Compact Routing Schemes with Improved Stretch.
Shiri Chechik.
Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing (PODC 2013)

* Best paper award.

New Additive Spanners.
Shiri Chechik.
Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)

* Best student paper award.

Low-distortion Inference of Latent Similarities from a Multiplex Social Network.
Ittai Abraham, Shiri Chechik, David Kempe and Aleksandrs Slivkins.
of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2013)
Improved Distance Oracles and Spanners for Vertex-Labeled Graphs.
Shiri Chechik.
Proceedings of the 20th Annual European Symposium on Algorithms (ESA 2012)
Fault Tolerant Additive Spanners..
Gilad Braunschvig, Shiri Chechik and David Peleg.
Proceedings of the 38th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2012)
Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels .
Ittai Abraham, Shiri Chechik and Cyril Gavoille.
Proceedings of the 44th ACM Symposium on Theory of Computing (STOC 2012)
Fault-Tolerant Compact Routing Schemes for General Graphs.
Shiri Chechik.
Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011)

* Best student paper award.

Forbidden-set distance labels for graphs of bounded doubling dimension .
Ittai Abraham, Shiri Chechik, Cyril Gavoille and David Peleg.
Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC 2010)
Sparse Reliable Graph Backbones .
Shiri Chechik, Yuval Emek, Boaz Patt-Shamir and David Peleg.
Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP 2010)
f-sensitivity distance oracles and routing schemes .
Shiri chechik, Michael Langberg, David Peleg and Liam Roditty.
Algorithmica, 2010, special issue for ESA'10. Preliminary version in Proceedings of the 18th Annual European Symposium on Algorithms (ESA 2010)
Robust Fault Tolerant uncapacitated facility location .
Shiri Chechik and David Peleg.
Proceedings of the 27th international Symposium on Theoretical Aspects of Computer Science (STACS 2010)
Fault Tolerant Spanners for General Graphs .
Shiri chechik, Michael Langberg, David Peleg and Liam Roditty.
SIAM Journal on Computing 39(7) , SICOMP, 2010. Preliminary version in Proceedings of the 41st ACM Symposium on Theory of Computing (STOC 2009)
Low-Port Tree Representations .
Shiri Chechik and David Peleg.
Proceedings of the 35th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009)