Philip N. Klein
Appearance
Philip N. Klein | |
---|---|
![]() | |
Nationality | American |
Education | Harvard University (BA) Massachusetts Institute of Technology (PhD) |
Occupations |
|
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
- 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
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
- ^ "Philip N Klein". awards.acm.org. Retrieved 2022-05-29.
- ^ a b "Philip N. Klein". cs.brown.edu. Archived from the original on 2022-01-03. Retrieved 2022-06-27.
- ^ "Philip N. Klein". Radcliffe Institute for Advanced Study at Harvard University. Archived from the original on 2022-04-19. Retrieved 2022-06-27.
- ^ "Philip Klein And Brown CS Alums Receive The 2023 STOC Test Of Time Award".
- ^ 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.
- ^ 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.
- ^ Hochbaum, Dorit. Approximation Algorithms for NP-Hard Problems. p. 158.
- ^ Motwani, Rajeev; Raghavan, Prabhakar (1995). Randomized Algorithms. Cambridge University Press. pp. Section 10.3.
- ^ 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.
- ^ 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.
- ^ 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. doi:10.1137/060649562.
- ^ 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.
- ^ 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.