• Source: Philip N. Klein

      • Philip N. Klein is an American computer scientist and professor at Brown University. His research focuses on algorithms for optimization problems in graphs.
      Klein is a fellow of the Association for Computing Machinery and a recipient of the National Science Foundation's Presidential Young Investigator Award (1991). He is a recipient of Brown University's Philip J. Bray Award for Excellence in Teaching in the Sciences (2007) and was a Fellow at the Radcliffe Institute for Advanced Study at Harvard University (2015–16). He graduated summa cum laude from Harvard with an A.B. in Applied Mathematics and earned a Ph.D. in Computer Science at MIT.


      Key contributions


      In 1991, Klein and his then-students Ajit Agrawal and R. Ravi gave an approximation algorithm for network design that is considered "the first highly sophisticated use of the primal-dual method in the design of approximation algorithms". In 2023, this research received the Annual ACM Symposium on Theory of Computing (STOC) 30-year Test of Time Award.
      In 1994, Klein and Robert E. Tarjan gave a randomized linear-time algorithm to find minimum spanning trees, based on a sampling technique due to David Karger.
      In 2005, Klein gave a linear-time algorithm to find a nearly optimal traveling salesman tour in a planar graph.


      Books


      Klein has published two textbooks:

      Klein, Philip N. (2014). A cryptography primer : secrets and promises. New York, NY, USA. ISBN 978-1-107-01788-7. OCLC 863632974.{{cite book}}: CS1 maint: location missing publisher (link)
      Klein, Philip N. (2013). Coding the matrix : linear algebra through applications to computer science. [Newton, Mass.]: Newtonian Press. ISBN 978-0-615-85673-5. OCLC 855087626.


      References

    Kata Kunci Pencarian: