http://www.cs.bgu.ac.il/~elkinm/ya.aug04.jpg 

Michael Elkin

A faculty member (an associate professor) 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. 14:00-16:00, Room 217, Alon Bldng.

  • Design of Algorithms


The homepage of the class
Spring 2014

  • Mini-Project on Low-Distortion Embeddings


The homepage of the class
Spring 2014

Classes taught in the past

  • Distributed Algorithms


The homepage of the class
Autumns 2004,2005,2006,2008,2009,2010,2011,2012,2013

  • Mini-Project on Embeddings of Graphs


The homepage of the mini-project
Autumn 2004, Autumn 2005, Spring 2008, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Spring 2013

  • Design of Algorithms


Spring 2009, Spring 2010, Spring 2011, Spring 2013 (coordinated the course)

  • 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

  • Mini-Project on Distributed Graph Coloring and Channel Allocation


The homepage of the mini-project
Autumn 2013

  • Seminar on Distributed Algorithms

  • The homepage of the seminar
    Spring 2007

    A Postdoc Position Available

    Applications are invited for a postdoctoral position in theoretical computer science at Ben-Gurion University of the Negev, Israel. An ideal candidate should have a Ph.D. in computer science/mathematics and a strong research track-record. Within theoretical computer science, our focus is on Graph Algorithms (distributed, approximation, etc) and Metric Embeddings. Our group consists of Eden Chlamtac, Ofer Neiman and myself. The position is for one year with possible extension for an additional year, there are no teaching duties. Candidates should submit a current CV (with list of publications), a letter describing research plan, and names and addresses of three individuals who will provide recommendation letters. Applications material should be sent by email directly to me or to Ofer Neiman.

    Program Committees

    SODA 2014 , DISC 2013 , PODC 2012, SWAT 2012, ICDCN 2012, SOFSEM 2012, PODC 2011, SWAT 2008, SIROCCO 2008, ALGOSENSORS 2008.

    Graduate Students

    Arnold Filtzer (M.Sc.) (co-advised with Ofer Neiman)

    Former Students

    Shay Solomon (Ph.D.),

    Leonid Barenboim (finished M.Sc. and Ph.D. under my supervision),

    Elad Horev (M.Sc.)

    Monograph (a preliminary draft)

  • L. Barenboim and M. Elkin,
  • Distributed Graph Coloring.

    Journal Papers

  • J. Schneider, M. Elkin and R. Wattenhofer,
  • Symmetry Breaking Depending on Chromatic Number of Neighborhood Growth, Theoretical Computer Science, 509, pp. 40-50, 2013.

  • L. Barenboim and M. Elkin,
  • Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence, Distributed Computing, 26 (5-6), pp. 273-287 (2013). Special Issue for PODC'11 conference.

  • M. Elkin, A. Ingemar and D. Lukatsky,
  • Energy Fluctuations Shape Free Energy of Non-Specific Biomolecular Interactions,
    In Journal of Statistical Physics, Vol. 146, Number 4, pp. 870-877, 2012.

  • L. Barenboim and M. Elkin,
  • Distributed Deterministic Vertex Coloring in Polylogarithmic Time,
    In Journal of ACM, Vol. 58, No. 5, 23, 2011.

  • M. Elkin and S. Solomon,
  • Narrow-Shallow-Low-Light Trees, with and without Steiner Points,
    In SIAM Journal on Discrete Mathematics, Vol. 25, No. 1, pp.181-210, 2011.

  • M. Elkin, Y. Lando, Z. Nutov, M. Segal and H. Shpungin,
  • Novel Algorithms for the Network Lifetime Problem in Wireless Setting
    Wireless Networks journal, Vol. 17, Issue 2, pp. 397-410, 2011.

  • M. Elkin,
  • An Improved Construction of Progression-Free Sets,
    Israeli J. Math., Vol. 184, pp. 93-128, 2011
    see also the archive version.
    Below on this web-page one can also find 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.

  • Y. Dinitz and M. Elkin and S. Solomon,
  • Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners,
    Discrete and Computational Geometry (an invited paper), Vol. 43, Issue 4, pp. 736-783, 2010.

  • L. Barenboim and M. Elkin,
  • Sublogarithmic Distributed MIS Algorithm for Sparse Graphs Using Nash-Williams Decomposition,
    Distributed Computing, special issue of PODC'08, vol. 22, pp. 363-379, 2010.

  • M. Elkin,
  • Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners,
    Transactions on Algorithms, Vol. 7, No. 2, Article 20, March 2011.

  • 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 and S. Solomon,
  • Euclidean Spanners: Really Short, Thin and Lanky ,
    In Proc. of the 45th ACM Symp. on Theory of Computing, STOC'13, pp. 645-654, Palo-Alto, CA, USA, June 2013

  • M. Elkin and S. Solomon,
  • Fast Constructions of Light-Weight Spanners for General Graphs ,
    In Proc. of the ACM-SIAM Symp. on Discrete Algorithms, SODA'13, pp. 513-525, New Orleans, LA, USA, Jan. 2013

  • L. Barenboim, M. Elkin, S.Pettie and J. Schneider.
  • The Locality of Distributed Symmetry Breaking ,
    In Proc. of 53rd Annual Symp. on Theoretical Foundations of Computer Science, FOCS'12, pp. 321-330, New Brunswick, NJ, USA, Oct. 2012

  • M. Elkin and S. Solomon,
  • Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones ,
    In Proc. of 52nd Annual Symp. on Theoretical Foundations of Computer Science, FOCS'11, pp. 373-382, Palm Springs, CA, USA, Oct. 2011

  • L. Barenboim and M. Elkin,
  • Combinatorial Algorithms for Distributed Graph Coloring ,
    In Proc. of International Symp. on Distributed Computing, DISC'11, Rome, Italy, Sep. 2011

  • B. Ben-Moshe, M. Elkin and E. Omri,
  • Optimizing Budget Allocation in Graphs ,
    In Proc. of Canadian Conference on Computational Geometry, CCCG'11, Toronto, CA, Aug. 2011

  • L. Barenboim and M. Elkin,
  • Distributed Deterministic Edge Coloring Using Bounded Neighborhood Independence ,
    In Proc. of International Symp. on Principles of Distributed Computing, PODC'11, pp. 129-138, San Jose, CA, USA, June 2011.
    Received PODC'11 best student paper award.

  • S. Solomon and M. Elkin,
  • Balancing Degree, Weight and Diameter in Euclidean Spanners ,
    In Proc. of European Symp. on Algorithms, ESA'10, pp. 48-59, Liverpool, UK, Sep. 2010.

  • L. Barenboim and M. Elkin,
  • Deterministic Distributed Coloring in Polylogarithmic Time,
    In Proc. of International Symp. on Principles of Distributed Computing, PODC'10, pp. 410-419 Zurich, Switzerland, July 2010.
    Received PODC'10 best paper award.


  • M. Elkin,
  • An Improved Constructions of Progression-Free Sets,
    In Proc. SIAM-ACM Symp. on Discr. Alg., SODA'10, pp.886-905, Austin, TX, USA, 2010.

  • M. Elkin and S. Solomon,
  • Narrow-Shallow-Low-Light Trees, with and without Steiner Points,
    In Proc. European Symp. on Algorithms, ESA'09, pp. 215-226, 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

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


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

    (Contains an error in the proof that high-girth Label-Cover is still hard to approximate within exp{log^{1-eps} n} factor. See my TCS paper with Peleg and a paper by Mike Dinitz, Guy Kortsarz and Ran Raz for more details about the error. The latter paper also proves that Label-Cover with high girth is indeed hard to approximate within this factor.)

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

  • The presentations (progression-free sets and coloring)

  • (progressions),
    (coloring),

     

    Misc