Michael Elkin

According to our database1, Michael Elkin authored at least 97 papers between 2000 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

2020
Near-Additive Spanners and Near-Exact Hopsets, A Unified View.
CoRR, 2020

Lossless Prioritized Embeddings.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

2019
Efficient Algorithms for Constructing Very Sparse Spanners and Emulators.
ACM Trans. Algorithms, 2019

Hopsets with Constant Hopbound, and Applications to Approximate Shortest Paths.
SIAM J. Comput., 2019

Almost Shortest Paths and PRAM Distance Oracles in Weighted Graphs.
CoRR, 2019

Fast Deterministic Constructions of Linear-Size Spanners and Skeletons.
CoRR, 2019

Distributed Construction of Light Networks.
CoRR, 2019

Linear-Size Hopsets with Small Hopbound, and Constant-Hopbound Hopsets in RNC.
Proceedings of the 31st ACM on Symposium on Parallelism in Algorithms and Architectures, 2019

Near-Additive Spanners In Low Polynomial Deterministic CONGEST Time.
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

2018
A fast network-decomposition algorithm and its applications to constant-time distributed computation.
Theor. Comput. Sci., 2018

Prioritized Metric Structures and Embedding.
SIAM J. Comput., 2018

On efficient distributed construction of near optimal routing schemes.
Distributed Computing, 2018

Ramsey Spanning Trees and their Applications.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Near-Optimal Distributed Routing with Low Memory.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Session details: Session 3D: Graphs and Population.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Locally-Iterative Distributed (Δ+ 1): -Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Near Isometric Terminal Embeddings for Doubling Metrics.
Proceedings of the 34th International Symposium on Computational Geometry, 2018

2017
Terminal embeddings.
Theor. Comput. Sci., 2017

