The beauty of computer science

As a sophomore at Harvard College in 1992, Salil Vadhan skeptically and rather grudgingly enrolled in an introductory departmental course that a friend had cajoled him into taking.

The course was “Computer Science 121: Introduction to Formal Systems and Computation,” a class that he would revisit a little more than a decade later — as the professor.

“I came to college thinking that I already knew what computer science was about, after having done a significant amount of programming in high school,” Vadhan explained from the University of California, Berkeley, where he is on a yearlong sabbatical from his duties as the Gordon McKay Professor of Computer Science and Applied Mathematics. “I didn’t have much interest in pursuing it further, and I had already decided to concentrate in either math or physics. CS 121 showed me that there was much more to the subject than I had imagined. It opened my eyes to the deep and beautiful theory on which computer science is built.”

His interest in the subject renewed, Vadhan decided to concentrate in computer science (jointly with math) after all. He spent four years working extensively with professors and mentors in electrical engineering and computer science, returning as a junior colleague only two years after completing his Ph.D. at the Massachusetts Institute of Technology (MIT).

At Harvard, he taught classes in his research fields, cryptography and computational complexity, until a serendipitous turn of events brought him back to the CS 121 classroom. In 2004, Harry Lewis, his former professor, went on sabbatical, and Vadhan was given the opportunity to take up the teaching post.

“What I found extraordinary in returning to CS 121,” Vadhan said, “was that students could learn about open problems at the frontier of the field — basic problems that we aren’t even close to solving — in an introductory course. That’s pretty remarkable — in most other fields, the basic problems have been solved for a long time.”

Vadhan’s own research in computational complexity touches upon one of the most formidable problems in computer science — the P vs. NP problem, one of the Clay Mathematics Institute’s Seven Millennium Problems and, as Vadhan noted, “one of the most important open problems in computer science and mathematics.”

The P vs. NP problem, said Vadhan, addresses a common-sense observation of how people compute, or solve problems, in the real world.

“Given our everyday experience of solving problems, it seems obvious that there are certain kinds of problems in which it’s easier to check a solution than it is to come up with one from scratch,” he said. “Take, for example, the famous Traveling Salesman problem: If a traveling salesman has X number of cities to visit and Y budget at a given mileage cost of travel, what’s a round-trip route that he can take to visit all X cities without spending more than Y?

“It seems to be a hard question, but if I gave you an answer, you could quickly check it against the criteria to see if it was right,” Vadhan said. “That’s an NP problem. The question is, how do we know that the NP problem isn’t really a P problem [an easy-to-solve problem] that we just haven’t figured out a better way to solve?”

That question has been formative for Vadhan’s research in cryptography. Current security systems, he notes, rely on the assumption that the codes used to protect information would require impossibly large amounts of computational resources to crack — in short, that they are NP problems, not P problems.

But there is no guarantee. The codes could, in fact, be P problems in disguise; a computational shortcut might be found that could crack the code and endanger the security of the protected information. As Vadhan observed, “Without mathematical proof that NP isn’t equal to P, the security of our systems is based on conjecture. We’ll never know for sure if the codes we use are absolutely secure until that question is solved.”

In the meantime, Vadhan has been working to minimize the conjectures that are currently used to build existing codes. “The codes we use actually require assuming not only that NP is not equal to P, but even stronger assumptions,” he said, “I am trying to close this gap, bringing us closer to having cryptography based entirely on the P vs. NP problem.”

The Berkeley sabbatical will give Vadhan the chance to poke around the subject and see what fresh approaches might be fruitful in the future. Additionally, his colleagues at Berkeley have been working on an intriguing set of problems that don’t fall neatly into the P or NP categories — an area of research that Vadhan is considering exploring.

“It seems counterintuitive,” Vadhan said, “but sometimes it’s necessary to take a step back from what you’ve been doing in order to know what should come next. The next best steps don’t always flow in step-wise order from what you’ve been doing. It always helps to get a bit of perspective every once in a while.”

In any case, he is taking advantage of the California weather to gain some perspective of the outdoor variety, hiking with his wife and children on the weekends and occasionally indulging in a game of tennis.

“It’s one thing that you can’t do in Cambridge in the winter,” he admitted. “I’ve had a wonderful experience at Harvard and MIT, but it’s been nice to have a change of scenery this year.”