Philip N. Klein

Add links
From Wikipedia, the free encyclopedia
For other people named Philip Klein, see Philip Klein (disambiguation).
Philip N. Klein
NationalityAmerican
EducationHarvard University (BA)
Massachusetts Institute of Technology (PhD)
Occupations
  • Computer scientist
  • professor

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[1] and a recipient of the National Science Foundation's Presidential Young Investigator Award (1991).[2] 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).[2] He graduated summa cum laude from Harvard with an A.B. in Applied Mathematics and earned a Ph.D. in Computer Science at MIT.[3]

Key contributions[edit]

  • 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.[4][5][6][7]
  • 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.[8][9][10]
  • In 2005, Klein gave a linear-time algorithm to find a nearly optimal traveling salesman tour in a planar graph.[11][12]

Books[edit]

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)[13]
  • 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.[14]

References[edit]

  1. ^ "Philip N Klein". awards.acm.org. Retrieved 2022-05-29.
  2. ^ a b "Philip N. Klein". cs.brown.edu. Archived from the original on 2022-01-03. Retrieved 2022-06-27.
  3. ^ "Philip N. Klein". Radcliffe Institute for Advanced Study at Harvard University. Archived from the original on 2022-04-19. Retrieved 2022-06-27.
  4. ^ "Philip Klein And Brown CS Alums Receive The 2023 STOC Test Of Time Award".
  5. ^ Agrawal, Ajit; Klein, Philip; Ravi, R. (1995). "When trees collide: An approximation algorithm for the generalized Steiner problem on networks". SIAM Journal on Computing. 24 (3): 440–456. doi:10.1137/S0097539792236237.
  6. ^ Agrawal, Ajit; Klein, Philip; Ravi, R. (1991). ""When trees collide: An approximation algorithm for the generalized Steiner problem on networks"". Proceedings of the 23rd Annual ACM Symposium on Theory of Computing: 134–144.
  7. ^ Hochbaum, Dorit. Approximation Algorithms for NP-Hard Problems. p. 158.
  8. ^ Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. Cambridge University Press. pp. Section 10.3.
  9. ^ Karger, David R.; Klein, Philip N.; Tarjan, Robert E. (1995). "A randomized linear-time algorithm to find minimum spanning trees". Journal of the ACM. 42 (2): 321–328. doi:10.1145/201019.201022. S2CID 832583.
  10. ^ Klein, Philip N.; Tarjan, Robert E. (1994). "A randomized linear-time algorithm for finding minimum spanning trees". Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94. pp. 9–15. doi:10.1145/195058.195084. ISBN 0897916638. S2CID 15667728.
  11. ^ Klein, Philip N. (2008). "A linear-time approximation scheme for TSP in undirected planar graphs with edge-weights". SIAM Journal on Computing. 37 (6): 1926–1952. CiteSeerX 10.1.1.155.897. doi:10.1137/060649562.
  12. ^ Klein, Philip N. (2005). "A linear-time approximation scheme for planar weighted TSP". 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05). pp. 647–656. doi:10.1109/SFCS.2005.7. ISBN 0-7695-2468-0. S2CID 16327107.
  13. ^ 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)
  14. ^ 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.


Stub icon

This biographical article relating to a computer specialist in the United States is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Philip_N._Klein&oldid=1211540529"