The Association for Computing Machinery has named Lance Fortnow, Professor in Computer Science at the University of Chicago, as a 2007 ACM Fellow. Fortnow is among 38 association members that the ACM is recognizing as fellows this year for their contributions to computing technology that have brought advances in the way people live and work.
The ACM cited Fortnow for his contributions to complexity theory. In his research in computational complexity, Fortnow tries to understand the theoretical power and limits of efficient computation.
“Much of the field is driven by the well-known ‘P versus NP’ problem, which asks whether for every problem that has efficiently verifiable solutions, can we find those solutions quickly,” Fortnow said. “For example, whether given a list of who is friends with whom, can we find a large clique of people who are friendly with each other?”
Fortnow’s research has shown that allowing randomized verification of proofs is much more powerful than without randomness. The latter approach has led to limitations in the ability of computer scientists to find even approximate solutions to some problems. He has also taken what he terms “a baby step” toward settling the P versus NP question, by showing that some verification problems cannot be solved with a small amount of computer time and memory. Most recently, Fornow has been trying to apply complexity tools to economic issues.
An educational and scientific society, the ACM has more than 82,000 members in industry, academia and government institutions worldwide.