# Philip Klein

Professor of Computer Science## Contact Information

Box 1910Brown University

Providence, RI 02912

Email: klein at cs.brown.edu

Personal home page:

http://www.cs.brown.edu/~klein/

## Research Areas

Combinatorial Optimization |

Design and Analysis of Algorithms |

Theory of Computation |

## Courses Taught

## About Philip

Background: Born and raised in Berkeley. Started programming in seventh grade, digital logic design in eighth. Attended programming methodology lecture series as a high-school junior, where I first met CS academics such as Dijkstra. Worked at Xerox PARC after high school graduation.

A.B. in Applied Math at Harvard, summer jobs at Xerox PARC, BBN, and MIT. Ph.D. in Computer Science at MIT. Post-doc with Michael Rabin at Harvard. Taught at Brown since 1989, with occasional stints at start-up companies.Research Focus: Algorithms, especially for optimization, and especially for graphs. An example: The traveling salesperson problem involves finding the shortest tour that visits a given set of locations. Computing the best solution is theoretically difficult, but for planar graphs (e.g. road maps), for any desired percentage error, there is an O(n log n) algorithm that is guaranteed to output a solution whose length exceeds the best by at most the given error percentage.

Classes: Developed CS007 (Secrets and Promises: A course on cryptography for nonmajors), and CS53 (Directions: The Matrix in Computer Science). Co-developed CS258 (Solving Hard Problems in Combinatorial Optimization: Theory and Systems) and CS17-18 (Computer Science: An Integrated Introduction)

How did you become interested in computer science?

In ninth grade, I had a job wrote some assembly code examples for a publisher of books on computers. In the office, the publisher had a collection of the old Communications of the ACM. It was in browsing these that I first realized that there was a science to computers.