Teaching
My office hours are Tue. 14:0016:00, Room 217, Alon Bldng.
The homepage of the class
Autumn 2016
 MiniProject
on LowDistortion Embeddings
The
homepage of the class
Autumn 2016

Miniproject on Distributed
Algorithms and Channel Allocation
The homepage of the class
Spring 2017
Classes taught in
the past
The
homepage of the class
Autumns 2004, 2005, 2006, 2008, 2009, 2010, 2011, 2012, 2013, 2014
 MiniProject on
Embeddings of Graphs
The
homepage of the miniproject
Autumn 2004, Autumn 2005, Spring 2008, Autumn 2008, Autumn 2009, Autumn 2010, Autumn 2011, Spring 2013,
Spring 2014, Autumn 2014
Spring 2009, Spring 2010, Spring 2011, Spring 2013 (coordinated the course)
 Design of Algorithms
for IAF
Spring 2005, Spring 2008
The homepage of the class
Spring 2006, Spring 2007, Spring 2008
 MiniProject on
Algorithms, Geometry and Graphs
The
homepage of the miniproject
Spring 2006, Spring 2007
 MiniProject on Distributed Graph
Coloring and Channel Allocation
The homepage of the miniproject
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
BenGurion University of the Negev, Israel.
An ideal candidate should have a Ph.D. in computer science/mathematics
and a strong research trackrecord. 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
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
Ziv Amram (M.Sc.)
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.) (coadvised with Ofer Neiman)
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 IssueinProgress
Article No. 20
Michael Elkin, Shay Solomon,
Fast Constructions of Lightweight Spanners for General Graphs.
ACM Trans. Algorithms 12(3): 29 (2016)
Boaz BenMoshe, Michael Elkin, LeeAd Gottlieb, Eran Omri
Optimizing budget allocation for center and median points.
Theor. Comput. Sci. 627: 1325
Michael Elkin, Shay Solomon,
Optimal Euclidean Spanners: Really Short, Thin, and Lanky. J. ACM 62(5): 35 (2015)
Michael Elkin, Shay Solomon,
Steiner ShallowLight Trees Are Exponentially Lighter than Spanning Ones.
SIAM J. Comput. 44(4): 9961025 (2015)
Michael Elkin, Ofer Neiman, Shay Solomon,
Light Spanners.
SIAM J. Discrete Math. 29(3): 13121321 (2015)
Leonid Barenboim, Michael Elkin,
Combinatorial algorithms for distributed graph coloring.
Distributed Computing 27(2): 7993 (2014)
Leonid Barenboim, Michael Elkin, Fabian Kuhn.
Distributed (Delta+1)Coloring in Linear (in Delta) Time.
SIAM J. Comput. 43(1): 7295 (2014)
Shay Solomon, Michael Elkin,
Balancing Degree, Diameter, and Weight in Euclidean Spanners.
SIAM J. Discrete Math. 28(3): 11731198 (2014)
J. Schneider, M. Elkin and R. Wattenhofer,
Symmetry Breaking Depending on Chromatic Number of Neighborhood Growth,
Theoretical Computer Science, 509, pp. 4050, 2013.
L. Barenboim and M. Elkin,
Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence,
Distributed Computing, 26 (56), pp. 273287 (2013). Special Issue for PODC'11 conference.
M. Elkin, A. Ingemar and D. Lukatsky,
Energy Fluctuations Shape Free Energy of NonSpecific Biomolecular
Interactions,
In
Journal of Statistical Physics, Vol. 146, Number 4, pp. 870877, 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,
NarrowShallowLowLight Trees, with and without Steiner Points,
In
SIAM Journal on Discrete Mathematics, Vol. 25, No. 1, pp.181210, 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. 397410, 2011.
M. Elkin,
An Improved Construction of ProgressionFree Sets,
Israeli J. Math., Vol. 184, pp. 93128, 2011
see also the archive
version. Below on this webpage
one can also find the more TCSoriented 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,
LowLight Trees, and Tight Lower Bounds for Euclidean Spanners,
Discrete and Computational Geometry (an invited paper), Vol. 43, Issue 4, pp. 736783,
2010.
L. Barenboim and M.
Elkin,
Sublogarithmic Distributed MIS Algorithm for Sparse Graphs Using
NashWilliams Decomposition,
Distributed Computing, special issue of PODC'08, vol. 22, pp. 363379,
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,
LowerStretch
Spanning Trees ,
In special issue of SIAM Journal on Computing for
STOC'05 conference, Vol. 38, No. 2, pp. 608628, 2008.
E. Bachmat and M.
Elkin,
Bounds on the
Performance of Backtofront Airplane Boarding Policies,
Operations Research Letters, 36(5), pp. 597601, 2008.
M. Elkin, C.
Liebchen, and R. Rizzi,
New Bounds for Cycle Bases,
Information Processing Letters, 104(5), 186193, 2007
M. Elkin and D.
Peleg,
(1+e,b)Spanner
Constructions for General Graphs,
SIAM J. Comput. 33(3): 608631 (2004)
M. Elkin and G.
Kortsarz,
Logarithmic
Inapproximability of the Radio Broadcast Problem,
J. Algorithms 52(1): 825 (2004)
M. Elkin,
Computing Almost
Shortest Paths,
in Transactions on Algorithms, Vol. 1, No. 2, pp.283323, 2005.
M. Elkin and G.
Kortsarz,
Combinatorial Logarithmic
Approximation Algorithm for Directed Telephone Broadcast Problem,
SIAM Journal on Computing, Vol. 35, Num. 3, pp. 672689
M. Elkin and D.
Peleg,
Approximating
kspanner problem for k > 2 ,
Theoretical Computer Science 337 (2005) 249277
M. Elkin and G.
Kortsarz,
Polylogarithmic
Additive Hardness of Approximating Radio Broadcast Problem ,
SIAM Journal of Discrete Mathematics
Vol. 19, Num. 4, pp. 881899, 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. 10291055, 2006
M. Elkin and J.
Zhang,
Efficient constructions
of (1+e,b)spanners in the Streaming and Distributed Models,
Distributed Computing, 18(5), pages 375385, 2006.
M. Elkin and G.
Kortsarz,
An Approximation
Algorithm for the Directed Multicast Problem,
Algorithmica, 45(4), pages 569583, 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. 648659, June 2006.
D. Coppersmith and M.
Elkin,
Sparse SourceWise and
PairWise Preservers,
SIAM Journal of Discrete Mathematics, Vol. 20, Number 2, pages 463501.
M. Elkin,
An Unconditional Lower
Bound on the TimeApproximation Tradeoff for the Minimum Spanning Tree
Problem,
SIAM Journal on Computing, Vol. 36, No. 2, pp. 433456, 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. 12821308,
2006.
M. Elkin and D. Peleg,
The Hardness of
Approximating Spanner Problems,
Theory Comput. Systems, Vol. 41, pp. 691729, 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. 4057.
M. Elkin,
Sparse Graph Spanners,
In Encyclopedia of Algorithms, ed. MingYang Kao.
M. Elkin,
LowStretch Spanning Trees,
In Encyclopedia of Algorithms, ed. MingYang Kao.
M. Elkin,
Synchronizers, Spanners,
In Encyclopedia of Algorithms, ed. MingYang Kao.
Conference
Papers
Michael Elkin, Ofer Neiman,
Distributed Strong Diameter Network Decomposition. PODC 2016: 211216
Michael Elkin, Ofer Neiman:
On Efficient Distributed Construction of Near Optimal Routing Schemes. PODC 2016: 235244
Michael Elkin, Arnold Filtser, Ofer Neiman,
Terminal Embeddings. APPROXRANDOM 2015: 242264
Leonid Barenboim, Michael Elkin, Cyril Gavoille,
A Fast NetworkDecomposition Algorithm and Its Applications to ConstantTime Distributed Computation. SIROCCO 2015: 209223
Michael Elkin, Seth Pettie, HsinHao Su,
(2*Delta  l)EdgeColoring is Much Easier than Maximal Matching in the Distributed Setting. SODA 2015: 355370
Michael Elkin, Seth Pettie:
A LinearSize Logarithmic Stretch PathReporting Distance Oracle for General Graphs.
SODA 2015: 805821
Michael Elkin, Arnold Filtser, Ofer Neiman,
Prioritized Metric Structures and Embedding.
STOC 2015: 489498
Michael Elkin, Ofer Neiman, Shay Solomon,
Light Spanners.
ICALP (1) 2014: 442452
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 166175, 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. 645654,
PaloAlto, CA, USA, June 2013
M. Elkin and S. Solomon,
Fast Constructions of LightWeight Spanners for General Graphs ,
In
Proc. of the ACMSIAM Symp. on Discrete Algorithms, SODA'13, pp. 513525,
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. 321330, New Brunswick, NJ, USA, Oct. 2012
M. Elkin and S. Solomon,
Steiner ShallowLight Trees are Exponentially Lighter than Spanning Ones
,
In
Proc. of 52nd Annual Symp. on Theoretical Foundations of Computer Science,
FOCS'11, pp. 373382,
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. BenMoshe, 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. 129138,
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. 4859,
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. 410419
Zurich, Switzerland, July 2010.
Received PODC'10 best paper award.
M. Elkin,
An Improved Constructions of ProgressionFree Sets,
In
Proc. SIAMACM Symp. on Discr. Alg., SODA'10, pp.886905,
Austin, TX, USA, 2010.
M. Elkin and S. Solomon,
NarrowShallowLowLight Trees, with and without Steiner Points,
In
Proc. European Symp. on Algorithms, ESA'09, pp. 215226,
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.111120,
Bethesda, MD, 2009.
Y. Dinitz, M. Elkin and S. Solomon,
ShallowLowLight Trees, and Tight Lower Bounds for Euclidean Spanners ,
In
Proc. IEEE Annual Symp. on Foundations of Comp. Science, FOCS'08,
pp. 519528,
Philadelphia, PA, 2008.
L. Barenboim and M.
Elkin,
Sublogarithmic
Distributed MIS Algorithm for MIS on Sparse Graphs Using NashWilliams
Decomposition
In Proc. of International Symp. on Principles of Distributed
Computing, PODC'08, pp. 2534, 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. 425438, 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. 494503
Baltimore, Maryland, USA.
M. Elkin and G.
Kortsarz,
An Improved Algorithm
for Radio Broadcast,
in Proc. ACMSIAM on Discrete Algorithms, SODA'05, Vancouver, British
Columbia, Canada.
D.Coppersmith and M.
Elkin,
Sparse Soursewise
and Pairwise Distance Preservers,
in Proc. ACMSIAM 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.
160168, 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.331340.
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. 105114, Cambridge, MA, 2004.
M. Elkin,
A Faster
Distributed Protocol for Constructing a Minimum Spanning Tree, in Proc.
ACMSIAM on Discrete Algorithms, SODA'04, pp. 352361, 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 ACMSiam 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 ACMSiam 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. 173182,
Greece, Crete, July, 2001.
M. Elkin,
Computing Almost
Shortest Paths,
in Proc. 20th ACM Symp. on Principles of Distributed Computing, pp. 5362,
Newport, Rhode Island, USA, August, 2001.
M. Elkin and D.
Peleg,
Strong Inapproximability of the Basic kSpanner Problem,
in Proc. 27th Int. Colloq. on Automata, Languages and Programming, Geneva,
Switzerland, July 2000, pp. 636648. 2000.
(Contains an error in the proof that highgirth LabelCover is still hard to approximate
within exp{log^{1eps} 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 LabelCover with high girth
is indeed hard to approximate within this factor.)
M. Elkin and D.
Peleg,
Approximating
kspanner 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, 370381.
M. Elkin and D.
Peleg,
The
ClientServer 2Spanner 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
(progressionfree sets and coloring)
(progressions),
(coloring),
(oracles)

