Jump to content

Philip N. Klein

Add links
From Wikipedia, the free encyclopedia
(Redirected from Draft:Philip N. Klein)
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".[4] In 2023, this research received the Annual ACM Symposium on Theory of Computing (STOC) 30-year Test of Time Award.[5][6][7][4]
  • 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. ^ a b Hochbaum, Dorit. Approximation Algorithms for NP-Hard Problems. p. 158.
  5. ^ "Philip Klein And Brown CS Alums Receive The 2023 STOC Test Of Time Award".
  6. ^ 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.
  7. ^ 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.
  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=1245483509"