Michael Elkin
A
professor in the Department of
Computer Science at the BenGurion
University of the Negev. Research
Interests
Generally,
I am interested in Theoretical Computer Science (TCS) and Discrete
Mathematics. In particular, I am interested in: 

Department
of Computer Science BenGurion
University of the Negev BeerSheva, Israel 

Teaching
The
homepage of the class Classes taught in
the past
The
homepage of the class
The
homepage of the miniproject
The
homepage of the miniproject MiniProject
on Distributed Graph Coloring and Channel Allocation
The
homepage of the seminar
The
homepage of the class 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 ServiceAn associate editor of Journal
of Computer and System Sciences. Program CommitteesFOCS 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.), 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 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, · L. Barenboim and M. Elkin, Distributed Deterministic
Vertex Coloring in Polylogarithmic Time, · M. Elkin and S.
Solomon, NarrowShallowLowLight
Trees, with and without Steiner Points, · M. Elkin, Y. Lando, Z. Nutov, M. Segal and
H. Shpungin, Novel
Algorithms for the Network Lifetime Problem in Wireless Setting · M. Elkin, An Improved
Construction of ProgressionFree Sets, · Y. Dinitz and M.
Elkin and S. Solomon, LowLight
Trees, and Tight Lower Bounds for Euclidean Spanners, · L. Barenboim and
M. Elkin, Sublogarithmic Distributed MIS Algorithm for Sparse
Graphs Using NashWilliams Decomposition, · M. Elkin, Streaming and
Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse
Spanners, · M. Elkin and Y.
Emek and D. Spielman and S. Teng,
LowerStretch
Spanning Trees , · E. Bachmat and M.
Elkin, Bounds on the
Performance of Backtofront Airplane Boarding Policies, · M. Elkin, C. Liebchen, and R. Rizzi, New Bounds for Cycle Bases,
· M. Elkin and D. Peleg, (1+e,b)Spanner
Constructions for General Graphs, · M. Elkin and G.
Kortsarz, Logarithmic Inapproximability of the Radio Broadcast Problem, · M. Elkin, Computing Almost
Shortest Paths, · M. Elkin and G.
Kortsarz, Combinatorial
Logarithmic Approximation Algorithm for Directed Telephone Broadcast Problem,
· M. Elkin and D.
Peleg, Approximating
kspanner problem for k > 2 , · M. Elkin and G. Kortsarz, Polylogarithmic
Additive Hardness of Approximating Radio Broadcast Problem , · B. Bollobas, D. Coppersmith and M. Elkin, Sparse Subgraphs
that Preserve Long Distances and Additive Spanners, · M. Elkin and J. Zhang, Efficient constructions of
(1+e,b)spanners in the Streaming and Distributed Models, · M. Elkin and G. Kortsarz, An Approximation
Algorithm for the Directed Multicast Problem, · M. Elkin and G.
Kortsarz, Sublogarithmic Approximation for Telephone Multicast:
Path out of Jungle, · D. Coppersmith and M. Elkin, Sparse SourceWise and
PairWise Preservers, · M. Elkin, An Unconditional Lower Bound
on the TimeApproximation Tradeoff for the Minimum Spanning Tree Problem,
· M. Elkin and G. Kortsarz, An Improved Algorithm
for Radio Broadcast, · M. Elkin, A Faster Distributed
Protocol for Constructing a Minimum Spanning Tree, · M. Elkin and D. Peleg, The Hardness of
Approximating Spanner Problems, Survey
Papers
· M. Elkin, An Overview of Distributed
Approximation, · M. Elkin, Sparse Graph Spanners, · M. Elkin, LowStretch Spanning Trees,
· M. Elkin, Synchronizers, Spanners, 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? · M. Elkin and S. Solomon, Euclidean
Spanners: Really Short, Thin and Lanky , · M. Elkin and S. Solomon, Fast Constructions of
LightWeight Spanners for General Graphs , · L. Barenboim, M. Elkin, S.Pettie and J. Schneider. The Locality of
Distributed Symmetry Breaking , · M. Elkin and S. Solomon, Steiner ShallowLight
Trees are Exponentially Lighter than Spanning Ones , · L. Barenboim and M. Elkin, Combinatorial
Algorithms for Distributed Graph Coloring , · B. BenMoshe, M.
Elkin and E. Omri, Optimizing Budget
Allocation in Graphs , · L.
Barenboim and M. Elkin, Distributed
Deterministic Edge Coloring Using Bounded Neighborhood Independence , · S. Solomon
and M. Elkin, Balancing
Degree, Weight and Diameter in Euclidean Spanners , · L.
Barenboim and M. Elkin, Deterministic
Distributed Coloring in Polylogarithmic Time, · M. Elkin, An Improved
Constructions of ProgressionFree Sets, · M. Elkin
and S. Solomon, NarrowShallowLowLight
Trees, with and without Steiner Points, · L.
Barenboim and M. Elkin, Distributed
(Delta+1)Coloring in Linear (in Delta) Time, · Y. Dinitz,
M. Elkin and S. Solomon, ShallowLowLight
Trees, and Tight Lower Bounds for Euclidean Spanners , · L.
Barenboim and M. Elkin, Sublogarithmic
Distributed MIS Algorithm for MIS on Sparse Graphs Using NashWilliams
Decomposition · M. Elkin, Y. Lando, Z. Nutov, M. Segal and
H. Shpungin Novel
Algorithms for the Network Lifetime Problem in Wireless Setting · M. Elkin, Fully Dynamic
Distributed Algorithm for Maintaining Sparse Spanners, · M. Elkin, Streaming and Fully
Dynamic Centralized Algorithms for Maintaining Sparse Spanners, · M. Elkin, Y. Emek,
D. Spielman, S. Teng, Lower Stretch Spanning Trees,
· M. Elkin
and G. Kortsarz, An
Improved Algorithm for Radio Broadcast, · D.Coppersmith and M. Elkin, Sparse Soursewise and Pairwise Distance Preservers, · M. Elkin
and J. Zhang, Efficient
constructions of (1+e,b)spanners in the Streaming and Distributed Models,
· M. Elkin, An Unconditional
Lower Bound on the Hardness of Approximation of Distributed Minimum Spanning
Tree Problem, · M. Elkin and G. Kortsarz, Polylogarithmic
Inapproximability of the Radio Broadcast Problem,
· 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, · M. Elkin and G. Kortsarz, Sublogarithmic Approximation for Telephone Multicast:
Path out of Jungle, · M. Elkin and G.
Kortsarz, Approximation algorithm for the directed telephone multicast
problem, · M. Elkin
and G. Kortsarz, Combinatorial
Logarithmic Approximation Algorithm for Directed Telephone Broadcast Problem,
· M. Elkin and D. Peleg, (1+e,b)Spanner
Constructions for General Graphs, · M. Elkin, Computing Almost
Shortest Paths, · M. Elkin and D.
Peleg, Strong Inapproximability of the Basic
kSpanner Problem, · M. Elkin and D.
Peleg, Approximating
kspanner problems for k > 2, · M. Elkin and D. Peleg, The Hardness of
Approximating Spanner Problems, · M. Elkin and D.
Peleg, The ClientServer 2Spanner problem and Applications to Network
Design, · Presentations (progressionfree sets and
coloring) 
ch 
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:)