Locally-Iterative Distributed (Delta + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models.
CoRR, 2017

Linear-Size Hopsets with Small Hopbound, and Distributed Routing with Low Memory.
CoRR, 2017

Distributed exact shortest paths in sublinear time.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

A Simple Deterministic Distributed MST Algorithm, with Near-Optimal Time and Message Complexities.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity.
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2017

2016
Synchronizers, Spanners.
Encyclopedia of Algorithms, 2016

Sparse Graph Spanners.
Encyclopedia of Algorithms, 2016

Low Stretch Spanning Trees.
Encyclopedia of Algorithms, 2016

Space-efficient path-reporting approximate distance oracles.
Theor. Comput. Sci., 2016

Optimizing budget allocation for center and median points.
Theor. Comput. Sci., 2016

Fast Constructions of Lightweight Spanners for General Graphs.
ACM Trans. Algorithms, 2016

A Linear-Size Logarithmic Stretch Path-Reporting Distance Oracle for General Graphs.
ACM Trans. Algorithms, 2016

The Locality of Distributed Symmetry Breaking.
J. ACM, 2016

Distributed Strong Diameter Network Decomposition.
CoRR, 2016

Deterministic Distributed (Delta + o(Δ))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity.
CoRR, 2016

On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

Distributed Strong Diameter Network Decomposition: Extended Abstract.
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, 2016

2015
Light Spanners.
SIAM J. Discrete Math., 2015

Steiner Shallow-Light Trees Are Exponentially Lighter than Spanning Ones.
SIAM J. Comput., 2015

Optimal Euclidean Spanners: Really Short, Thin, and Lanky.
J. ACM, 2015

(2Δ - l)-Edge-Coloring is Much Easier than Maximal Matching in the Distributed Setting.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

A Fast Network-Decomposition Algorithm and Its Applications to Constant-Time Distributed Computation - (Extended Abstract).
Proceedings of the Structural Information and Communication Complexity, 2015

2014
Balancing Degree, Diameter, and Weight in Euclidean Spanners.
SIAM J. Discrete Math., 2014

Distributed (Delta+1)-Coloring in Linear (in Delta) Time.
SIAM J. Comput., 2014

Combinatorial algorithms for distributed graph coloring.
Distributed Computing, 2014

Optimizing Budget Allocation in Graphs.
CoRR, 2014

Can quantum communication speed up distributed computation?
Proceedings of the ACM Symposium on Principles of Distributed Computing, 2014

2013
Distributed Graph Coloring: Fundamentals and Recent Developments
Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, ISBN: 9781627050197, 2013

Symmetry breaking depending on the chromatic number or the neighborhood growth.
Theor. Comput. Sci., 2013

Distributed deterministic edge coloring using bounded neighborhood independence.
Distributed Computing, 2013

Fast Constructions of Light-Weight Spanners for General Graphs.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012
Quantum Distributed Network Computing: Lower Bounds and Techniques
CoRR, 2012

Fast Distributed Algorithms for Maximal Matching and Maximal Independent Set
CoRR, 2012

2011
Novel algorithms for the network lifetime problem in wireless settings.
Wireless Networks, 2011

Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners.
ACM Trans. Algorithms, 2011

Narrow-Shallow-Low-Light Trees with and without Steiner Points.
SIAM J. Discrete Math., 2011

Deterministic Distributed Vertex Coloring in Polylogarithmic Time.
J. ACM, 2011

Optimizing Budget Allocation in Graphs.
Proceedings of the 23rd Annual Canadian Conference on Computational Geometry, 2011

2010
Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.
Discrete & Computational Geometry, 2010

Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition.
Distributed Computing, 2010

An Improved Construction of Progression-Free Sets.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009
Distributed (delta+1)-coloring in linear (in delta) time.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008
Synchronizers, Spanners.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Sparse Graph Spanners.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Low Stretch Spanning Trees.
Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

Lower-Stretch Spanning Trees.
SIAM J. Comput., 2008

Bounds on the performance of back-to-front airplane boarding policies.
Oper. Res. Lett., 2008

Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners
CoRR, 2008

Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007
An improved algorithm for radio broadcast.
ACM Trans. Algorithms, 2007

The Hardness of Approximating Spanner Problems.
Theory Comput. Syst., 2007

New length bounds for cycle bases.
Inf. Process. Lett., 2007

A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Principles of Distributed Computing, 2007

2006
Sparse Sourcewise and Pairwise Distance Preservers.
SIAM J. Discrete Math., 2006

An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem.
SIAM J. Comput., 2006

Sublogarithmic approximation for telephone multicast.
J. Comput. Syst. Sci., 2006

A faster distributed protocol for constructing a minimum spanning tree.
J. Comput. Syst. Sci., 2006

Efficient algorithms for constructing (1+epsilon, beta)-spanners in the distributed and streaming models.
Distributed Computing, 2006

A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners
CoRR, 2006

An Approximation Algorithm for the Directed Telephone Multicast Problem.
Algorithmica, 2006

2005
Approximating k-spanner problems for kge2.
Theor. Comput. Sci., 2005

Computing almost shortest paths.
ACM Trans. Algorithms, 2005

Polylogarithmic Additive Inapproximability of the Radio Broadcast Problem.
SIAM J. Discrete Math., 2005

Sparse Distance Preservers and Additive Spanners.
SIAM J. Discrete Math., 2005

A Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem.
SIAM J. Comput., 2005

Improved schedule for radio broadcast.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Sparse source-wise and pair-wise distance preservers.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004
Distributed approximation: a survey.
SIGACT News, 2004

(1+epsilon, beta)-Spanner Constructions for General Graphs.
SIAM J. Comput., 2004

Logarithmic inapproximability of the radio broadcast problem.
J. Algorithms, 2004

Lower-Stretch Spanning Trees
CoRR, 2004

Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Efficient algorithms for constructing (1+, varepsilon;, beta)-spanners in the distributed and streaming models.
Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, 2004

Polylogarithmic Inapproximability of the Radio Broadcast Problem.
Proceedings of the Approximation, 2004

2003
Sublogarithmic approximation for telephone multicast: path out of jungle.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Approximation Algorithm for Directed Telephone Multicast Problem.
Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

2001
The Client-Server 2-Spanner Problem with Applications to Network Design.
Proceedings of the SIROCCO 8, 2001

Approximating k-Spanner Problems for k>2.
Proceedings of the Integer Programming and Combinatorial Optimization, 2001

2000
Strong Inapproximability of the Basic k-Spanner Problem.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000


  Loading...