Brown CS News

Professor Philip Klein of Brown University’s Computer Science Department has just received a one-year fellowship from the Radcliffe Institute for Advanced Study at Harvard University. The fellowship, which has an acceptance rate of only four percent, has previously benefited such luminaries as author Junot Díaz, Senator Elizabeth Warren, and theoretical physicist Lisa Randall, as well as multiple Pulitzer Prize winners, a US Poet Laureate, and a Tony Award winner. Colleagues at Brown who have recently received the fellowship include Professor Susan Moffitt and Professor Sheila Blumstein.

As one of fifty scholars, scientists, and artists from around the world, Philip will pursue innovative and independent work as part of a multidisciplinary community, enriched by the contribution of other fellows and supported by dedicated undergraduate researchers. “My project,” he says, “aims to apply algorithms to help in data-driven research in social science, especially research on urban areas. Specifically, we believe that many combinatorial-optimization problems in graphs (networks) are inherently difficult computationally, but intractability can sometimes be circumvented by restricting the input to be a planar graph, one that can be drawn on the plane without crossings.” 

Using planarity-exploiting algorithms, Philip explains, has yielded powerful algorithmic techniques. “Because planar graphs can model phenomena in the plane such as distances in a road map or neighborhood boundaries more faithfully than a purely geometric approach, these techniques are likely to be useful in addressing problems of a spatial or geographical nature.”