Newly appointed associate professor Benjamin Rossman is a member of the Theory Group at Duke CS, which engages in cutting-edge research at the intersection of computer science and mathematics. Rossman, who completed his Ph.D. at MIT, previously held faculty positions at the University of Toronto and the National Institute of Informatics in Tokyo.
“I work in complexity theory, an area of theoretical computer science that is concerned with the nature and limits of efficient computation,” says Rossman, who also holds an associate professor appointment with Duke Department of Mathematics. “The holy grail of this area is to show that specific computational problems – for instance, finding the largest clique of mutual friends in a social network graph – cannot be solved by circuits below a certain size.”
Rossman explains that this particular task is the flip side of typical algorithmic design. Rather than designing an algorithm or circuit to solve a particular problem, the goal is to prove that no efficient algorithm exists. These kinds of “impossibility results” in mathematics are notoriously difficult, Rossman says, but such research ultimately sheds light on the obstacles to algorithm design and has significant implications for cryptography.
In recent years, Rossman has been particularly interested in the problem of proving lower bounds for formulas – circuits with the structure of a tree. “This is a major frontier in the area of circuit complexity and a focus of my recent work,” he says.
Rossman moved to North Carolina in January and he is enthused about continuing his theoretical work at Duke. “I’m thrilled to be a member of the great CS and Math Departments,” he says. “I’m excited for the opportunity to work with outstanding students at both undergraduate and graduate levels.”
He’s also hoping to pursue at least one additional ambition: “A personal goal is to learn to dance the Carolina Shag.”
Department of Computer Science
