In receiving the award, Lipton was cited for “inventing new computer science and mathematical techniques to tackle foundational and practical problems in a wide range of areas in graph algorithms, computation, communication, program testing, and DNA computing.”
The Knuth Prize is jointly presented by ACM’s Special Interest Group on Algorithms and Computation Theory (SIGACT) and the IEEE Computer Society Technical Committee on the Mathematical Foundations of Computing (TCMF). The award will be presented at the Foundations of Computer Science (FOCS) Conference in Philadelphia, PA, from Oct. 18 to 21, where Lipton will give the Knuth Prize Lecture.
Earlier this year, Lipton was elected to the 2014 class of the American Academy of Arts and Sciences. With the Knuth Prize, Lipton joins a short list of extraordinary computer scientists.
“The Knuth Prize means a great deal,” Lipton said. “It is very exciting to be recognized by your peers for work that spans over 40 years. I feel very special and thankful to have been selected.”
Lance Fortnow, chair of the School of Computer Science, offered his praise:
"Dick's work has had a major impact in quite diverse areas across theoretical computer science and has heavily influenced many researchers including myself. I can think of no one more deserving of this award."
In presenting the award, the selection committee cited:
The Knuth Prize is named in honor and recognition of Turing Award winner Donald Knuth, professor emeritus at Stanford University. Knuth is well-known for his ongoing multivolume series, The Art of Computer Programming, which played a critical role in establishing and defining computer science as a rigorous, intellectual discipline.
Lipton earned his undergraduate degree in mathematics from Case Western Reserve University and his Ph.D. from Carnegie Mellon University. He taught at Yale, the University of California in Berkeley and Princeton before joining the Georgia Tech faculty in 2000.
Lipton explores one of the most daunting puzzles in computation theory in his blog Gödel’s Lost Letter and P=NP and recently published his second book based on the blog, People, Problems, and Proofs: Essays from Gödel's Lost Letter, which he co-authored with Kenneth W. Regan of the University of Buffalo.
]]>The selection committee includes: Gregory Blekherman, Math; Santanu Dey (committee chair), ISyE; David Goldberg, ISyE; Milena Mihail, SCS; Le Song, CSE; and Santosh Vempala, CS.
]]>Subhash Khot is awarded the Nevanlinna Prize for his prescient definition of the "Unique Games" problem, and leading the effort to understand its complexity and its pivotal role in the study of efficient approximation of optimization problems; his work has led to breakthroughs in algorithmic design and approximation hardness, and to new exciting interactions between computational complexity, analysis and geometry.
Details may be found at the website of the International Mathematical Union.
]]>These problems have proved nearly intractable, requiring weeks or even months of high performance processing to handle such data sets.
But not anymore.
Researchers at Georgia Tech’s School of Computer Science have discovered an algorithm – deemed “Gaussian Cooling” – to accurately compute the volume of convex bodies in a matter of minutes using off-the-shelf computers.
“With this randomized algorithm, mathematicians and researchers can estimate the volume of high dimensional objects in real time,” said Santosh Vempala, a professor in the School of Computer Science (SCS) who developed the new algorithm with doctoral candidate, Ben Cousins. “It can handle bodies in 100 dimensions and greater, using a new, provably correct technique.”
The problem of estimating the volume of a set is ancient. It has spawned a stream of mathematical and algorithmic ideas throughout history, starting with the Egyptians and Greeks who developed formulas in only two or three dimensions.
However, in spite of rapid advances in computers and algorithms and intensive study over the past 25 years, sampling and volume computation for high-dimensional sets has evaded a practical and complete solution. Research has resulted in a suite of tools to address parts of the challenge, such as analyzing and manipulating high-dimensional objects, choosing representative samples, and learning useful properties.
With this latest advance, total volume computation is practical for the first time.
"Professor Vempala and his student, Ben Cousins, made significant and surprising improvements to take the theoretical algorithm for volume computation to where we can now solve volume problems on today's computers,” said Lance Fortnow, chair of SCS. “Their work brings a major tool to the algorithmic arsenal that should have applications across the sciences."
The algorithm can be used as a tool for high-dimensional data analysis. Such data involving great numbers of parameters abounds in many fields today, including biology, neuroscience, as well as applied areas such as medical research, which may involve numerous vital statistics across many patients, or in computer security, where the algorithm can be applied to a model of information flow to estimate number of instances where data might leak.
Ravi Kannan, a principal researcher at Microsoft Research India and a member of the first team to create algorithms in this field, calls the latest discovery a “tour de force.”
“It is the culmination of a decades-long effort by leading researchers to develop an efficient algorithm for the problem of estimating the volume of convex sets,” Kannan said. “I foresee many important consequences. Congratulations to Cousins and Vempala on their achievement.’’
Georgia Tech’s researchers have made their algorithm publicly available as a MATLAB implementation and report that the method has been downloaded hundreds of times to date. More details of the research and the researchers’ paper are available here.
]]>News & Media Relations Manager
]]>