Shiri Chechik

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

Improved Approximate Distance Oracles: Bypassing the Thorup-Zwick Bound in Dense Graphs.

[BibT_eX]

[DOI]

CoRR, 2023

Õptimal Fault-Tolerant Reachability Labeling in Planar Graphs.

[BibT_eX]

[DOI]

Shay Mozes

Oren Weimann

CoRR, 2023

Streaming Edge Coloring with Subquadratic Palette Size.

[BibT_eX]

[DOI]

CoRR, 2023

Approximate Distance Sensitivity Oracles in Subquadratic Space.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Faster Deterministic Worst-Case Fully Dynamic All-Pairs Shortest Paths via Decremental Hop-Restricted Shortest Paths.

[BibT_eX]

[DOI]

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

2022

Dynamic Graph Algorithms (Dagstuhl Seminar 22461).

[BibT_eX]

[DOI]

Dagstuhl Reports, November, 2022

Single-source shortest paths in the CONGEST model with improved bounds.

[BibT_eX]

[DOI]

Distributed Comput., 2022

Nearly 2-Approximate Distance Oracles in Subquadratic Time.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Constant-Round Near-Optimal Spanners in Congested Clique.

[BibT_eX]

[DOI]

Proceedings of the PODC '22: ACM Symposium on Principles of Distributed Computing, Salerno, Italy, July 25, 2022

Constant Approximation of Min-Distances in Near-Linear Time.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Incremental Single Source Shortest Paths in Sparse Digraphs.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

Optimal Girth Approximation for Dense Directed Graphs.

[BibT_eX]

[DOI]

Gur Lifshitz

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

Ramsey Spanning Trees and Their Applications.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2020

Constant girth approximation for directed graphs in subquadratic time.

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Distance sensitivity oracles with subcubic preprocessing time and fast query time.

[BibT_eX]

[DOI]

Sarel Cohen

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Dynamic Low-Stretch Spanning Trees in Subpolynomial Time.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Single-Source Shortest Paths in the CONGEST Model with Improved Bound.

[BibT_eX]

[DOI]

Proceedings of the PODC '20: ACM Symposium on Principles of Distributed Computing, 2020

Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs.

[BibT_eX]

[DOI]

Moran Nechushtan

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem.

[BibT_eX]

[DOI]

Ofer Magen

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

2019

Special Issue: APPROX-RANDOM 2016: Guest Editors' Foreword.

[BibT_eX]

[DOI]

Ronen Shaltiel

Theory Comput., 2019

Improved Girth Approximation and Roundtrip Spanners.

[BibT_eX]

[DOI]

CoRR, 2019

Reachability and Shortest Paths in the Broadcast CONGEST Model.

[BibT_eX]

[DOI]

Proceedings of the 33rd International Symposium on Distributed Computing, 2019

Optimal Distributed Coloring Algorithms for Planar Graphs in the LOCAL model.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Near Optimal Algorithms For The Single Source Replacement Paths Problem.

[BibT_eX]

[DOI]

Sarel Cohen

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles.

[BibT_eX]

[DOI]

Noga Alon

Sarel Cohen

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

Fully Dynamic Maximal Independent Set in Expected Poly-Log Update Time.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Near-Optimal Light Spanners.

[BibT_eX]

[DOI]

Christian Wulff-Nilsen

ACM Trans. Algorithms, 2018

Incremental Topological Sort and Cycle Detection in Expected Total Time.

[BibT_eX]

[DOI]

Aaron Bernstein

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Near-Optimal Approximate Decremental All Pairs Shortest Paths.

[BibT_eX]

[DOI]

Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, 2018

Clustering Small Samples With Quality Guarantees: Adaptivity With One2all PPS.

[BibT_eX]

[DOI]

Edith Cohen

Haim Kaplan

Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, 2018

2017

Clustering over Multi-Objective Samples: The one2all Sample.

[BibT_eX]

[DOI]

Edith Cohen

Haim Kaplan

CoRR, 2017

Secluded Connectivity Problems.

[BibT_eX]

[DOI]

Algorithmica, 2017

Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs.

[BibT_eX]

[DOI]

