default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDMichael Elkin
Person information
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[i45]Michael Elkin, Chhaya Trehan:
Faster Multi-Source Directed Reachability via Shortcuts and Matrix Multiplication. CoRR abs/2401.05628 (2024)- [i44]Michael Elkin, Ariel Khuzman:
Deterministic Simple (1+°)Δ-Edge-Coloring in Near-Linear Time. CoRR abs/2401.10538 (2024) - 2023
- [j54]Michael Elkin, Yuval Gitlitz, Ofer Neiman:
Improved weighted additive spanners. Distributed Comput. 36(3): 385-394 (2023) - [c67]Michael Elkin, Idan Shabat:
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n). FOCS 2023: 2278-2311 - [i43]Michael Elkin, Idan Shabat:
Path-Reporting Distance Oracles with Near-Logarithmic Stretch and Linear Size. CoRR abs/2304.04445 (2023) - 2022
- [j53]Michael Elkin, Ofer Neiman
:
Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNC. Distributed Comput. 35(5): 419-437 (2022) - [j52]Leonid Barenboim, Michael Elkin, Uri Goldenberg:
Locally-iterative Distributed (Δ + 1)-coloring and Applications. J. ACM 69(1): 5:1-5:26 (2022) - [j51]Michael Elkin, Ofer Neiman:
Lossless Prioritized Embeddings. SIAM J. Discret. Math. 36(3): 1529-1550 (2022) - [j50]Michael Elkin, Ofer Neiman:
Distributed strong diameter network decomposition. Theor. Comput. Sci. 922: 150-157 (2022) - [c66]Michael Elkin, Chhaya Trehan:
(1+ε)-Approximate Shortest Paths in Dynamic Streams. APPROX/RANDOM 2022: 51:1-51:23 - [c65]Václav Rozhon, Michael Elkin, Christoph Grunau, Bernhard Haeupler:
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. FOCS 2022: 1114-1121 - [c64]Michael Elkin, Chhaya Trehan:
Brief Announcement: (1+ε)-Approximate Shortest Paths in Dynamic Streams. PODC 2022: 57-59 - [c63]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: 1-10 - [c62]Michael Elkin, Ofer Neiman:
Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication. STACS 2022: 27:1-27:22 - [c61]Michael Elkin, Yuval Gitlitz, Ofer Neiman:
Almost Shortest Paths with Near-Additive Error in Weighted Graphs. SWAT 2022: 23:1-23:22 - [i42]Michael Elkin, Bernhard Haeupler, Václav Rozhon, Christoph Grunau:
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications. CoRR abs/2204.08254 (2022) - [i41]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 abs/2204.14086 (2022) - 2021
- [j49]Michael Elkin, Ofer Neiman:
Near Isometric Terminal Embeddings for Doubling Metrics. Algorithmica 83(11): 3319-3337 (2021) - [c60]Michael Elkin, Shaked Matar:
Ultra-Sparse Near-Additive Emulators. PODC 2021: 235-246 - [c59]Michael Elkin, Shaked Matar:
Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work. SPAA 2021: 198-207 - [c58]Michael Elkin, Yuval Gitlitz, Ofer Neiman:
Improved Weighted Additive Spanners. DISC 2021: 21:1-21:15 - [i40]Michael Elkin, Shaked Matar:
Ultra-Sparse Near-Additive Emulators. CoRR abs/2106.01036 (2021) - [i39]Michael Elkin, Chhaya Trehan:
$(1+ε)$-Approximate Shortest Paths in Dynamic Streams. CoRR abs/2107.13309 (2021) - 2020
- [j48]Michael Elkin, Ofer Neiman:
Near-Additive Spanners and Near-Exact Hopsets, A Unified View. Bull. EATCS 130 (2020) - [j47]Michael Elkin:
A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities. J. ACM 67(2): 13:1-13:15 (2020) - [j46]Michael Elkin:
Distributed Exact Shortest Paths in Sublinear Time. J. ACM 67(3): 15:1-15:36 (2020) - [j45]Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman:
Ramsey Spanning Trees and Their Applications. ACM Trans. Algorithms 16(2): 19:1-19:21 (2020) - [c57]Michael Elkin, Arnold Filtser, Ofer Neiman:
Distributed Construction of Light Networks. PODC 2020: 483-492 - [c56]Michael Elkin, Ofer Neiman:
Lossless Prioritized Embeddings. SODA 2020: 1049-1062 - [i38]Michael Elkin, Ofer Neiman:
Near-Additive Spanners and Near-Exact Hopsets, A Unified View. CoRR abs/2001.07477 (2020) - [i37]Michael Elkin, Ofer Neiman:
Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication. CoRR abs/2004.07572 (2020) - [i36]Michael Elkin, Yuval Gitlitz, Ofer Neiman:
Improved Weighted Additive Spanners. CoRR abs/2008.09877 (2020) - [i35]Michael Elkin, Shaked Matar:
Deterministic PRAM Approximate Shortest Paths in Polylogarithmic Time and Slightly Super-Linear Work. CoRR abs/2009.14729 (2020)
2010 – 2019
- 2019
- [j44]Michael Elkin, Ofer Neiman:
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. SIAM J. Comput. 48(4): 1436-1480 (2019) - [j43]Michael Elkin, Ofer Neiman:
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. ACM Trans. Algorithms 15(1): 4:1-4:29 (2019) - [c55]Michael Elkin, Shaked Matar:
Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time. PODC 2019: 531-540 - [c54]Michael Elkin, Ofer Neiman:
Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC. SPAA 2019: 333-341 - [i34]Michael Elkin, Shaked Matar:
Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time. CoRR abs/1903.00872 (2019) - [i33]Michael Elkin, Arnold Filtser, Ofer Neiman:
Distributed Construction of Light Networks. CoRR abs/1905.02592 (2019) - [i32]Michael Elkin, Ofer Neiman:
Lossless Prioritized Embeddings. CoRR abs/1907.06983 (2019) - [i31]Michael Elkin, Shaked Matar:
Fast Deterministic Constructions of Linear-Size Spanners and Skeletons. CoRR abs/1907.10895 (2019) - [i30]Michael Elkin, Yuval Gitlitz, Ofer Neiman:
Almost Shortest Paths and PRAM Distance Oracles in Weighted Graphs. CoRR abs/1907.11422 (2019) - 2018
- [j42]Michael Elkin, Ofer Neiman:
On efficient distributed construction of near optimal routing schemes. Distributed Comput. 31(2): 119-137 (2018) - [j41]Michael Elkin, Arnold Filtser, Ofer Neiman:
Prioritized Metric Structures and Embedding. SIAM J. Comput. 47(3): 829-858 (2018) - [j40]Leonid Barenboim, Michael Elkin, Cyril Gavoille:
A fast network-decomposition algorithm and its applications to constant-time distributed computation. Theor. Comput. Sci. 751: 2-23 (2018) - [c53]Michael Elkin, Ofer Neiman:
Near Isometric Terminal Embeddings for Doubling Metrics. SoCG 2018: 36:1-36:15 - [c52]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: 437-446 - [c51]Michael Elkin:
Session details: Session 3D: Graphs and Population. PODC 2018 - [c50]Michael Elkin, Ofer Neiman:
Near-Optimal Distributed Routing with Low Memory. PODC 2018: 207-216 - [c49]Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman:
Ramsey Spanning Trees and their Applications. SODA 2018: 1650-1664 - [i29]Michael Elkin, Ofer Neiman:
Near Isometric Terminal Embeddings for Doubling Metrics. CoRR abs/1802.07967 (2018) - 2017
- [j39]Michael Elkin, Arnold Filtser, Ofer Neiman:
Terminal embeddings. Theor. Comput. Sci. 697: 1-36 (2017) - [c48]Michael Elkin:
A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities. PODC 2017: 157-163 - [c47]Leonid Barenboim, Michael Elkin, Tzalik Maimon:
Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity. PODC 2017: 175-184 - [c46]Michael Elkin, Ofer Neiman:
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. SODA 2017: 652-669 - [c45]Michael Elkin:
Distributed exact shortest paths in sublinear time. STOC 2017: 757-770 - [i28]Michael Elkin:
Distributed Exact Shortest Paths in Sublinear Time. CoRR abs/1703.01939 (2017) - [i27]Michael Elkin:
A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities. CoRR abs/1703.02411 (2017) - [i26]Michael Elkin, Ofer Neiman:
Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory. CoRR abs/1704.08468 (2017) - [i25]Ittai Abraham, Shiri Chechik, Michael Elkin, Arnold Filtser, Ofer Neiman:
Ramsey Spanning Trees and their Applications. CoRR abs/1707.08769 (2017) - [i24]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 abs/1712.00285 (2017) - 2016
- [j38]Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider:
The Locality of Distributed Symmetry Breaking. J. ACM 63(3): 20:1-20:45 (2016) - [j37]Michael Elkin, Shay Solomon:
Fast Constructions of Lightweight Spanners for General Graphs. ACM Trans. Algorithms 12(3): 29:1-29:21 (2016) - [j36]Michael Elkin, Seth Pettie:
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. ACM Trans. Algorithms 12(4): 50:1-50:31 (2016) - [j35]Boaz Ben-Moshe, Michael Elkin, Lee-Ad Gottlieb, Eran Omri:
Optimizing budget allocation for center and median points. Theor. Comput. Sci. 627: 13-25 (2016) - [j34]Michael Elkin, Ofer Neiman, Christian Wulff-Nilsen:
Space-efficient path-reporting approximate distance oracles. Theor. Comput. Sci. 651: 1-10 (2016) - [c44]Michael Elkin, Ofer Neiman:
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. FOCS 2016: 128-137 - [c43]Michael Elkin, Ofer Neiman:
Distributed Strong Diameter Network Decomposition: Extended Abstract. PODC 2016: 211-216 - [c42]Michael Elkin, Ofer Neiman:
On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract. PODC 2016: 235-244 - [r6]Michael Elkin:
Low Stretch Spanning Trees. Encyclopedia of Algorithms 2016: 1156-1159 - [r5]Michael Elkin:
Sparse Graph Spanners. Encyclopedia of Algorithms 2016: 2041-2043 - [r4]Michael Elkin:
Synchronizers, Spanners. Encyclopedia of Algorithms 2016: 2189-2191 - [i23]Michael Elkin, Ofer Neiman:
On Efficient Distributed Construction of Near Optimal Routing Schemes. CoRR abs/1602.02293 (2016) - [i22]Michael Elkin, Ofer Neiman:
Distributed Strong Diameter Network Decomposition. CoRR abs/1602.05437 (2016) - [i21]Michael Elkin, Arnold Filtser, Ofer Neiman:
Terminal Embeddings. CoRR abs/1603.02321 (2016) - [i20]Michael Elkin, Ofer Neiman:
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths. CoRR abs/1605.04538 (2016) - [i19]Michael Elkin, Ofer Neiman:
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators. CoRR abs/1607.08337 (2016) - [i18]Leonid Barenboim, Michael Elkin, Tzalik Maimon:
Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity. CoRR abs/1610.06759 (2016) - 2015
- [j33]Michael Elkin, Shay Solomon:
Optimal Euclidean Spanners: Really Short, Thin, and Lanky. J. ACM 62(5): 35:1-35:45 (2015) - [j32]Michael Elkin, Shay Solomon:
Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones. SIAM J. Comput. 44(4): 996-1025 (2015) - [j31]Michael Elkin, Ofer Neiman, Shay Solomon:
Light Spanners. SIAM J. Discret. Math. 29(3): 1312-1321 (2015) - [c41]Michael Elkin, Arnold Filtser, Ofer Neiman:
Terminal Embeddings. APPROX-RANDOM 2015: 242-264 - [c40]Leonid Barenboim, Michael Elkin, Cyril Gavoille:
A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation - (Extended Abstract). SIROCCO 2015: 209-223 - [c39]Michael Elkin, Seth Pettie, Hsin-Hao Su:
(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. SODA 2015: 355-370 - [c38]Michael Elkin, Seth Pettie:
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. SODA 2015: 805-821 - [c37]Michael Elkin, Arnold Filtser, Ofer Neiman:
Prioritized Metric Structures and Embedding. STOC 2015: 489-498 - [i17]Michael Elkin, Arnold Filtser, Ofer Neiman:
Prioritized Metric Structures and Embedding. CoRR abs/1502.05543 (2015) - [i16]Leonid Barenboim, Michael Elkin, Cyril Gavoille:
A Fast Network-Decomposition Algorithm and its Applications to Constant-Time Distributed Computation. CoRR abs/1505.05697 (2015) - [i15]Michael Elkin, Seth Pettie:
A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. CoRR abs/1506.08392 (2015) - 2014
- [j30]Leonid Barenboim, Michael Elkin:
Combinatorial algorithms for distributed graph coloring. Distributed Comput. 27(2): 79-93 (2014) - [j29]Leonid Barenboim, Michael Elkin, Fabian Kuhn:
Distributed (Delta+1)-Coloring in Linear (in Delta) Time. SIAM J. Comput. 43(1): 72-95 (2014) - [j28]Shay Solomon, Michael Elkin:
Balancing Degree, Diameter, and Weight in Euclidean Spanners. SIAM J. Discret. Math. 28(3): 1173-1198 (2014) - [c36]Michael Elkin, Ofer Neiman, Shay Solomon:
Light Spanners. ICALP (1) 2014: 442-452 - [c35]Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan:
Can quantum communication speed up distributed computation? PODC 2014: 166-175 - [i14]Michael Elkin, Ofer Neiman, Shay Solomon:
Light Spanners. CoRR abs/1404.7703 (2014) - [i13]Boaz Ben-Moshe, Michael Elkin, Lee-Ad Gottlieb, Eran Omri:
Optimizing Budget Allocation in Graphs. CoRR abs/1406.2107 (2014) - [i12]Michael Elkin, Ofer Neiman, Christian Wulff-Nilsen:
Space-Efficient Path-Reporting Approximate Distance Oracles. CoRR abs/1410.0768 (2014) - 2013
- [b1]Leonid Barenboim, Michael Elkin:
Distributed Graph Coloring: Fundamentals and Recent Developments. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers 2013, ISBN 9781627050180, pp. 1-171 - [j27]Leonid Barenboim, Michael Elkin:
Distributed deterministic edge coloring using bounded neighborhood independence. Distributed Comput. 26(5-6): 273-287 (2013) - [j26]Johannes Schneider, Michael Elkin, Roger Wattenhofer:
Symmetry breaking depending on the chromatic number or the neighborhood growth. Theor. Comput. Sci. 509: 40-50 (2013) - [c34]Michael Elkin, Shay Solomon:
Fast Constructions of Light-Weight Spanners for General Graphs. SODA 2013: 513-525 - [c33]Michael Elkin, Shay Solomon:
Optimal euclidean spanners: really short, thin and lanky. STOC 2013: 645-654 - 2012
- [c32]Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider:
The Locality of Distributed Symmetry Breaking. FOCS 2012: 321-330 - [i11]Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider:
Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set. CoRR abs/1202.1983 (2012) - [i10]Michael Elkin, Shay Solomon:
Fast Constructions of Light-Weight Spanners for General Graphs. CoRR abs/1207.1668 (2012) - [i9]Michael Elkin, Shay Solomon:
Optimal Euclidean spanners: really short, thin and lanky. CoRR abs/1207.1831 (2012) - [i8]Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan:
Quantum Distributed Network Computing: Lower Bounds and Techniques. CoRR abs/1207.5211 (2012) - 2011
- [j25]Leonid Barenboim, Michael Elkin:
Deterministic Distributed Vertex Coloring in Polylogarithmic Time. J. ACM 58(5): 23:1-23:25 (2011) - [j24]Michael Elkin, Shay Solomon:
Narrow-Shallow-Low-Light Trees with and without Steiner Points. SIAM J. Discret. Math. 25(1): 181-210 (2011) - [j23]Michael Elkin:
Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms 7(2): 20:1-20:17 (2011) - [j22]Michael Elkin, Yuval Lando, Zeev Nutov, Michael Segal, Hanan Shpungin:
Novel algorithms for the network lifetime problem in wireless settings. Wirel. Networks 17(2): 397-410 (2011) - [c31]Boaz Ben-Moshe, Eran Omri, Michael Elkin:
Optimizing Budget Allocation in Graphs. CCCG 2011 - [c30]Michael Elkin, Shay Solomon:
Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones. FOCS 2011: 373-382 - [c29]Leonid Barenboim, Michael Elkin:
Distributed deterministic edge coloring using bounded neighborhood independence. PODC 2011: 129-138 - [c28]Leonid Barenboim, Michael Elkin:
Combinatorial Algorithms for Distributed Graph Coloring. DISC 2011: 66-81 - [i7]Shay Solomon, Michael Elkin:
Balancing Degree, Diameter and Weight in Euclidean Spanners. CoRR abs/1108.6022 (2011) - 2010
- [j21]Leonid Barenboim, Michael Elkin:
Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distributed Comput. 22(5-6): 363-379 (2010) - [j20]Yefim Dinitz, Michael Elkin, Shay Solomon:
Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. Discret. Comput. Geom. 43(4): 736-783 (2010) - [c27]Shay Solomon, Michael Elkin:
Balancing Degree, Diameter and Weight in Euclidean Spanners. ESA (1) 2010: 48-59 - [c26]Leonid Barenboim, Michael Elkin:
Deterministic distributed vertex coloring in polylogarithmic time. PODC 2010: 410-419 - [c25]Michael Elkin:
An Improved Construction of Progression-Free Sets. SODA 2010: 886-905 - [i6]Leonid Barenboim, Michael Elkin:
Deterministic Distributed Vertex Coloring in Polylogarithmic Time. CoRR abs/1003.1608 (2010) - [i5]Leonid Barenboim, Michael Elkin:
Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence. CoRR abs/1010.2454 (2010)
2000 – 2009
- 2009
- [c24]Michael Elkin, Shay Solomon:
Narrow-Shallow-Low-Light Trees with and without Steiner Points. ESA 2009: 215-226 - [c23]