Michael Elkin

A faculty member in the   Department of Computer Science  at the Ben-Gurion University .

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 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

Address:

Department of Computer Science

Ben-Gurion University

Beer-Sheva, Israel
Room:   217, Alon Building.
Phone:  972 8 6477884
Fax:      972 8 6477650 (attn. Michael Elkin)
Email: elkinm at cs.bgu.ac.il

---

Teaching

My office hours are Mon. 11:00-13:00, Room 217, Alon Bldng.

• Distributed Algorithms

The homepage of the class
Autumn 2009

• Mini-Project on Algorithms, Geometry and Graphs

The homepage of the mini-project
Autumn 2009

• Classes taught in the past

  • Distributed Algorithms

  
  The homepage of the class
  Autumns 2004,2005,2006,2008

  • Mini-Project on Embeddings of Graphs

  
  The homepage of the mini-project
  Autumn 2004, Autumn 2005, Spring 2008, Autumn 2008

  • Design of Algorithms for IAF

  
  Spring 2005, Spring 2008
  
  

  • Data Structures

  
  The homepage of the class
  Spring 2006, Spring 2007, Spring 2008
  
  

  • Mini-Project on Algorithms, Geometry and Graphs

  
  The homepage of the mini-project
  Spring 2006, Spring 2007

  • Seminar on Distributed Algorithms

  
  The homepage of the seminar
  Spring 2007

  Serving in Program Committees

  11th Scandinavian Workshop on Algorithm Theory
  SWAT 2008

  15th International Colloquium on Structural Information and Communication Complexity
  SIROCCO 2008

  4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks
  ALGOSENSORS 2008

  Graduate Students

  
  Shay Solomon (Ph.D.)
  Won Clore Fellowship.
  
  Leonid Barenboim (Ph.D.)
  Finished M.Sc. summa cum laude under my supervision, and won Zabey prize for the best M.Sc. thesis in the Faculty of Natural Sciences.

  Former Students

  
  Elad Horev (M.Sc.)

  Journal Papers

  • M. Elkin

  
  An Improved Construction of Progression-Free Sets,
  Accepted to Israeli J. Math., 2008.
  see also the archive version.
  Below on this web-page one can also the more TCS-oriented SODA'10 variant of this paper.
  The link to the post by Gil Kalai about this result.
  For the paper by Ben Green and Julia Wolf titled "A Note on Elkin's Improvement of Behrend's Construction" please follow this link.
  
  

  • M. Elkin

  
  Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners,
  Accepted to Transactions on Algorithms, 2008.
  
  

  • M. Elkin and Y. Emek and D. Spielman and S. Teng

  
  Lower-Stretch Spanning Trees, ,
  In special issue of SIAM Journal on Computing for STOC'05 conference, Vol. 38, No. 2, pp. 608-628, 2008.
  
  

  • E. Bachmat and M. Elkin

  
  Bounds on the Performance of Back-to-front Airplane Boarding Policies,
  Operations Research Letters, 36(5), pp. 597-601, 2008.
  
  

  • M. Elkin, C. Liebchen, and R. Rizzi

  
  New Bounds for Cycle Bases,
  Information Processing Letters, 104(5), 186-193, 2007
  
  

  • M. Elkin and D. Peleg,

  
  (1+e,b)-Spanner Constructions for General Graphs,
  SIAM J. Comput. 33(3): 608-631 (2004)
  
  

  • M. Elkin and G. Kortsarz,

  
  Logarithmic Inapproximability of the Radio Broadcast Problem,
  J. Algorithms 52(1): 8-25 (2004)
  
  

  • M. Elkin,

  
  Computing Almost Shortest Paths,
  in Transactions on Algorithms, Vol. 1, No. 2, pp.283-323, 2005.
  
  

  • M. Elkin and G. Kortsarz,

  
  Combinatorial Logarithmic Approximation Algorithm for Directed Telephone Broadcast Problem,
  SIAM Journal on Computing, Vol. 35, Num. 3, pp. 672-689
  
  

  • M. Elkin and D. Peleg,

  
  Approximating k-spanner problem for k > 2 ,
  Theoretical Computer Science 337 (2005) 249-277
  
  

  • M. Elkin and G. Kortsarz,

  
  Polylogarithmic Additive Hardness of Approximating Radio Broadcast Problem ,
  SIAM Journal of Discrete Mathematics
  
  Vol. 19, Num. 4, pp. 881-899, 2005.

  • B. Bollobas, D. Coppersmith and M. Elkin,

  
  Sparse Subgraphs that Preserve Long Distances and Additive Spanners,
  SIAM Journal on Discrete Mathematics, Vol. 19, No. 4, pp. 1029-1055, 2006
  
  

  • M. Elkin and J. Zhang,

  
  Efficient constructions of (1+e,b)-spanners in the Streaming and Distributed Models,
  Distributed Computing, 18(5), pages 375-385, 2006.
  
  

  • M. Elkin and G. Kortsarz,

  
  An Approximation Algorithm for the Directed Multicast Problem,
  Algorithmica, 45(4), pages 569-583, 2006.
  
  

  • M. Elkin and G. Kortsarz,

  
  Sublogarithmic Approximation for Telephone Multicast: Path out of Jungle,
  Journal of Computer and System Sciences, Vol. 72(4), pp. 648-659, June 2006.

  • D. Coppersmith and M. Elkin

  
  Sparse Source-Wise and Pair-Wise Preservers,
  SIAM Journal of Discrete Mathematics, Vol. 20, Number 2, pages 463-501.

  • M. Elkin

  
  An Unconditional Lower Bound on the Time-Approximation Tradeoff for the Minimum Spanning Tree Problem,
  SIAM Journal on Computing, Vol. 36, No. 2, pp. 433-456, 2006.

  • M. Elkin and G. Kortsarz

  
  An Improved Algorithm for Radio Broadcast,
  Transactions on Algorithms, 3(1), 2007.

  • M. Elkin

  
  A Faster Distributed Protocol for Constructing a Minimum Spanning Tree,
  Journal of Computer and System Sciences, Vol. 72, Number 8, pp. 1282-1308, 2006.

  • M. Elkin and D. Peleg

  
  The Hardness of Approximating Spanner Problems,
  Theory Comput. Systems, Vol. 41, pp. 691-729, 2007.

  Survey Papers

  • M. Elkin,

  
  An Overview of Distributed Approximation,
  in ACM SIGACT News Distributed Computing Column Volume 35, Number 4 (Whole number 132), Dec. 2004, pp. 40-57.

  • M. Elkin,

  
  Sparse Graph Spanners,
  In Encyclopedia of Algorithms, ed. Ming-Yang Kao

  • M. Elkin,

  
  Low-Stretch Spanning Trees,
  In Encyclopedia of Algorithms, ed. Ming-Yang Kao

  • M. Elkin,

  
  Synchronizers, Spanners,
  In Encyclopedia of Algorithms, ed. Ming-Yang Kao

  Conference Papers

  • M. Elkin,
  
  An Improved Constructions of Progression-Free Sets,
  In Proc. SIAM-ACM Symp. on Discr. Alg., SODA'10, Austin, TX, USA, 2010.
  
  • M. Elkin and S. Solomon,
  
  Narrow-Shallow-Low-Light Trees, with and without Steiner Points,
  To appear in Proc. European Symp. on Algorithms, ESA'09, Copenhagen, Denmark, 2009.
  
  • L. Barenboim and M. Elkin,
  
  Distributed (Delta+1)-Coloring in Linear (in Delta) Time ,
  In Proc. Symp. on Theory of Computing, STOC'09, pp.111-120, Bethesda, MD, 2009.
  
  • Y. Dinitz, M. Elkin and S. Solomon,
  
  Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners ,
  In Proc. IEEE Annual Symp. on Foundations of Comp. Science, FOCS'08, pp. 519-528, Philadelphia, PA, 2008.
  
  • L. Barenboim and M. Elkin,

  
  Sublogarithmic Distributed MIS Algorithm for MIS on Sparse Graphs Using Nash-Williams Decomposition
  In Proc. of International Symp. on Principles of Distributed Computing, PODC'08, pp. 25-34, Toronto, Canada

  • M. Elkin, Y. Lando, Z. Nutov, M. Segal and H. Shpungin

  
  Novel Algorithms for the Network Lifetime Problem in Wireless Setting
  In Proc. of the 7th International Conf. on Adhoc and Wireless Networks, AdhocNow'08, pp. 425-438, Antibes, France

  • M. Elkin,

  
  Fully Dynamic Distributed Algorithm for Maintaining Sparse Spanners,
  in Proc. of International Symp. on Principles of Distributed Computing, PODC'07 Portland, Oregon, USA
  
  This paper is singled out "the paper that stood out in PODC 2007" in the
  SIGACT Annual Report 2007 (by Richard Ladner), SIGACT News, Vol. 38, No. 4

  • M. Elkin,

  
  Streaming and Fully Dynamic Centralized Algorithms for Maintaining Sparse Spanners,
  in Proc. of International Colloq. on Automata, Languages, and Programming, ICALP'07 Wroclaw, Poland

  • M. Elkin, Y. Emek, D. Spielman, S. Teng,

  
  Lower Stretch Spanning Trees,
  in Proc. ACM Symposium on Theory of Computing, STOC'05, pp. 494-503 Baltimore, Maryland, USA.
  
  This paper is mentioned among "the significant papers on new areas that were published in Proceedings of SIGACT conferences in 2005" in the
  SIGACT Annual Report 2005 (by Hal Gabow)

  • M. Elkin and G. Kortsarz,

  
  An Improved Algorithm for Radio Broadcast,
  in Proc. ACM-SIAM on Discrete Algorithms, SODA'05, Vancouver, British Columbia, Canada.

  • D.Coppersmith and M. Elkin,

  
  Sparse Sourse-wise and Pair-wise Distance Preservers,
  in Proc. ACM-SIAM on Discrete Algorithms, SODA'05, Vancouver, British Columbia, Canada.

  • M. Elkin and J. Zhang,

  
  Efficient constructions of (1+e,b)-spanners in the Streaming and Distributed Models,
  in Proc. 23rd ACM Symp. on Principles of Distributed Computing, PODC'04, pp. 160-168, St. John's, Newfoundland, Canada.

  • M. Elkin,

  
  An Unconditional Lower Bound on the Hardness of Approximation of Distributed Minimum Spanning Tree Problem,
  Proc. 36th Annual ACM Symp. on Theory of Computing, STOC'04 Chicago, IL, USA, June, 2004, pp.331-340.

  • M. Elkin and G. Kortsarz,

  
  Polylogarithmic Inapproximability of the Radio Broadcast Problem,
  Proc. of 7th. International Workshop on > Approximation Algorithms for Combinatorial Optimization Problems, pp. 105-114, Cambridge, MA, 2004.
  
  

  • M. Elkin,

  
  A Faster Distributed Protocol for Constructing a Minimum Spanning Tree, in Proc. ACM-SIAM on Discrete Algorithms, SODA'04, pp. 352-361, New Orleans, LA, USA, Jan. 04.

  • B. Bollobas, D. Coppersmith and M. Elkin,

  
  Sparse Subgraphs that Preserve Long Distances and Additive Spanners,
  in  Proc. 14th Annual ACM-Siam Symp. on Discrete Algorithms, SODA'03, USA, MD, Baltimore, January, 2003.

  • M. Elkin and G. Kortsarz,

  
  Sublogarithmic Approximation for Telephone Multicast: Path out of Jungle,
  in Proc. 14th Annual ACM-Siam Symp. on Discrete Algorithms,SODA'03, USA, MD, Baltimore, January, 2003.

  • M. Elkin and G. Kortsarz,

  
  Approximation algorithm for the directed telephone multicast problem,
  in Proc. 30th International Colloq. on Automata, Languages and Programming}, Eindhoven, Netherlands, June 2003.

  • M. Elkin and G. Kortsarz,

  
  Combinatorial Logarithmic Approximation Algorithm for Directed Telephone Broadcast Problem,
  in Proc. 34th Annual ACM Symp. on Theory of Computing, STOC'02, Canada, Montreal, May, 2002.

  • M. Elkin and D. Peleg,

  
  (1+e,b)-Spanner Constructions for General Graphs,
  in Proc. 33rd Annual ACM Symp. on Theory of Computing, STOC'01, pp. 173-182, Greece, Crete, July, 2001.
  
  
  

  • M. Elkin,

  
  Computing Almost Shortest Paths,
  in Proc. 20th ACM Symp. on Principles of Distributed Computing, pp. 53-62, Newport, Rhode Island, USA, August, 2001.

  • M. Elkin and D. Peleg,

  
  Strong Inapproximability of the Basic k-Spanner Problem,
  in Proc. 27th Int. Colloq. on Automata, Languages and Programming, Geneva, Switzerland, July 2000, pp. 636-648. 2000.

  • M. Elkin and D. Peleg,

  
  Approximating k-spanner problems for k > 2,
  in: Proc. 8th Conference in Integer Programming and Combinatorial Optimization, Utrecht, Netherlands, June, 2001.

  • M. Elkin and D. Peleg,

  
  The Hardness of Approximating Spanner Problems,
  in Proc. 17th Symp. on Theoretical Aspects of Computer Science, Lille, France, Feb. 2000, 370-381.
  
  

  • M. Elkin and D. Peleg,

  The Client-Server 2-Spanner problem and Applications to Network Design,  
  in  Proc. 8th International Colloq. on Structural Information and Communication Complexity, Vall de Nuria, Catalonia, Spain, July, 2001. 2001.

  • The presentation (progression-free sets)

  
  (pdf),
  (ps),