Thomas Dueholm Hansen

Giuseppe F. Italiano

Veronika Loitzenbauer

Nikos Parotsidis

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

(1 + ∊)-Approximate <i>f</i>-Sensitive Distance Oracles.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs.

[BibT_eX]

[DOI]

Aaron Bernstein

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Fully dynamic all-pairs shortest paths with worst-case update-time revisited.

[BibT_eX]

[DOI]

Sebastian Krinninger

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

2016

Compact Routing Schemes.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Additive Spanners.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Forbidden-Set Distance Labels for Graphs of Bounded Doubling Dimension.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2016

Deterministic decremental single source shortest paths: beyond the o(mn) bound.

[BibT_eX]

[DOI]

Aaron Bernstein

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Bottleneck Paths and Trees and Deterministic Graphical Games.

[BibT_eX]

[DOI]

Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science, 2016

On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Decremental Single-Source Reachability and Strongly Connected Components in Õ(m√n) Total Update Time.

[BibT_eX]

[DOI]

Thomas Dueholm Hansen

Giuseppe F. Italiano

Jakub Lacki

Nikos Parotsidis

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

The fault-tolerant capacitated K-center problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Fault tolerant additive and (μ, α)-spanners.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2015

Low-Distortion Inference of Latent Similarities from a Multiplex Social Network.

[BibT_eX]

[DOI]

SIAM J. Comput., 2015

Approximate Distance Oracles with Improved Bounds.

[BibT_eX]

[DOI]

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Average Distance Queries through Weighted Samples in Graphs and Metric Spaces: High Scalability with Tight Statistical Guarantees.

[BibT_eX]

[DOI]

Edith Cohen

Haim Kaplan

Proceedings of the Approximation, 2015

Approximate Nearest Neighbor Search in Metrics of Planar Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2015

2014

Robust fault tolerant uncapacitated facility location.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2014

Approximate distance oracles with constant query time.

[BibT_eX]

[DOI]

Virginia Vassilevska Williams

Proceedings of the Symposium on Theory of Computing, 2014

Better Approximation Algorithms for the Graph Diameter.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Distance Labels with Optimal Local Stretch.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Fully Dynamic All-Pairs Shortest Paths: Breaking the O(n) Barrier.

[BibT_eX]

[DOI]

Kunal Talwar

Proceedings of the Approximation, 2014

2013

Fault-tolerant compact routing schemes for general graphs.

[BibT_eX]

[DOI]

Inf. Comput., 2013

Approximate Distance Oracle with Constant Query Time

[BibT_eX]

[DOI]

CoRR, 2013

Dynamic Decremental Approximate Distance Oracles with (1+ε, 2) stretch.

[BibT_eX]

[DOI]

CoRR, 2013

New Additive Spanners.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

Compact routing schemes with improved stretch.

[BibT_eX]

[DOI]

Proceedings of the ACM Symposium on Principles of Distributed Computing, 2013

2012

Sparse reliable graph backbones.

[BibT_eX]

[DOI]

Inf. Comput., 2012

Secluded Connectivity Problems

[BibT_eX]

[DOI]

CoRR, 2012

f-Sensitivity Distance Oracles and Routing Schemes.

[BibT_eX]

[DOI]

Algorithmica, 2012

Fault Tolerant Additive Spanners.

[BibT_eX]

[DOI]

Gilad Braunschvig

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels.

[BibT_eX]

[DOI]

Cyril Gavoille

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

Multipath Spanners via Fault-Tolerant Spanners.

[BibT_eX]

[DOI]

Quentin Godfroy

Proceedings of the Design and Analysis of Algorithms, 2012

Improved Distance Oracles and Spanners for Vertex-Labeled Graphs.

[BibT_eX]

[DOI]

Proceedings of the Algorithms - ESA 2012, 2012

2011

Improved Distance Oracles for Vertex-Labeled Graphs

[BibT_eX]

[DOI]

CoRR, 2011

2010

Fault Tolerant Spanners for General Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2010

<i>f</i>-Sensitivity Distance Oracles and Routing Schemes.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2010

2009

Low-Port Tree Representations.

[BibT_eX]

[DOI]