Michael Elkin
A
faculty member (an associate professor) in the Department of
Computer Science at the BenGurion
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 BenGurion
University
BeerSheva, Israel 

Teaching
Classes taught in
the past
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.
Program Committees
SODA 2014 ,
DISC 2013 ,
PODC 2012,
SWAT 2012,
ICDCN 2012,
SOFSEM 2012,
PODC 2011,
SWAT 2008,
SIROCCO 2008,
ALGOSENSORS 2008.Graduate
Students
Arnold Filtzer (M.Sc.) (coadvised with Ofer Neiman)
Former
Students
Shay Solomon (Ph.D.),
Leonid Barenboim (finished M.Sc. and Ph.D. under my supervision), Elad Horev (M.Sc.) Monograph (a preliminary draft)Journal
Papers
In Journal of Statistical Physics, Vol. 146, Number 4, pp. 870877, 2012. In Journal of ACM, Vol. 58, No. 5, 23, 2011. In SIAM Journal on Discrete Mathematics, Vol. 25, No. 1, pp.181210, 2011. Wireless Networks journal, Vol. 17, Issue 2, pp. 397410, 2011. Israeli J. Math., Vol. 184, pp. 93128, 2011 see also the archive version. Below on this webpage one can also find the more TCSoriented 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. Discrete and Computational Geometry (an invited paper), Vol. 43, Issue 4, pp. 736783, 2010. Distributed Computing, special issue of PODC'08, vol. 22, pp. 363379, 2010. Transactions on Algorithms, Vol. 7, No. 2, Article 20, March 2011. In special issue of SIAM Journal on Computing for STOC'05 conference, Vol. 38, No. 2, pp. 608628, 2008. Operations Research Letters, 36(5), pp. 597601, 2008. Information Processing Letters, 104(5), 186193, 2007 SIAM J. Comput. 33(3): 608631 (2004) J. Algorithms 52(1): 825 (2004) in Transactions on Algorithms, Vol. 1, No. 2, pp.283323, 2005. SIAM Journal on Computing, Vol. 35, Num. 3, pp. 672689 Theoretical Computer Science 337 (2005) 249277 SIAM Journal of Discrete Mathematics Vol. 19, Num. 4, pp. 881899, 2005. SIAM Journal on Discrete Mathematics, Vol. 19, No. 4, pp. 10291055, 2006 Distributed Computing, 18(5), pages 375385, 2006. Algorithmica, 45(4), pages 569583, 2006. Journal of Computer and System Sciences, Vol. 72(4), pp. 648659, June 2006. SIAM Journal of Discrete Mathematics, Vol. 20, Number 2, pages 463501. SIAM Journal on Computing, Vol. 36, No. 2, pp. 433456, 2006. Transactions on Algorithms, 3(1), 2007. Journal of Computer and System Sciences, Vol. 72, Number 8, pp. 12821308, 2006. Theory Comput. Systems, Vol. 41, pp. 691729, 2007. Survey
Papers
in ACM SIGACT News Distributed Computing Column Volume 35, Number 4 (Whole number 132), Dec. 2004, pp. 4057. In Encyclopedia of Algorithms, ed. MingYang Kao. In Encyclopedia of Algorithms, ed. MingYang Kao. In Encyclopedia of Algorithms, ed. MingYang Kao. Conference
Papers
In Proc. of the 45th ACM Symp. on Theory of Computing, STOC'13, pp. 645654, PaloAlto, CA, USA, June 2013 In Proc. of the ACMSIAM Symp. on Discrete Algorithms, SODA'13, pp. 513525, New Orleans, LA, USA, Jan. 2013 In Proc. of 53rd Annual Symp. on Theoretical Foundations of Computer Science, FOCS'12, pp. 321330, New Brunswick, NJ, USA, Oct. 2012 In Proc. of 52nd Annual Symp. on Theoretical Foundations of Computer Science, FOCS'11, pp. 373382, Palm Springs, CA, USA, Oct. 2011 In Proc. of International Symp. on Distributed Computing, DISC'11, Rome, Italy, Sep. 2011 In Proc. of Canadian Conference on Computational Geometry, CCCG'11, Toronto, CA, Aug. 2011 In Proc. of International Symp. on Principles of Distributed Computing, PODC'11, pp. 129138, San Jose, CA, USA, June 2011. Received PODC'11 best student paper award. In Proc. of European Symp. on Algorithms, ESA'10, pp. 4859, Liverpool, UK, Sep. 2010. In Proc. of International Symp. on Principles of Distributed Computing, PODC'10, pp. 410419 Zurich, Switzerland, July 2010. Received PODC'10 best paper award. In Proc. SIAMACM Symp. on Discr. Alg., SODA'10, pp.886905, Austin, TX, USA, 2010. In Proc. European Symp. on Algorithms, ESA'09, pp. 215226, Copenhagen, Denmark, 2009. In Proc. Symp. on Theory of Computing, STOC'09, pp.111120, Bethesda, MD, 2009. In Proc. IEEE Annual Symp. on Foundations of Comp. Science, FOCS'08, pp. 519528, Philadelphia, PA, 2008. In Proc. of International Symp. on Principles of Distributed Computing, PODC'08, pp. 2534, Toronto, Canada In Proc. of the 7th International Conf. on Adhoc and Wireless Networks, AdhocNow'08, pp. 425438, Antibes, France in Proc. of International Symp. on Principles of Distributed Computing, PODC'07 Portland, Oregon, USA in Proc. of International Colloq. on Automata, Languages, and Programming, ICALP'07 Wroclaw, Poland in Proc. ACM Symposium on Theory of Computing, STOC'05, pp. 494503 Baltimore, Maryland, USA. in Proc. ACMSIAM on Discrete Algorithms, SODA'05, Vancouver, British Columbia, Canada. in Proc. ACMSIAM on Discrete Algorithms, SODA'05, Vancouver, British Columbia, Canada. in Proc. 23rd ACM Symp. on Principles of Distributed Computing, PODC'04, pp. 160168, St. John's, Newfoundland, Canada. Proc. 36th Annual ACM Symp. on Theory of Computing, STOC'04 Chicago, IL, USA, June, 2004, pp.331340. Proc. of 7th. International Workshop on > Approximation Algorithms for Combinatorial Optimization Problems, pp. 105114, Cambridge, MA, 2004. in Proc. 14th Annual ACMSiam Symp. on Discrete Algorithms, SODA'03, USA, MD, Baltimore, January, 2003. in Proc. 14th Annual ACMSiam Symp. on Discrete Algorithms,SODA'03, USA, MD, Baltimore, January, 2003. in Proc. 30th International Colloq. on Automata, Languages and Programming}, Eindhoven, Netherlands, June 2003. in Proc. 34th Annual ACM Symp. on Theory of Computing, STOC'02, Canada, Montreal, May, 2002. in Proc. 33rd Annual ACM Symp. on Theory of Computing, STOC'01, pp. 173182, Greece, Crete, July, 2001. in Proc. 20th ACM Symp. on Principles of Distributed Computing, pp. 5362, Newport, Rhode Island, USA, August, 2001. in Proc. 27th Int. Colloq. on Automata, Languages and Programming, Geneva, Switzerland, July 2000, pp. 636648. 2000. (Contains an error in the proof that highgirth LabelCover is still hard to approximate within exp{log^{1eps} n} factor. See my TCS paper with Peleg and a paper by Mike Dinitz, Guy Kortsarz and Ran Raz for more details about the error. The latter paper also proves that LabelCover with high girth is indeed hard to approximate within this factor.) in Proc. 8th Conference in Integer Programming and Combinatorial Optimization, Utrecht, Netherlands, June, 2001. in Proc. 17th Symp. on Theoretical Aspects of Computer Science, Lille, France, Feb. 2000, 370381. in Proc. 8th International Colloq. on Structural Information and Communication Complexity, Vall de Nuria, Catalonia, Spain, July, 2001. (progressions), (coloring), (oracles) 
