When Nathan Klein started graduate school two years ago, his advisers proposed a modest plan: to work together on one of the most famous, long-standing problems in theoretical computer science.
Even if they didn’t manage to solve it, they figured, Klein would learn a lot in the process. He went along with the idea. “I didn’t know to be intimidated,” he said. “I was just a first-year grad student—I don’t know what’s going on.”
Now, in a paper posted online in July, Klein and his advisers at the University of Washington, Anna Karlin and Shayan Oveis Gharan, have finally achieved a goal computer scientists have pursued for nearly half a