Edge Rewrite
everything Source code View original
// HTMLRewriter · presentation

This page was redesigned at the edge.

Cloudflare fetched the original article and streamed it through HTMLRewriter to apply an entirely new visual system without rebuilding the source page.

// request.cf · coarse context

A page that knows where it met you.

Only coarse request metadata is shown. This demo does not display or persist visitor IP addresses.

Country
US
Cloudflare location
CMH
Connection
HTTP/2
Language
Not provided

Ray ID: a46433fedc4fddf0

Jump to content

// Workers AI · dad joke modeIs Philip N. Klein a good climber? He's got a great Klein of rope.

Edit links
From Wikipedia, the free encyclopedia
(Redirected from Draft:Philip N. Klein)
Philip N. Klein
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. 1 2 "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. 1 2 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". 23 June 2023.
  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 0-89791-663-8. 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. 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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Philip_N._Klein&oldid=1375127048"