Michael Elkin
A
faculty member (an associate professor) in the Department of
Computer Science at the Ben-Gurion
University . 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
Beer-Sheva, Israel |
|
Teaching
Classes taught in
the past
A Postdoc Position Available
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.
Program Committees
PODC 2012,
SWAT 2012,
ICDCN 2012,
SOFSEM 2012,
PODC 2011,
SWAT 2008,
SIROCCO 2008,
ALGOSENSORS 2008.Graduate
Students
Leonid Barenboim (Ph.D.) Finished M.Sc. summa cum laude under my supervision, and won Zabey prize for the best M.Sc. thesis in the Faculty of Natural Sciences, and Rector's prize for the best Ph.D. thesis. Won Adams Fellowship. Arnold Filtzer (M.Sc.) (co-advised with Ofer Neiman) Former
Students
Monograph (a preliminary draft)Distributed Graph Coloring. Journal
Papers
Symmetry Breaking Depending on Chromatic Number of Neighborhood Growth Accepted to Theoretical Computer Science Distributed Deterministic Edge Coloring using Bounded Neighborhood Independence To appear in Distributed Computing, Special Issue for PODC'11 conference Energy Fluctuations Shape Free Energy of Non-Specific Biomolecular Interactions, In Journal of Statistical Physics, Vol. 146, Number 4, pp. 870-877, 2012. Distributed Deterministic Vertex Coloring in Polylogarithmic Time, In Journal of ACM, Vol. 58, No. 5, 23, 2011. Narrow-Shallow-Low-Light Trees, with and without Steiner Points, In SIAM Journal on Discrete Mathematics, Vol. 25, No. 1, pp.181-210, 2011. Novel Algorithms for the Network Lifetime Problem in Wireless Setting Wireless Networks journal, Vol. 17, Issue 2, pp. 397-410, 2011. An Improved Construction of Progression-Free Sets, Israeli J. Math., Vol. 184, pp. 93-128, 2011 see also the archive version. Below on this web-page one can also find the more TCS-oriented 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. Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners, Discrete and Computational Geometry (an invited paper), Vol. 43, Issue 4, pp. 736-783, 2010. Sublogarithmic Distributed MIS Algorithm for Sparse Graphs Using Nash-Williams Decomposition, Distributed Computing, special issue of PODC'08, vol. 22, pp. 363-379, 2010. Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners, Transactions on Algorithms, Vol. 7, No. 2, Article 20, March 2011. Lower-Stretch Spanning Trees , In special issue of SIAM Journal on Computing for STOC'05 conference, Vol. 38, No. 2, pp. 608-628, 2008. Bounds on the Performance of Back-to-front Airplane Boarding Policies, Operations Research Letters, 36(5), pp. 597-601, 2008. New Bounds for Cycle Bases, Information Processing Letters, 104(5), 186-193, 2007 SIAM J. Comput. 33(3): 608-631 (2004) Logarithmic Inapproximability of the Radio Broadcast Problem, J. Algorithms 52(1): 8-25 (2004) Computing Almost Shortest Paths, in Transactions on Algorithms, Vol. 1, No. 2, pp.283-323, 2005. Combinatorial Logarithmic Approximation Algorithm for Directed Telephone Broadcast Problem, SIAM Journal on Computing, Vol. 35, Num. 3, pp. 672-689 Approximating k-spanner problem for k > 2 , Theoretical Computer Science 337 (2005) 249-277 Polylogarithmic Additive Hardness of Approximating Radio Broadcast Problem , SIAM Journal of Discrete Mathematics Vol. 19, Num. 4, pp. 881-899, 2005. Sparse Subgraphs that Preserve Long Distances and Additive Spanners, SIAM Journal on Discrete Mathematics, Vol. 19, No. 4, pp. 1029-1055, 2006 Efficient constructions of (1+e,b)-spanners in the Streaming and Distributed Models, Distributed Computing, 18(5), pages 375-385, 2006.
Survey
Papers
Conference
Papers
Euclidean Spanners: Really Short, Thin and Lanky , To appear in Proc. of the 45th ACM Symp. on Theory of Computing, STOC'13, Palo-Alto, CA, USA, June 2013 Fast Constructions of Light-Weight Spanners for General Graphs , In Proc. of the ACM-SIAM Symp. on Discrete Algorithms, SODA'13, New Orleans, LA, USA, Jan. 2013 The Locality of Distributed Symmetry Breaking , To appear in Proc. of 53rd Annual Symp. on Theoretical Foundations of Computer Science, FOCS'12, New Brunswick, NJ, USA, Oct. 2012 Steiner Shallow-Light Trees are Exponentially Lighter than Spanning Ones , In Proc. of 52nd Annual Symp. on Theoretical Foundations of Computer Science, FOCS'11, pp. 373-382, Palm Springs, CA, USA, Oct. 2011 Combinatorial Algorithms for Distributed Graph Coloring , In Proc. of International Symp. on Distributed Computing, DISC'11, Rome, Italy, Sep. 2011 Optimizing Budget Allocation in Graphs , In Proc. of Canadian Conference on Computational Geometry, CCCG'11, Toronto, CA, Aug. 2011 Distributed Deterministic Edge Coloring Using Bounded Neighborhood Independence , In Proc. of International Symp. on Principles of Distributed Computing, PODC'11, pp. 129-138, San Jose, CA, USA, June 2011. Received PODC'11 best student paper award. Balancing Degree, Weight and Diameter in Euclidean Spanners , In Proc. of European Symp. on Algorithms, ESA'10, pp. 48-59, Liverpool, UK, Sep. 2010. Deterministic Distributed Coloring in Polylogarithmic Time, In Proc. of International Symp. on Principles of Distributed Computing, PODC'10, pp. 410-419 Zurich, Switzerland, July 2010. Received PODC'10 best paper award. An Improved Constructions of Progression-Free Sets, In Proc. SIAM-ACM Symp. on Discr. Alg., SODA'10, pp.886-905, Austin, TX, USA, 2010. Narrow-Shallow-Low-Light Trees, with and without Steiner Points, In Proc. European Symp. on Algorithms, ESA'09, pp. 215-226, Copenhagen, Denmark, 2009. Distributed (Delta+1)-Coloring in Linear (in Delta) Time, In Proc. Symp. on Theory of Computing, STOC'09, pp.111-120, Bethesda, MD, 2009. Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners , In Proc. IEEE Annual Symp. on Foundations of Comp. Science, FOCS'08, pp. 519-528, Philadelphia, PA, 2008. In Proc. of International Symp. on Principles of Distributed Computing, PODC'08, pp. 25-34, Toronto, Canada 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. 425-438, Antibes, France Fully Dynamic Distributed Algorithm for Maintaining Sparse Spanners, in Proc. of International Symp. on Principles of Distributed Computing, PODC'07 Portland, Oregon, USA Streaming and Fully Dynamic Centralized Algorithms for Maintaining Sparse Spanners, in Proc. of International Colloq. on Automata, Languages, and Programming, ICALP'07 Wroclaw, Poland Lower Stretch Spanning Trees, in Proc. ACM Symposium on Theory of Computing, STOC'05, pp. 494-503 Baltimore, Maryland, USA. This paper is mentioned among "the significant papers on new areas that were published in Proceedings of SIGACT conferences in 2005" in the SIGACT Annual Report 2005 (by Hal Gabow)
The
Client-Server 2-Spanner problem and Applications to Network Design, |
|
Misc
- My story (in Russian)
Otkrovenie (open with Word) .