Philip Klein

Philip Klein

Professor of Computer Science

Contact Information

Box 1910
Brown University
Providence, RI 02912
Email: klein at
Personal home page:

Research Areas

Combinatorial Optimization
Design and Analysis of Algorithms
Theory of Computation

Courses Taught

CSCI0170   CS: An Integrated Introduction
CSCI0180   CS: An Integrated Introduction
CSCI0220   Introduction to Discrete Structures and Probability
CSCI2580   Solving Hard Problems in Combinatorial Optimization: Theory and Systems
CSCI1570   Design and Analysis of Algorithms
CSCI2500-A   Advanced Algorithms

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.

All publications by Philip Klein