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: |
|
Department
of Computer Science Ben-Gurion
University of the Negev Beer-Sheva, Israel |
|
Teaching
The
homepage of the class Classes taught in
the past
The
homepage of the class
The
homepage of the mini-project
The
homepage of the mini-project Mini-Project
on Distributed Graph Coloring and Channel Allocation
The
homepage of the seminar
The
homepage of the class 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. An associate editor of Journal
of Computer and System Sciences. 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. Shaked Matar (Ph.D.) Shay
Solomon (Ph.D.), Ziv Amram (M.Sc.) Shaked Matar (M.Sc.) · L.
Barenboim and M. Elkin, Distributed
Graph Coloring. · 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, · L. Barenboim and M. Elkin, Distributed Deterministic
Vertex Coloring in Polylogarithmic Time, · M. Elkin and S.
Solomon, Narrow-Shallow-Low-Light
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 Progression-Free Sets, · Y. Dinitz and M.
Elkin and S. Solomon, Low-Light
Trees, and Tight Lower Bounds for Euclidean Spanners, · L. Barenboim and
M. Elkin, Sublogarithmic Distributed MIS Algorithm for Sparse
Graphs Using Nash-Williams 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,
Lower-Stretch
Spanning Trees , · E. Bachmat and M.
Elkin, Bounds on the
Performance of Back-to-front 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
k-spanner 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 Source-Wise and
Pair-Wise Preservers, · M. Elkin, An Unconditional Lower Bound
on the Time-Approximation 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, · M. Elkin, An Overview of Distributed
Approximation, · M. Elkin, Sparse Graph Spanners, · M. Elkin, Low-Stretch Spanning Trees,
· M. Elkin, Synchronizers, Spanners, · 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? · M. Elkin and S. Solomon, Euclidean
Spanners: Really Short, Thin and Lanky , · M. Elkin and S. Solomon, Fast Constructions of
Light-Weight 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 Shallow-Light
Trees are Exponentially Lighter than Spanning Ones , · L. Barenboim and M. Elkin, Combinatorial
Algorithms for Distributed Graph Coloring , · B. Ben-Moshe, 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 Progression-Free Sets, · M. Elkin
and S. Solomon, Narrow-Shallow-Low-Light
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, Shallow-Low-Light
Trees, and Tight Lower Bounds for Euclidean Spanners , · L.
Barenboim and M. Elkin, Sublogarithmic
Distributed MIS Algorithm for MIS on Sparse Graphs Using Nash-Williams
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 Sourse-wise and Pair-wise 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. 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, · 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
k-Spanner Problem, · M. Elkin and D.
Peleg, Approximating
k-spanner problems for k > 2, · M. Elkin and D. Peleg, The Hardness of
Approximating Spanner Problems, · M. Elkin and D.
Peleg, The Client-Server 2-Spanner problem and Applications to Network
Design, · Presentations (progression-free 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:-)