Research output per year
Research output per year
Personal profile
Research interests
- Generally, I am interested in Theoretical Computer Science (TCS) and Discrete Mathematics. In particular, I am interested in:
Graph Algorithms
Low-Distortion Embeddings
Distributed and Parallel Graph Algorithms
Streaming Graph Algorithms
Dynamic (Centralized and Distributed) Graph Algorithms
Approximation Algorithms and Hardness of Approximation
Discrete Mathematics, Combinatorial and Computational Geometry
Additive Number Theory
Fingerprint
Dive into the research topics where Michael Elkin is active. These topic labels come from the works of this person. Together they form a unique fingerprint.
- 1 Similar Profiles
Collaborations and top research areas from the last five years
Recent external collaboration on country/territory level. Dive into details by clicking on the dots or
-
Efficient Parallel (Δ+ 1)-Edge-Coloring
Khuzman, A. & Elkin, M., 8 Jul 2026, Proceedings of the 38th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA 26. Association for Computing Machinery, p. 62-74 13 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Improved weighted additive spanners
Elkin, M., Gitlitz, Y. & Neiman, O., 1 Sep 2023, In: Distributed Computing. 36, 3, p. 385-394 10 p.Research output: Contribution to journal › Article › peer-review
Open Access4 Scopus citations -
Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n log log n)
Elkin, M. & Shabat, I., 1 Jan 2023, Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. Institute of Electrical and Electronics Engineers, p. 2278-2311 34 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
9 Scopus citations -
(1 + ϵ)-Approximate Shortest Paths in Dynamic Streams
Elkin, M. & Trehan, C., 1 Sep 2022, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2022. Chakrabarti, A. & Swamy, C. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 51. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 245).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
4 Scopus citations -
Almost Shortest Paths with Near-Additive Error in Weighted Graphs
Elkin, M., Gitlitz, Y. & Neiman, O., 1 Jun 2022, 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022. Czumaj, A. & Xin, Q. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 23. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 227).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
5 Scopus citations -
Brief Announcement: (1+)-Approximate Shortest Paths in Dynamic Streams.
Elkin, M. & Trehan, C., 21 Jul 2022, PODC 2022 - Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing. Association for Computing Machinery, p. 57-59 3 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Centralized, Parallel, and Distributed Multi-Source Shortest Paths via Hopsets and Rectangular Matrix Multiplication
Elkin, M. & Neiman, O., 1 Mar 2022, 39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022. Berenbrink, P. & Monmege, B. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 27. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 219).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
7 Scopus citations -
Deterministic Distributed Sparse and Ultra-Sparse Spanners and Connectivity Certificates
Bezdrighin, M., Elkin, M., Ghaffari, M., Grunau, C., Haeupler, B., Ilchi, S. & RozhoÅ, V., 11 Jul 2022, SPAA 2022 - Proceedings of the 34th ACM Symposium on Parallelism in Algorithms and Architectures. Association for Computing Machinery, p. 1-10 10 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
7 Scopus citations -
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
Rozhon, V., Elkin, M., Grunau, C. & Haeupler, B., 1 Jan 2022, Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022. Institute of Electrical and Electronics Engineers, p. 1114-1121 8 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; vol. 2022-October).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
14 Scopus citations -
Distributed strong diameter network decomposition
Elkin, M. & Neiman, O., 24 Jun 2022, In: Theoretical Computer Science. 922, p. 150-157 8 p.Research output: Contribution to journal › Article › peer-review
Open Access3 Scopus citations
-
Metric Structures for Graph Sparsification and Augmentation
Elkin, M. (PI)
1/01/25 → 31/12/29
Project: Research
-
-
-
Locality in Distributed Computing
Barenboim, L. (PI) & Elkin, M. (CoPI)
1/01/15 → 31/12/18
Project: Research
-
Distributed Graph Coloring, MIS, and Related Problems
Elkin, M. (PI)
1/01/11 → 31/12/14
Project: Research
-