Research output per year
Research output per year
- 1 - 50 out of 83 results
Search results
-
2023
Improved weighted additive spanners
Elkin, M., Gitlitz, Y. & Neiman, O., 1 Sep 2023, In: Distributed Computing. 36, 3, p. 385-394 10 p.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
-
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. p. 2278-2311 34 p. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
-
2022
(1 + ϵ)-Approximate Shortest Paths in Dynamic Streams
Elkin, M. & Trehan, C., 15 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, p. 51:1--51:23 51. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 245).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
-
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).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
-
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. p. 57-59 3 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).Ben-Gurion University of the Negev
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., 9 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, Vol. 219. p. 27:1-27:22 (Leibniz International Proceedings in Informatics, LIPIcs; vol. 219).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
-
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. p. 1-10 10 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Deterministic Low-Diameter Decompositions for Weighted Graphs and Distributed and Parallel Applications
Rozhon, V., Elkin, M., Grunau, C. & Haeupler, B., 28 Dec 2022, Proceedings - 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science, FOCS 2022. p. 1114-1121 8 p.Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
-
Distributed strong diameter network decomposition
Elkin, M. & Neiman, O., 24 Jun 2022, In: Theoretical Computer Science. 922, p. 150-157 8 p.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
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.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
-
Locally-iterative Distributed (Δ + 1)-coloring and Applications.
Barenboim, L., Elkin, M. & Goldenberg, U., 1 Feb 2022, In: Journal of the ACM. 69, 1, p. 5:1-5:26 26 p., 5.Open University of Israel, Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
-
LOSSLESS PRIORITIZED EMBEDDINGS
Elkin, M. & Neiman, O., 1 Jan 2022, In: SIAM Journal on Discrete Mathematics. 36, 3, p. 1529-1550 22 p.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
2021
Centralized and Parallel Multi-Source Shortest Paths via Hopsets and Fast Matrix Multiplication
Elkin, M. & Neiman, O., 12 Feb 2021.Ben-Gurion University of the Negev
Research output: Working paper › Preprint
Open Access -
Deterministic PRAM approximate shortest paths in polylogarithmic time and slightly super-linear work
Elkin, M. & Matar, S., 6 Jul 2021, SPAA 2021 - Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures. p. 198-207 10 p. (Annual ACM Symposium on Parallelism in Algorithms and Architectures).Ben-Gurion University of the Negev
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 Oct 2021, 35th International Symposium on Distributed Computing, DISC 2021. Gilbert, S. (ed.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 21. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 209).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
-
Near Isometric Terminal Embeddings for Doubling Metrics
Elkin, M. & Neiman, O., 1 Nov 2021, In: Algorithmica. 83, 11, p. 3319-3337 19 p.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
-
Ultra-Sparse Near-Additive Emulators
Elkin, M. & Matar, S., 21 Jul 2021, PODC 2021 - Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. p. 235-246 12 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
2020
A Simple Deterministic Distributed MST Algorithm with Near-Optimal Time and Message Complexities
Elkin, M., 4 May 2020, In: Journal of the ACM. 67, 2, 13.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
Distributed Construction of Light Networks
Elkin, M., Filtser, A. & Neiman, O., 31 Jul 2020, PODC 2020 - Proceedings of the 39th Symposium on Principles of Distributed Computing. p. 483-492 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Distributed Exact Shortest Paths in Sublinear Time
Elkin, M., 1 May 2020, In: Journal of the ACM. 67, 3, 15.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
Lossless prioritized embeddings
Elkin, M. & Neiman, O., 1 Jan 2020, 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. Chawla, S. (ed.). p. 1049-1062 14 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 2020-January).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Near-Additive Spanners and Near-Exact Hopsets, A Unified View
Elkin, M. & Neiman, O., 21 Jan 2020.Ben-Gurion University of the Negev
Research output: Working paper › Preprint
Open Access -
Ramsey Spanning Trees and Their Applications
Abraham, I., Chechik, S., Elkin, M., Filtser, A. & Neiman, O., 1 Apr 2020, In: ACM Transactions on Algorithms. 16, 2, 19.Tel Aviv University, Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
2019
Almost Shortest Paths and PRAM Distance Oracles in Weighted Graphs.
Elkin, M., Gitlitz, Y. & Neiman, O., 2019.Ben-Gurion University of the Negev
Research output: Working paper › Preprint
Open Access -
Fast Deterministic Constructions of Linear-Size Spanners and Skeletons
Elkin, M. & Matar, S., 2019.Ben-Gurion University of the Negev
Research output: Working paper › Preprint
-
Hopsets with constant hopbound, and applications to approximate shortest paths
Elkin, M. & Neiman, O., 1 Jan 2019, In: SIAM Journal on Computing. 48, 4, p. 1436-1480 45 p.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
Linear-size hopsets with small hopbound, and constant-hopbound hopsets in RNC
Elkin, M. & Neiman, O., 17 Jun 2019, SPAA 2019 - Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures. p. 333-341 9 p.Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
-
Near-Additive Spanners in Low Polynomial Deterministic CONGEST Time
Elkin, M. & Matar, S., 16 Jul 2019, PODC 2019 - Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. p. 531-540 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
2018
A fast network-decomposition algorithm and its applications to constant-time distributed computation
Barenboim, L., Elkin, M. & Gavoille, C., 3 Dec 2018, In: Theoretical Computer Science. 751, p. 2-23 22 p.Open University of Israel, Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
Efficient algorithms for constructing very sparse spanners and emulators
Elkin, M. & Neiman, O., 1 Jan 2018, In: ACM Transactions on Algorithms. 15, 1, p. 4:1-4:29Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
Locally-iterative distributed (∆ + 1)-coloring below szegedy-vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models
Barenboim, L., Elkin, M. & Goldenberg, U., 23 Jul 2018, PODC 2018 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. p. 437-446 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).Open University of Israel, Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
-
Near isometric terminal embeddings for doubling metrics
Elkin, M. & Neiman, O., 1 Jun 2018, 34th International Symposium on Computational Geometry, SoCG 2018. Toth, C. D. & Speckmann, B. (eds.). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, p. 361-3615 3255 p. (Leibniz International Proceedings in Informatics, LIPIcs; vol. 99).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
-
Near-optimal distributed routing with low memory
Elkin, M. & Neiman, O., 23 Jul 2018, PODC 2018 - Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing. p. 207-216 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
-
On efficient distributed construction of near optimal routing schemes
Elkin, M. & Neiman, O., 1 Apr 2018, In: Distributed Computing. 31, 2, p. 119-137 19 p.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
-
Prioritized metric structures and embedding
Elkin, M., Filtser, A. & Neiman, O., 1 Jan 2018, In: SIAM Journal on Computing. 47, 3, p. 829-858 30 p.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
Ramsey spanning trees and their applications
Abraham, I., Chechik, S., Elkin, M., Filtser, A. & Neiman, O., 1 Jan 2018, 29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Czumaj, A. (ed.). p. 1650-1664 15 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).Ben-Gurion University of the Negev, Tel Aviv University
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Session details: Session 3D: Graphs and Population
Elkin, M., 23 Jul 2018.Ben-Gurion University of the Negev
Research output: Contribution to conference › Paper › peer-review
-
2017
A simple deterministic distributed MST algorithm, with near-optimal time and message complexities
Elkin, M., 26 Jul 2017, PODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing. p. 157-163 7 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; vol. Part F129314).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Deterministic distributed (Δ + o(Δ))-edge-coloring, and vertex-coloring of graphs with bounded diversity
Beranboim, L., Elkin, M. & Maimon, T., 26 Jul 2017, PODC 2017 - Proceedings of the ACM Symposium on Principles of Distributed Computing. p. 175-184 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; vol. Part F129314).Open University of Israel, Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Distributed exact shortest paths in sublinear time?
Elkin, M., 19 Jun 2017, STOC 2017 - Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing. McKenzie, P., King, V. & Hatami, H. (eds.). p. 757-770 14 p. (Proceedings of the Annual ACM Symposium on Theory of Computing; vol. Part F128415).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Efficient algorithms for constructing very sparse spanners and emulators
Elkin, M. & Neiman, O., 1 Jan 2017, 28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017. Klein, P. N. (ed.). p. 652-669 18 p. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; vol. 0).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Terminal embeddings
Elkin, M., Filtser, A. & Neiman, O., 12 Oct 2017, In: Theoretical Computer Science. 697, p. 1-36 36 p.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
2016
A linear-size logarithmic stretch path-reporting distance oracle for general graphs
Elkin, M. & Pettie, S., 1 Aug 2016, In: ACM Transactions on Algorithms. 12, 4, 50.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
Distributed strong diameter network decomposition: [Extended Abstract]
Elkin, M. & Neiman, O., 25 Jul 2016, PODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing. p. 211-216 6 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; vol. 25-28-July-2016).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Fast constructions of lightweight spanners for general graphs
Elkin, M. & Solomon, S., 1 Apr 2016, In: ACM Transactions on Algorithms. 12, 3, 29.Ben-Gurion University of the Negev, Tel Aviv University
Research output: Contribution to journal › Article › peer-review
Open Access -
Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths
Elkin, M. & Neiman, O., 14 Dec 2016, Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016. Vol. 2016-December. p. 128-137 10 p. 7782925Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
On efficient distributed construction of near optimal routing schemes: [Extended Abstract]
Elkin, M. & Neiman, O., 25 Jul 2016, PODC 2016 - Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing. p. 235-244 10 p. (Proceedings of the Annual ACM Symposium on Principles of Distributed Computing; vol. 25-28-July-2016).Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Open Access -
Optimizing budget allocation for center and median points
Ben-Moshe, B., Elkin, M., Gottlieb, L. A. & Omri, E., 9 May 2016, In: Theoretical Computer Science. 627, p. 13-25 13 p.Ariel University, Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
Space-efficient path-reporting approximate distance oracles
Elkin, M., Neiman, O. & Wulff-Nilsen, C., 25 Oct 2016, In: Theoretical Computer Science. 651, p. 1-10 10 p.Ben-Gurion University of the Negev
Research output: Contribution to journal › Article › peer-review
Open Access -
Sparse Graph Spanners
Elkin, M., 2016, Encyclopedia of Algorithms. Kao, M.-Y. (ed.). 2 ed. Springer New York, p. 2041-2043 3 p.Ben-Gurion University of the Negev
Research output: Chapter in Book/Report/Conference proceeding › Entry for encyclopedia/dictionary › peer-review