Prof. Michael Elkin

elkinm foto Professor

Research: My research focuses in graph algorithms, including distributed, parallel and streaming algorithms.
In the realm of distributed algorithms I study both global problems, such as constructions of minimum spanning trees, and local ones, such as graph colorings, and computation of small dominating sets, and spanners. I am also very interested in metric data structures, both algorithmic, graphic, and ones obtained via metric embeddings.

Contacts

Email:
Homepage:
Office: 217 in 37 building
Phone number: 08-6477884
Fax number: 08-6477650
Box number: 34
Office hours: Tue 14:00-16:00

Teaching

Fall 2018-2019 20226211 Metric Graph Algorithms
Fall 2018-2019 20214071 Mini-Project on Low-Distortion Embeddings
Spring 2019 20211031 Data Structures
Fall 2017-2018 20225811 Distributed Algorithms
Fall 2017-2018 20214071 Mini-Project on Low-Distortion Embeddings
Spring 2018 20211031 Data Structures
Fall 2016-2017 20225811 Distributed Algorithms
Fall 2016-2017 20214071 Mini-Project on Low-Distortion Embeddings
Spring 2017 20211031 Data Structures
Spring 2017 20214381 Mini-Project in Distributed Computing
Fall 2014-2015 20214071 Mini-Project on Low-Distortion Embeddings
Fall 2014-2015 20225811 Distributed Algorithms
Spring 2015 20214331 Mini-Project on distributed algorithms for channel allocation
Spring 2015 20211051 Data Structures for Information Systems
Fall 2013-2014 20214331 Mini-Project on distributed algorithms for channel allocation
Fall 2013-2014 20225811 Distributed Algorithms
Fall 2013-2014 20221561 Theory Seminar
Spring 2014 20214071 Mini-Project on Low-Distortion Embeddings
Spring 2014 20212041 Design of Algorithms
Fall 2012-2013 20225811 Distributed Algorithms
Spring 2013 20214071 Mini-Project on Low-Distortion Embeddings
Spring 2013 20212041 Design of Algorithms
Fall 2011-2012 20214071 Mini-Project on Low-Distortion Embeddings
Fall 2011-2012 20215371 Distributed Algorithms
Fall 2010-2011 20214071 Mini-Project on Low-Distortion Embeddings
Fall 2010-2011 20215371 Distributed Algorithms
Spring 2011 20212041 Design of Algorithms
Fall 2009-2010 20214071 Mini-Project on Low-Distortion Embeddings
Fall 2009-2010 20215371 Distributed Algorithms
Spring 2010 20212041 Design of Algorithms
Fall 2008-2009 20215371 Distributed Algorithms
Fall 2008-2009 20214071 Mini-Project on Low-Distortion Embeddings
Spring 2009 20211051 Data Structures for Information Systems
Spring 2009 20215611 Seminar in Computer Science
Fall 2007-2008 20214071 Mini-Project on Low-Distortion Embeddings
Fall 2007-2008 20221511 Advanced Seminar A
Spring 2008 20012041 Design of Algorithms for IAF
Spring 2008 20211031 Data Structures
Fall 2006-2007 20215371 Distributed Algorithms
Spring 2007 20214071 Mini-Project on Low-Distortion Embeddings
Spring 2007 20225081 Seminar Distributed and Parallel Algorithms
Summer 2007 20011031 Data Structures for IAF
Fall 2005-2006 20214071 Mini-Project on Low-Distortion Embeddings
Fall 2005-2006 20215371 Distributed Algorithms
Spring 2006 20211051 Data Structures for Information Systems
Spring 2006 20012041 Design of Algorithms for IAF
Spring 2006 20214101 Topics in Algorithims
Fall 2004-2005 20214071 Mini-Project on Low-Distortion Embeddings
Fall 2004-2005 20215371 Distributed Algorithms
Spring 2005 20012041 Design of Algorithms for IAF

Research groups

Algorithms
Communication Networks and Algorithms
Complexity
Distributed Algorithms
Low Distortion Embeddings

