Prof. Michael Elkin

elkinm foto Assistant professor

Contacts

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

Teaching

Fall 2004-2005 20215371 Distributed Algorithms
Fall 2004-2005 20214071 Mini Project on Low-Distortion Embeddings
Spring 2005 20012041 Design of Algorithms for IAF
Fall 2005-2006 20215371 Distributed Algorithms
Fall 2005-2006 20214071 Mini Project on Low-Distortion Embeddings
Spring 2006 20012041 Design of Algorithms for IAF
Spring 2006 20211051 Data Structures for Information Systems
Spring 2006 20214101 Topics in Algorithims
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 Structure for IAF
Fall 2007-2008 20221511 Advanced Seminar A
Fall 2007-2008 20214071 Mini Project on Low-Distortion Embeddings
Spring 2008 20012041 Design of Algorithms for IAF
Spring 2008 20211031 Data Structures
Fall 2008-2009 20214071 Mini Project on Low-Distortion Embeddings
Fall 2008-2009 20215371 Distributed Algorithms
Spring 2009 20211051 Data Structures for Information Systems
Spring 2009 20215611 Seminar in Computer Science
Fall 2009-2010 20214071 Mini Project on Low-Distortion Embeddings
Fall 2009-2010 20215371 Distributed Algorithms
Spring 2010 20212041 Design of Algorithms
Fall 2010-2011 20214071 Mini Project on Low-Distortion Embeddings
Fall 2010-2011 20215371 Distributed Algorithms
Spring 2011 20212041 Design of Algorithms
Fall 2011-2012 20215371 Distributed Algorithms
Fall 2011-2012 20214071 Mini Project on Low-Distortion Embeddings
Fall 2012-2013 20225811 Distributed Algorithms
Spring 2013 20214071 Mini Project on Low-Distortion Embeddings
Spring 2013 20212041 Design of Algorithms

Research groups

Algorithms
Communication networks
Complexity

Selected publications all BibTex

 
Articles
BibTeX
M. Elkin and D. Peleg. (1+e,b)-Spanner Constructions for general graphs. SIAM Journal on Computing, 33(3):608-631.
BibTeX
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.
BibTeX
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.
BibTeX
M. Elkin and G. Kortsarz. Approximation Algorithm for the Directed Telephone Multicast Problem. Algorithmica, 2006.
BibTeX
M. Elkin. Computing almost shortest paths. Transactions on Algorithms, 1(2):283-323, 2005.
BibTeX
M. Elkin and D. Peleg. Approximating k-spanner problems for k > 2. Theoretical Computer Science, 337:249-277, 2005.
BibTeX
M. Elkin and G. Kortsarz. Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem. SIAM Journal on Discrete Mathematics, 19(4):881-899, 2005.
BibTeX
B. Bollobas, D. Coppersmith and M. Elkin. Sparse Distance Preservers and Additive Spanners. SIAM Journal of Discrete Mathematics, 19(4):1029-1055, 2005.
BibTeX
M. Elkin and G.Kortsarz. Combinatorial Logarithmic Algorithm for Directed Telephone Broadcast Problem. SIAM Journal on Computing, 35(3):672-689, 2005.
BibTeX
M. Elkin . An Overview of Distributed Algorithms. ACM SIGACT News Distributed Computing Column , 35(4):40-57, 2004.
BibTeX
M. Elkin and G. Kortsarz. Logarithmic Inapproximability of the Radio Broadcast Problem. Journal of Algorithms, 52(1):8-25, 2004.
 
Conference Articles
BibTeX
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.
BibTeX
D. Coppersmith and M. Elkin. Sparse Distance Preservers and Additive Spanners. In Proc. of ACM-SIAM Symp. on Discr. Algorithms, 2005.
BibTeX
M. Elkin and G. Kortsarz. Improved Upper Bound for the Radio Broadcast. In Proc. of ACM-SIAM Symp. on Discr. Algorithms, 2005.
BibTeX
M. Elkin, Y. Emek, D. Spielman, S. Teng. Lower Stretch Spanning Trees. In Proceedings of ACM Symposium on Theory of Computing, STOC`05, 2005.
BibTeX
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.
BibTeX
M. Elkin. A Faster Distributed Algorithm for Constructing a Mnimum Spanning Tree. In Proc. ACM-SIAM Symp. on Discr. Algorithms, pages 352-361, 2004.
BibTeX
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.
BibTeX
M. Elkin and G. Kortsarz. Sublogarithmic Approximation for Telephone Multicast. In Proc. of ACM-SIAM Symp. on Discr. Algorithms, pages 76-85, 2003.
BibTeX
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.
BibTeX
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.
BibTeX
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.
BibTeX
M. Elkin and D. Peleg. Approximating k-spanner for k > 2. In Proc. Conference on Integer Programming and Comb. Optimization, pages 90-104, 2001.
BibTeX
M. Elkin. Computing Almost Shortest Paths. In Proc. of ACM Symp. on Distr. Computing, pages 173-182, 2001.
BibTeX
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.
BibTeX
M. Elkin and D. Peleg. The Client-Server 2-Spanner problem. In Proc. Colloq. on Struct. Info. and Comm. Complexity, 2001.
BibTeX
Michael Elkin. Computing Almost Shortest Paths. In Proc. ACM Symp. on Principles of Distrib. Computing, pages 53-62, 2001.
BibTeX
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.
BibTeX
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.
BibTeX
M. Elkin and D. Peleg. The Hardness of Approximating Spanner Problems. In Proc. Symp. on theoretical Aspects of Computer Science, pages 370-381, 2000.