Philip Klein Professor of Computer Science

Professor Klein received an undergraduate degree in Applied Mathematics from Harvard and a doctoral degree in Computer Science from MIT. He was a postdoctoral fellow at Harvard before coming to Brown. He recently worked in the software industry for two years while on leave from Brown.

Brown Affiliations

Research Areas

research overview

Philip Klein is interested in the design of algorithms and algorithmic techniques, especially algorithms for combinatorial optimization (finding the best solution among a vast but finite set) and for analyzing networks (graphs).

research statement

Philip Klein does research in algorithms and data structures, especially in the area of combinatorial optimization, and especially those problems involving graphs.

Past work includes approximation algorithms (including the development of the primal-dual method for the Steiner forest problem), randomized algorithms (including the first linear-time algorithm for finding minimum-cost spanning trees), and parallel algorithms (including the first linear-processor, polylog-time algorithms for fundamental problems in planar graphs, e.g. topological sorting and shortest paths).

Recent work focuses on optimization problems in planar graphs, such as finding an approximately minimum-cost traveling salesperson tour in an undirected planar graph and finding a maximum st-flow in a directed planar graph.

funded research

Gift to support research (PI), Northern Telecom, Inc., , 1999

Algorithmic Techniques for Optimization in Graphs (PI), National Science Foundation, $229,154, 1997 - 2003

Gift to support research (PI), Northern Telecom, Inc., , 1997

Secrets and Promises: A Course on Cryptography for Nonmajors (PI), National Science Foundation, $56,326, 1996 - 1997

Workshop on Approximation Algorithms, Mar 24-26, 1993, New Brunswick, New Jersey (PI), National Science Foundation, $4,000, 1993

NSF Research Experiences for Undergraduates supplement award (PI), National Science Foundation, , 1992

ONR Grant "High-Performance Design Environments" (PI), Matching-fund contributions from Xerox, Thinking Machines, Honeywell, DEC, CPLEX, , 1991 - 1994

Presidential Young Investigator Award: Computational Problems in Network Design (PI), National Science Foundation, $320,178, 1991 - 1996

NSF Research Opportunities for Undergraduates supplement award (PI), National Science Foundation, , 1991

The Role of Approximation and Parallelism in Solving Graph Problems Quickly (PI), National Science Foundation, $46,436, 1990 - 1992