Home Page 

Leonid Barenboim, Associate Professor

Leonid Barenboim
Contact Info

The Open University of Israel Department of Mathematics and Computer Science 1 University Road P.O.B. 808 Ra’anana 43107, Israel
Office:972-9-7781259 Email:[email protected]

Additional Information

Areas of Interest
  • Distributed algorithms
  • Communication networks
  • Dynamic algorithms
  • Sublinear time algorithms
  • Local algorithms
  • Graph theory
  • Network security
  • Applications of the abovementioned fields in Big Data analysis

I am a faculty member in the Department of Mathematics and Computer Science at The Open University of Israel.
Before joining the Open University I was a postdoctoral fellow in a joint program of the Simons Institute for the Theory of Computing at UC Berkeley and I-CORE Israel at Weizman Institute, hosted by Prof. David Peleg.
I obtained my Ph.D. in Computer Science at Ben-Gurion University of the Negev under the supervision of Prof. Michael Elkin.

Selected Publications:

 

Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Synthesis Lectures on Distributed Computing. 2013

Leonid Barenboim and Tzalik Maimon. Fully Dynamic Graph Algorithms Inspired by Distributed Computing: Deterministic Maximal Matching and Edge Coloring in Sublinear Update-Time. ACM Journal on. Experimental. Algorithmics. 2019

Leonid Barenboim: Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic, and Faulty Networks. Journal of ACM. 2016

Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider: The Locality of Distributed Symmetry Breaking. Journal of ACM. 2016

Leonid Barenboim, Michael Elkin and Fabian Kuhn. Distributed (Delta + 1)-Coloring in Linear (in Delta) Time. SIAM Journal on Computing. 2014

Leonid Barenboim, Shlomi Dolev and Rafail Ostrovsky. Deterministic and Energy-Optimal Wireless Synchronization. Transactions on Sensor Networks. 2014

Leonid Barenboim and Michael Elkin. Combinatorial Algorithms for Distributed Graph Coloring. Distributed Computing Journal. 2014

Leonid Barenboim and Michael Elkin. Deterministic Distributed Vertex Coloring in Polylogarithmic Time. Journal of ACM. 2011

Leonid Barenboim and Michael Elkin. Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence. Distributed Computing Journal, special issue of PODC'11

Leonid Barenboim and Michael Elkin. Sublogarithmic Distributed MIS Algorithm for Sparse Graphs using Nash-Williams Decomposition. Distributed Computing Journal, special issue of PODC'08

Leonid Barenboim, Gal Oren: Distributed Backup Placement in One Round and its Applications to Maximum Matching Approximation and Self-Stabilization, SOSA 2020, Salt Lake City, UT, USA

Leonid Barenboim, Yaniv Tzur.  Distributed symmetry-breaking with improved vertex-averaged complexity,  ICDCN 2019, Bangalore, India

Leonid Barenboim, Michael Elkin, Uri Goldenberg. Locally-Iterative Distributed (Δ+ 1)--Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. PODC 2018, Egham, United Kingdom

PODC 2018 Best Paper Award:

 Leonid Barenboim, Michael Elkin, Tzalik Maimon: Leonid Barenboim, Michael Elkin, Tzalik Maimon: Deterministic Distributed (Delta + o(Delta))-Edge-Coloring, and Vertex-Coloring of Graphs with Bounded Diversity. PODC 2017, Washington, DC, USA

Leonid Barenboim: Deterministic (Δ + 1)-Coloring in Sublinear (in Δ) Time in Static, Dynamic and Faulty Networks. PODC 2015. Donostia-San Sebastián, Spain

PODC 2015 Best Paper Award:

Leonid Barenboim and David Peleg: Nearly Optimal Local Broadcasting in the SINR Model with Feedback. SIROCCO 2015. Montserrat, Spain

Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The Locality of Distributed Symmetry Breaking. In proc. of the Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA

Leonid Barenboim. On the Locality of Some NP-Complete Problems. In proc. of the International Colloquium on Automata, Languages and Programming, ICALP 2012, Warwick, UK

ICALP 2012 Best Student Paper Award. (Track C.):

Leonid Barenboim, Shlomi Dolev and Rafail Ostrovsky. Deterministic and Energy-Optimal Wireless Synchronization. In proc. of the International Symposium on Distributed Computing, Disc 2011, Rome, Italy

Leonid Barenboim and Michael Elkin. Combinatorial Algorithms for Distributed Graph Coloring. In proc. of the International Symposium on Distributed Computing, Disc 2011, Rome, Italy

Leonid Barenboim and Michael Elkin. Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence. In proc. of the Symposium on the Principles of Distributed Computing, PODC 2011, San Jose, California, USA

PODC 2011 Best Student Paper Award:

Leonid Barenboim and Michael Elkin. Deterministic Distributed Vertex Coloring in Polylogarithmic Time. In proc. of the Symposium on the Principles of Distributed Computing, PODC 2010, Zurich, Switzerland

PODC 2010 Best Paper Award:

Leonid Barenboim and Michael Elkin. Distributed (Delta + 1)-coloring in linear (in Delta) time. In proc. of the Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA

Leonid Barenboim and Michael Elkin. Sublogarithmic Distributed MIS Algorithm for Sparse Graphs using Nash-Williams Decomposition. In proc. of the Symposium on the Principles of Distributed Computing, PODC 2008, Toronto, Canada

Leonid Barenboim, Distributed Symmetry Breaking from a Local Point of View. SIGACT News , 46(4), December 2015

Leonid Barenboim, A review of PODC 2010, SIGACT News, 41(4), December 2010