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

Michael Elkin

A professor in the   Department of Computer Science  at the Ben-Gurion University of the Negev.
 

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 and Parallel 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 of the Negev

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


Teaching


My office hours are Tue. 10:00-12:00, Zoom

  • Distributed Algorithms

The homepage of the class
Spring 2021


Classes taught in the past

  • Distributed Algorithms

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

  • 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, Spring 2014, Autumn 2014, Autumn 2017, Autumn 2018, Autumn 2019

  • 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, Spring 2016, Spring 2017

  • 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

  • Metric Graph Algorithms

The homepage of the class
Autumn 2018

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.

Editorial Service

An associate editor of Journal of Computer and System Sciences.

Program Committees

FOCS 2019, SODA 2019, PODC 2018, DISC 2016, ICDCN 2016, DISC 2015, SODA 2014, DISC 2013, PODC 2012, SWAT 2012, ICDCN 2012, SOFSEM 2012, PODC 2011, SWAT 2008, SIROCCO 2008, ALGOSENSORS 2008.

Graduate Students

Shaked Matar (Ph.D.)

Former Students

Shay Solomon (Ph.D.),

Leonid Barenboim (M.Sc. and Ph.D.), Leonid won Distributed Computing Doctoral Dissertation Award for 2015.

Elad Horev (M.Sc.),

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

 

Ziv Amram (M.Sc.)


Shaked Matar (M.Sc.)

Monograph (a preliminary draft)

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

Journal Papers

·  Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider, The Locality of Distributed Symmetry Breaking. Journal of the ACM, Volume 63 Issue 3, August 2016 Issue-in-Progress Article No. 20

·  Michael Elkin, Shay Solomon, Fast Constructions of Lightweight Spanners for General Graphs. ACM Trans. Algorithms 12(3): 29 (2016)

·  Boaz Ben-Moshe, Michael Elkin, Lee-Ad Gottlieb, Eran Omri Optimizing budget allocation for center and median points. Theor. Comput. Sci. 627: 13-25

·  Michael Elkin, Shay Solomon, Optimal Euclidean Spanners: Really Short, Thin, and Lanky. J. ACM 62(5): 35 (2015)

·  Michael Elkin, Shay Solomon, Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones. SIAM J. Comput. 44(4): 996-1025 (2015)

·  Michael Elkin, Ofer Neiman, Shay Solomon, Light Spanners. SIAM J. Discrete Math. 29(3): 1312-1321 (2015)

·  Leonid Barenboim, Michael Elkin, Combinatorial algorithms for distributed graph coloring. Distributed Computing 27(2): 79-93 (2014)

·  Leonid Barenboim, Michael Elkin, Fabian Kuhn. Distributed (Delta+1)-Coloring in Linear (in Delta) Time. SIAM J. Comput. 43(1): 72-95 (2014)

·  Shay Solomon, Michael Elkin, Balancing Degree, Diameter, and Weight in Euclidean Spanners. SIAM J. Discrete Math. 28(3): 1173-1198 (2014)

·  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

·  Michael Elkin, Ofer Neiman, Distributed Strong Diameter Network Decomposition. PODC 2016: 211-216

·  Michael Elkin, Ofer Neiman: On Efficient Distributed Construction of Near Optimal Routing Schemes. PODC 2016: 235-244

·  Michael Elkin, Arnold Filtser, Ofer Neiman, Terminal Embeddings. APPROX-RANDOM 2015: 242-264

·  Leonid Barenboim, Michael Elkin, Cyril Gavoille, A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation. SIROCCO 2015: 209-223

·  Michael Elkin, Seth Pettie, Hsin-Hao Su, (2*Delta - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting. SODA 2015: 355-370

·  Michael Elkin, Seth Pettie: A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs. SODA 2015: 805-821

·  Michael Elkin, Arnold Filtser, Ofer Neiman, Prioritized Metric Structures and Embedding. STOC 2015: 489-498

·  Michael Elkin, Ofer Neiman, Shay Solomon, Light Spanners. ICALP (1) 2014: 442-452

·  Michael Elkin, Hartmut Klauck, Danupon Nanongkai, Gopal Pandurangan, Can quantum communication speed up distributed computation?
In Proc. of the 2014 ACM Symposium on Principles of Distributed Computing, PODC'14, Pages 166-175, Paris, France.

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

·  Presentations (progression-free sets and coloring)
(progressions),
(coloring), (oracles)

ch

 

Misc

Otkrovenie (open with Word)
Jetyud sorok drob' odin (open with Word)

Yiddish Book Center Tons of scanned Yiddish Books.
Oyb ir kont mameloshn un ir zayt ayf BGU campus, shrayb mir, un ih well freykech zayn zih zu shmuesen:-)