Michael Elkin

ORCID

Publication Activity (10 Years)

Years Active: 2000-2024
Publications (10 Years): 86

Top Venues

Publications

Michael Elkin, Chhaya Trehan
Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication. CoRR (2024)
Michael Elkin, Ariel Khuzman
Deterministic Simple (1+°)Δ-Edge-Coloring in Near-Linear Time. CoRR (2024)
Michael Elkin, Idan Shabat
Path-Reporting Distance Oracles with Near-Logarithmic Stretch and Linear Size. CoRR (2023)
Michael Elkin, Idan Shabat
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n). FOCS (2023)
Michael Elkin, Yuval Gitlitz, Ofer Neiman
Improved weighted additive spanners. Distributed Comput. 36 (3) (2023)
Michael Elkin, Ofer Neiman
Lossless Prioritized Embeddings. SIAM J. Discret. Math. 36 (3) (2022)
Michael Elkin, Chhaya Trehan
(1+ε)-Approximate Shortest Paths in Dynamic Streams. APPROX/RANDOM (2022)
Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. SPAA (2022)
Michael Elkin, Ofer Neiman
Distributed strong diameter network decomposition. Theor. Comput. Sci. 922 (2022)
Leonid Barenboim, Michael Elkin, Uri Goldenberg
Locally-iterative Distributed (Δ + 1)-coloring and Applications. J. ACM 69 (1) (2022)
Michael Elkin, Ofer Neiman
Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNC. Distributed Comput. 35 (5) (2022)
Michael Elkin, Ofer Neiman
Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication. STACS (2022)
Michael Elkin, Bernhard Haeupler, Václav Rozhon, Christoph Grunau
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. CoRR (2022)
Marcel Bezdrighin, Michael Elkin, Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, Václav Rozhon
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates. CoRR (2022)
Václav Rozhon, Michael Elkin, Christoph Grunau, Bernhard Haeupler
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. FOCS (2022)
Michael Elkin, Chhaya Trehan
Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams. PODC (2022)
Michael Elkin, Yuval Gitlitz, Ofer Neiman
Almost Shortest Paths with Near-Additive Error in Weighted Graphs. SWAT (2022)
Michael Elkin, Chhaya Trehan
$(1+ε)$-Approximate Shortest Paths in Dynamic Streams. CoRR (2021)
Michael Elkin, Shaked Matar
Ultra-Sparse Near-Additive Emulators. PODC (2021)
Michael Elkin, Yuval Gitlitz, Ofer Neiman
Improved Weighted Additive Spanners. DISC (2021)
Michael Elkin, Shaked Matar
Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work. SPAA (2021)
Michael Elkin, Shaked Matar
Ultra-Sparse Near-Additive Emulators. CoRR (2021)
Michael Elkin, Ofer Neiman
Near Isometric Terminal Embeddings for Doubling Metrics. Algorithmica 83 (11) (2021)
Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman
Ramsey Spanning Trees and Their Applications. ACM Trans. Algorithms 16 (2) (2020)
Michael Elkin
A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities. J. ACM 67 (2) (2020)
Michael Elkin
Distributed Exact Shortest Paths in Sublinear Time. J. ACM 67 (3) (2020)
Michael Elkin, Shaked Matar
Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work. CoRR (2020)
Michael Elkin, Ofer Neiman
Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication. CoRR (2020)
Michael Elkin, Ofer Neiman
Near-Additive Spanners and Near-Exact Hopsets, A Unified View. Bull. EATCS 130 (2020)
Michael Elkin, Ofer Neiman
Lossless Prioritized Embeddings. SODA (2020)
Michael Elkin, Arnold Filtser, Ofer Neiman
Distributed Construction of Light Networks. PODC (2020)
Michael Elkin, Yuval Gitlitz, Ofer Neiman
Improved Weighted Additive Spanners. CoRR (2020)
Michael Elkin, Ofer Neiman
Near-Additive Spanners and Near-Exact Hopsets, A Unified View. CoRR (2020)
Michael Elkin, Ofer Neiman
Lossless Prioritized Embeddings. CoRR (2019)
Michael Elkin, Arnold Filtser, Ofer Neiman
Distributed Construction of Light Networks. CoRR (2019)
Michael Elkin, Ofer Neiman
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. SIAM J. Comput. 48 (4) (2019)
Michael Elkin, Shaked Matar
Fast Deterministic Constructions of Linear-Size Spanners and Skeletons. CoRR (2019)
Michael Elkin, Ofer Neiman
Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC. SPAA (2019)
Michael Elkin, Yuval Gitlitz, Ofer Neiman
Almost Shortest Paths and PRAM Distance Oracles in Weighted Graphs. CoRR (2019)
Michael Elkin, Shaked Matar
Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time. PODC (2019)
Michael Elkin, Shaked Matar
Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time. CoRR (2019)
Michael Elkin, Ofer Neiman
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. ACM Trans. Algorithms 15 (1) (2019)
Leonid Barenboim, Michael Elkin, Cyril Gavoille
A fast network-decomposition algorithm and its applications to constant-time distributed computation. Theor. Comput. Sci. 751 (2018)
Michael Elkin
Session details: Session 3D: Graphs and Population. PODC (2018)
Michael Elkin, Ofer Neiman
Near-Optimal Distributed Routing with Low Memory. PODC (2018)
Michael Elkin, Ofer Neiman
Near Isometric Terminal Embeddings for Doubling Metrics. SoCG (2018)
Leonid Barenboim, Michael Elkin, Uri Goldenberg
Locally-Iterative Distributed (Δ+ 1): -Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. PODC (2018)
Michael Elkin, Ofer Neiman
On efficient distributed construction of near optimal routing schemes. Distributed Comput. 31 (2) (2018)
Michael Elkin, Ofer Neiman
Near Isometric Terminal Embeddings for Doubling Metrics. CoRR (2018)
Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman
Ramsey Spanning Trees and their Applications. SODA (2018)
Michael Elkin, Arnold Filtser, Ofer Neiman
Prioritized Metric Structures and Embedding. SIAM J. Comput. 47 (3) (2018)
Leonid Barenboim, Michael Elkin, Uri Goldenberg
Locally-Iterative Distributed (Delta + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. CoRR (2017)
Michael Elkin, Arnold Filtser, Ofer Neiman
Terminal embeddings. Theor. Comput. Sci. 697 (2017)
Michael Elkin
Distributed Exact Shortest Paths in Sublinear Time. CoRR (2017)
Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman
Ramsey Spanning Trees and their Applications. CoRR (2017)
Michael Elkin
A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities. PODC (2017)
Leonid Barenboim, Michael Elkin, Tzalik Maimon
Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity. PODC (2017)
Michael Elkin, Ofer Neiman
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. SODA (2017)
Michael Elkin
Distributed exact shortest paths in sublinear time. STOC (2017)
Michael Elkin, Ofer Neiman
Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory. CoRR (2017)
Michael Elkin
A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities. CoRR (2017)
Michael Elkin, Arnold Filtser, Ofer Neiman
Terminal Embeddings. CoRR (2016)
Michael Elkin, Ofer Neiman, Christian Wulff-Nilsen
Space-efficient path-reporting approximate distance oracles. Theor. Comput. Sci. 651 (2016)
Michael Elkin, Ofer Neiman
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. FOCS (2016)
Leonid Barenboim, Michael Elkin, Tzalik Maimon
Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity. CoRR (2016)
Michael Elkin, Ofer Neiman
Distributed Strong Diameter Network Decomposition: Extended Abstract. PODC (2016)
Michael Elkin, Ofer Neiman
Distributed Strong Diameter Network Decomposition. CoRR (2016)
Michael Elkin, Ofer Neiman
On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract. PODC (2016)
Michael Elkin, Ofer Neiman
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. CoRR (2016)
Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider
The Locality of Distributed Symmetry Breaking. J. ACM 63 (3) (2016)
Boaz Ben-Moshe, Michael Elkin, Lee-Ad Gottlieb, Eran Omri
Optimizing budget allocation for center and median points. Theor. Comput. Sci. 627 (2016)
Michael Elkin, Seth Pettie
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. ACM Trans. Algorithms 12 (4) (2016)
Michael Elkin, Ofer Neiman
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. CoRR (2016)
Michael Elkin, Shay Solomon
Fast Constructions of Lightweight Spanners for General Graphs. ACM Trans. Algorithms 12 (3) (2016)
Michael Elkin, Ofer Neiman
On Efficient Distributed Construction of Near Optimal Routing Schemes. CoRR (2016)
Michael Elkin, Ofer Neiman, Shay Solomon
Light Spanners. SIAM J. Discret. Math. 29 (3) (2015)
Michael Elkin, Shay Solomon
Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones. SIAM J. Comput. 44 (4) (2015)
Michael Elkin, Arnold Filtser, Ofer Neiman
Prioritized Metric Structures and Embedding. CoRR (2015)
Michael Elkin, Seth Pettie, Hsin-Hao Su
(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. SODA (2015)
Leonid Barenboim, Michael Elkin, Cyril Gavoille
A Fast Network-Decomposition Algorithm and its Applications to Constant-Time Distributed Computation. CoRR (2015)
Michael Elkin, Seth Pettie
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. SODA (2015)
Michael Elkin, Seth Pettie
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. CoRR (2015)
Leonid Barenboim, Michael Elkin, Cyril Gavoille
A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation - (Extended Abstract). SIROCCO (2015)
Michael Elkin, Arnold Filtser, Ofer Neiman
Terminal Embeddings. APPROX-RANDOM (2015)
Michael Elkin, Arnold Filtser, Ofer Neiman
Prioritized Metric Structures and Embedding. STOC (2015)
Michael Elkin, Shay Solomon
Optimal Euclidean Spanners: Really Short, Thin, and Lanky. J. ACM 62 (5) (2015)
Boaz Ben-Moshe, Michael Elkin, Lee-Ad Gottlieb, Eran Omri
Optimizing Budget Allocation in Graphs. CoRR (2014)
Leonid Barenboim, Michael Elkin, Fabian Kuhn
Distributed (Delta+1)-Coloring in Linear (in Delta) Time. SIAM J. Comput. 43 (1) (2014)
Michael Elkin, Ofer Neiman, Shay Solomon
Light Spanners. CoRR (2014)
Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan
Can quantum communication speed up distributed computation? PODC (2014)
Shay Solomon, Michael Elkin
Balancing Degree, Diameter, and Weight in Euclidean Spanners. SIAM J. Discret. Math. 28 (3) (2014)
Leonid Barenboim, Michael Elkin
Combinatorial algorithms for distributed graph coloring. Distributed Comput. 27 (2) (2014)
Michael Elkin, Ofer Neiman, Shay Solomon
Light Spanners. ICALP (1) (2014)
Michael Elkin, Ofer Neiman, Christian Wulff-Nilsen
Space-Efficient Path-Reporting Approximate Distance Oracles. CoRR (2014)
Johannes Schneider, Michael Elkin, Roger Wattenhofer
Symmetry breaking depending on the chromatic number or the neighborhood growth. Theor. Comput. Sci. 509 (2013)
Leonid Barenboim, Michael Elkin
Distributed deterministic edge coloring using bounded neighborhood independence. Distributed Comput. 26 (5-6) (2013)
Michael Elkin, Shay Solomon
Fast Constructions of Light-Weight Spanners for General Graphs. SODA (2013)
Michael Elkin, Shay Solomon
Optimal euclidean spanners: really short, thin and lanky. STOC (2013)
Michael Elkin, Shay Solomon
Optimal Euclidean spanners: really short, thin and lanky CoRR (2012)
Michael Elkin, Shay Solomon
Fast Constructions of Light-Weight Spanners for General Graphs CoRR (2012)

Michael Elkin.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Michael Elkin