Selected publications all BibTex

 
Articles
M. Elkin and D. Peleg. (1+e,b)-Spanner Constructions for general graphs. SIAM Journal on Computing, 33(3):608-631.
M. Elkin and G. Kortsarz. A Sublogarithmic Approximation Algorithm for the Telephone Multicast Problem. Journal of Computer and System Sciences, 72(4):648-659, June 2006.
M. Elkin and J. Zhang. Efficient algorithms for Constructing (1+e,b)-spanners in the Distributed and Streaming Models. Distributed Computing, 18(5):375-385, 2006.
M. Elkin and G. Kortsarz. Approximation Algorithm for the Directed Telephone Multicast Problem. Algorithmica, 2006.
M. Elkin. Computing almost shortest paths. Transactions on Algorithms, 1(2):283-323, 2005.
M. Elkin and D. Peleg. Approximating k-spanner problems for k > 2. Theoretical Computer Science, 337:249-277, 2005.
M. Elkin and G. Kortsarz. Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem. SIAM Journal on Discrete Mathematics, 19(4):881-899, 2005.
B. Bollobas, D. Coppersmith and M. Elkin. Sparse Distance Preservers and Additive Spanners. SIAM Journal of Discrete Mathematics, 19(4):1029-1055, 2005.
M. Elkin and G.Kortsarz. Combinatorial Logarithmic Algorithm for Directed Telephone Broadcast Problem. SIAM Journal on Computing, 35(3):672-689, 2005.
M. Elkin . An Overview of Distributed Algorithms. ACM SIGACT News Distributed Computing Column , 35(4):40-57, 2004.
M. Elkin and G. Kortsarz. Logarithmic Inapproximability of the Radio Broadcast Problem. Journal of Algorithms, 52(1):8-25, 2004.
 
Conference Articles
M. Elkin and J. Zhang. Efficient Algorithms for Constructing (1+e,b)-Spanners in Distributed and Streaming Models. In Proc. of ACM SIGACT-SIGOPS Symp. on Principles of DIstributed Computing, 2004:160-168.
D. Coppersmith and M. Elkin. Sparse Distance Preservers and Additive Spanners. In Proc. of ACM-SIAM Symp. on Discr. Algorithms, 2005.
M. Elkin and G. Kortsarz. Improved Upper Bound for the Radio Broadcast. In Proc. of ACM-SIAM Symp. on Discr. Algorithms, 2005.
M. Elkin, Y. Emek, D. Spielman, S. Teng. Lower Stretch Spanning Trees. In Proceedings of ACM Symposium on Theory of Computing, STOC`05, 2005.
M. Elkin. Unconditional Lower Bounds on the Time-Approximation Tradeoff of the Distributed Minimum Spanning Tree Problem. In Proc. 36th Annual ACM Symp. on Theory of Computing, pages 331-340, 2004.
M. Elkin. A Faster Distributed Algorithm for Constructing a Mnimum Spanning Tree. In Proc. ACM-SIAM Symp. on Discr. Algorithms, pages 352-361, 2004.
M. Elkin and G. Kortsarz. Polylogarithmic Inapproximability of the Radio Broadcast Problem. In Proc. of the 7th Intern. Workshop on Approx. Algorithms for Combinatorial Optimization Problems, pages 105-114, 2004.
M. Elkin and G. Kortsarz. Sublogarithmic Approximation for Telephone Multicast. In Proc. of ACM-SIAM Symp. on Discr. Algorithms, pages 76-85, 2003.
M. Elkin and G. Kortsarz. Approximation Algorithm for the Directed Telephone Multicast Problem. In Proc. of Intern. Colloq. on Automata, Languages and Programming, pages 212-223, 2003.
B. Bollobas, D. Coppersmith, M. Elkin. Spasrse Subgraphs that Preserve Large Distances and Additive Spanners. In Proc. of ACM-SIAM Symp. on Discr. Algorithms, pages 414-423, 2003.
M. Elkin and G. Kortsarz. Combinatorial Logarithmic Approximation Algorithm for Directed Broadcast Problem. In Proc. Ann. ACM Symp. on Theory of Computing, pages 438-447, 2002.
M. Elkin and D. Peleg. Approximating k-spanner for k > 2. In Proc. Conference on Integer Programming and Comb. Optimization, pages 90-104, 2001.
M. Elkin. Computing Almost Shortest Paths. In Proc. of ACM Symp. on Distr. Computing, pages 173-182, 2001.
M. Elkin and D. Peleg. Approximating k-spanner problems for k> 2. In Proc. 8th Conference in Integer Programming and Combinatorial Optimization, IPCO 2001, pages 90-104, 2001.
M. Elkin and D. Peleg. The Client-Server 2-Spanner problem. In Proc. Colloq. on Struct. Info. and Comm. Complexity, 2001.
Michael Elkin. Computing Almost Shortest Paths. In Proc. ACM Symp. on Principles of Distrib. Computing, pages 53-62, 2001.
M. Elkin and D. Peleg. (1+e,b)-Spanner Constructions for General Graphs. In Proc. of ACM Ann. Symp. on Theory of Computing, pages 173-182, 2001.
M. Elkin and D. Peleg. Strong Inapproximability of the Basic k-Spanner Problem. In Proc. of Int. Colloq. on Automata, Languages and Progr., pages 636-648, 2000.
M. Elkin and D. Peleg. The Hardness of Approximating Spanner Problems. In Proc. Symp. on theoretical Aspects of Computer Science, pages 370-381, 2000.