Homepage of Michael Elkin

Michael Elkin Postdoctoral Fellow in the Department of Computer Science at the Yale University . Research Interests: Graph Algorithms Low-Distortion Embeddings Distributed Computing Complexity Theory Approximation Algorithms and Hardness of Approximation
Address: Department of Computer Science Yale University New Haven,CT Room: 411, 51 Prospect street. Phone: +1 (203) 432 1276 Fax: +1 (203) 432 0593 (attn. Michael Elkin) Email: `elkin at cs.yale.edu`
Biography: Starting from September 2003, a postdoctoral associate in the department of Computer Science, Yale university. Sep. 2002 - Aug. 2003: Member of the School of Mathematics, Institute for Advanced Study, Princeton. Oct. 1998 - Aug. 2002: PhD student at Weizmann Institute of Science, Rehovot, Israel. Journal Papers: M. L. Elkin and D. Peleg, (1+e,b)-Spanner Constructions for General Graphs, SIAM J. Comput. 33(3): 608-631 (2004) M. L. Elkin and G. Kortsarz, Logarithmic Inapproximability of the Radio Broadcast Problem, J. Algorithms 52(1): 8-25 (2004) M. L. Elkin, Computing Almost Shortest Paths, to appear in Transactions on Algorithms Conference Papers: D.Coppersmith and M. Elkin, Sparse Sourse-wise and Pair-wise Distance Preservers, to appear in Proc. ACM-SIAM on Discrete Algorithms, SODA'05, M. L. Elkin, An Unconditional Lower Bound on the Hardness of Approximation of Distributed Minimum Spanning Tree Problem, Proc. 36th Annual ACM Symp. on Theory of Computing Chicago, IL, USA, June, 2004, pp.331-340. M. L. Elkin and G. Kortsarz, Polylogarithmic Inapproximability of the Radio Broadcast Problem, Proc. of 7th. International Workshop on > Approximation Algorithms for Combinatorial Optimization Problems, pp. 105-114, Cambridge, MA, 2004. M. L. 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. M. L. Elkin and D. Peleg, (1+e,b)-Spanner Constructions for General Graphs, in Proc. 33rd Annual ACM Symp. on Theory of Computing, pp. 173-182, Greece, Crete, July, 2001. M. L. Elkin and G. Kortsarz, Combinatorial Logarithmic Approximation Algorithm for Directed Telephone Broadcast Problem, in Proc. 34th Annual ACM Symp. on Theory of Computing, Canada, Montreal, May, 2002. B. Bollobas, D.Coppersmith and M. L. Elkin, Sparse Subgraphs that Preserve Long Distances and Additive Spanners, to appear in Proc. 14th Annual ACM-Siam Symp. on Discrete Algorithms, USA, MD, Baltimore, January, 2003. M. L. Elkin and G. Kortsarz, Sublogarithmic Approximation for Telephone Multicast: Path out of Jungle, to appear in Proc. 14th Annual ACM-Siam Symp. on Discrete Algorithms, USA, MD, Baltimore, January, 2003. M. L. Elkin, Computing Almost Shortest Paths, in Proc. 20th ACM Symp. on Principles of Distributed Computing, pp. 53-62, Newport, Rhode Island, USA, August, 2001. M. L. Elkin and D. Peleg, Strong Inapproximability of the Basic k-Spanner Problem, in Proc. 27th Int. Colloq. on Automata, Languages and Programming, Geneva, Switzerland, July 2000, pp. 636-648. 2000. M. L. Elkin and G. Kortsarz, Approximation algorithm for the directed telephone multicast problem, in Proc. 30th International Colloq. on Automata, Languages and Programming}, Eindhoven, Netherlands, June 2003. M. L. Elkin and D. Peleg, Approximating k-spanner problems for k > 2, in: Proc. 8th Conference in Integer Programming and Combinatorial Optimization}, Utrecht, Netherlands, June, 2001. M. L. Elkin and D. Peleg, The Hardness of Approximating Spanner Problems, in Proc. 17th Symp. on Theoretical Aspects of Computer Science, Lille, France, Feb. 2000, 370-381. M. L. Elkin and D. Peleg, The Client-Server 2-Spanner problem and Applications to Network Design, in Proc. 8th International Colloq. on Structural Information and Communication Complexity, Vall de Nuria, Catalonia, Spain, July, 2001. 2001. D. Coppersmith, M. L. Elkin and O. Regev, Sublinear Distributed Protocol for Constructing Shortest-Path-Tree on Weighted Clique, in preparation.