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) - 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) - New Additive Spanners.

Shiri Chechik.

*Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms*(SODA 2013) - 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) - 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)

Conferences Program Committees

- 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

- 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.
- The Shimon Even Prize in Theoretical Computer Science, Weizmann Institute of Science.
- ICALP 2011 - Best student paper award. "Fault-Tolerant Compact Routing Schemes for General Graphs".

Contact Information

Department of Computer Science

Tel-Aviv University

Tel Aviv 69978 Israel

e-mail: first "DOT" last "AT" gmail "DOT" com