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
- 1 Similar Profiles
Collaborations and top research areas from the last five years
-
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 Access3 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
7 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
4 Scopus citations -
Brief Announcement: (1+)-Approximate Shortest Paths in Dynamic Streams.
Elkin, M. & Trehan, C., 20 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
-
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
6 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
2 Scopus citations -
Linear-Size hopsets with small hopbound, and constant-hopbound hopsets in RNC
Elkin, M. & Neiman, O., 1 Oct 2022, In: Distributed Computing. 35, 5, p. 419-437 19 p.Research output: Contribution to journal › Article › peer-review
-
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
-