If your doctor diagnoses your malady by ordering an MRI, a tiny smidgen of the credit may be due to Richard Lipton. If you use the “people you may know” function to expand your LinkedIn network, theorems Lipton developed may be lurking somewhere deep, deep in the background.
At 68, Lipton is one of the most influential computer scientists of his generation. Among theoreticians, the Georgia Tech professor is a household name.
“There is nothing that goes on in theoretical computer science that doesn’t rely on something that he’s done,” said Lance Fortnow, chair of the university’s School of Computer Science. “My research wouldn’t have happened if his research hadn’t occurred first. “I think that’s true of probably almost everyone in our field.”
This fall, Lipton, who prefers to be called Dick, won the Knuth Prize, an annual award honoring one of the field’s most impressive thinkers.
While teaching at the University of California at Berkeley in the 1970s Lipton was among the first to show how computer systems could be hacked by exploiting weak links in networks – a phenomenon Target customers, among others, have experienced recently to their dismay.
A couple decades later his work at Princeton on DNA computing led the way toward blueprints for a machine that could utilize biological molecules, rather than silicon, as a medium for computation. A biologically based computer potentially could solve problems beyond the capabilities of even the most advanced current devices.
Tall and pale, avuncular and self-effacing, Lipton speaks in an excited staccato, especially when the subject is the hard problems that captivated him even as a teenager.
He can still recall a particular one that fired his imagination then, such as a problem that states that any two-dimensional map can be colored using just four colors in such a way that no two adjacent regions have the same color.
“I remember sitting there and drawing pictures and thinking about it,” he said, adding that in those days before the Internet, he found the problem in an encyclopedia, perhaps the Britannica.
For him, it was always math. In the beginning, he enjoyed proofs much more than computers.
“I liked the problem solving,” he said. “These were like puzzles. I liked that a lot. I was also good at it.”
He grew up amid late 1950s and early 1960s Long Island sprawl in the community of Massapequa, playing 3-on-3 stick ball and touch football in the street a block away from the bay.
His mother, Dorothy, was a homemaker; His father, Jack, worked in art production for advertising agencies in Manhattan.
For his undergraduate degree in math, he went to Case-Western University in Cleveland. There he learned to code from a friend.
Then he moved on to get his doctorate in computer scientist at Carnegie Mellon. Posts followed at Berkeley, Yale, Princeton and, in 2000, Georgia Tech.
In 1995 he married Judith Norback, whom he had met four years earlier through a New Jersey newspaper ad she placed.
“FUN & POSSIBLE ROMANCE- I am a DWF in my 30’s, thin, fit, smart, successful & good looking. I am not looking for a lifetime commitment at this point, but I love to have fun. I am looking for a S/DWM who is also looking for fun, companionship & possible romance, so I thought I’d try this.”
To a layperson, the way Lipton approaches fundamental problems might sound like the random musings of a curious, if slightly twisted adolescent.
Rich A. DeMillo, a distinguished professor of computing at Tech, remembers a car drive with Lipton in the late 90s. Somewhere between Santa Barbara and Los Angeles, Lipton asked: What happens if you put a smartcard in a microwave? (By smartcard, he meant the chip-based credit cards that are the standard in Europe and are now coming the U.S.)
The question got at an issue of immense importance to millions of credit card holders. “Because, when you put a smartcard in any high stress environment like that, the chip is going to fail, and the way that the chip fails is that it leaks the information,” said DeMillo.
Lipton didn’t just ask the question, he worked out the theoretical parameters for solving it. And that changed the way the payment card companies (including MasterCard and Visa) designed the algorithm securing cardholder information.
“He zeroes in on exactly the right problem, and then he brings in a lot of other people that can surround the problem and can make some practical significance out of it,” DeMillo said.
Recently, Lipton has been blogging about perhaps the hottest question in theoretical computing, expressed as P verses NP. It poses the question of whether shortcuts exist that would make performing enormously complex computations (NP) almost as fast as performing simple ones (P).
As arcane as that may seem, the security of encrypted messages and payment card data rests on the assumption that P ≠ NP, that complex, multi-factor computations take immensely longer to perform. If that assumption could be proven wrong, our digital privacy would be imperilled.
Many smart people are working on the problem, but Lipton’s work draws special attention.
“It’s hard to overemphasize how important that blog is,” DeMillo said, adding that it has received millions of page views. He’s stopped counting.
“This is really abstract math, it draws the best mathematicians in the world, and this thing ranks up with Kim Kardashian on Wordpress. There is something kind of universally appealing about the way he looks at the world.”
Lipton is also known for playing well with others. Most of his important work, including the blog, has been done with a partner.
One of his most famous theorems, Karp-Lipton, which is important to NP programs, is, as the name implies, the work of both Lipton and Richard M. Karp, a computer theorist at Berkeley
In October, during a prelude to his acceptance lecture for the Knuth Prize, Lipton joked that the theorem is so simple that it appeared on a tote bag at a computer science conference at Harvard to which he wasn’t invited.
Lipton took that as a badge of honor. He held up the tote to laughter. Nevertheless, the packed room clearly was awed.
Before Lipton headed to the lectern, someone in the crowd was heard to say, “This is the smartest person here.”