AT&t labs researcher to receive acm award for contributions to design of algorithms and development of np-completeness theory david S. Johnson Named 2010 Knuth Prize Winner for Innovations That Impacted the Foundations of Computer Science new

Download 12.82 Kb.
Size12.82 Kb.


Association for Computing Machinery

Advancing Computing as a Science & Profession

Lance Fortnow Virginia Gold

847-579-9310 ACM

ACM SIGACT Chair 212-626-0505


David S. Johnson Named 2010 Knuth Prize Winner for Innovations

That Impacted the Foundations of Computer Science

NEW YORK, March 2, 2010 – The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) will present its 2010 Knuth Prize to David S. Johnson of AT&T Labs for his contributions to theoretical and experimental analysis of algorithms. Johnson’s innovations helped lay the foundation for algorithms used to address optimization problems, which involve the process of finding the best solution from all feasible solutions. In addition, Johnson made many contributions to the early development of NP-completeness theory, which helps identify those problems that are hard to solve efficiently. The Knuth Prize, named in honor of Donald Knuth of Stanford University who has been called the "father" of the analysis of algorithms, will be presented at the ACM Symposium on Theory of Computing (STOC) June 6-8, 2010, in Cambridge, MA, where Johnson will present the Knuth Prize Lecture.
Johnson’s research in approximation techniques to solve computational problems set up the basic theoretical framework and approach for searching for an “almost” optimal solution. His work over the years has addressed the approximation of many problems including bin packing, which is an NP-hard problem that applies to filling up containers, loading trucks with weight capacity, and creating file backup in removable media. It also addresses TSP (the Traveling Salesman Problem), which can be useful in planning, logistics, and the manufacture of microchips, as well as DNA sequencing.
In addition to his theoretical analysis, Johnson has authored a set of highly influential papers on the experimental analysis of approximation algorithms. This research established equally rigorous standards for experimental algorithms, which focus on implementations as the standard of value and provide the key to the transfer of research results from paper to production code.
Johnson is an acknowledged expert on NP-completeness, a reference to the hardest search problems. His 1979 book, Computers and Intractability: A Guide to the Theory of NP-Completeness, which he coauthored with Michael Garey, remains the standard reference on the topic. Johnson has also written continuously on NP-completeness in his columns for the Journal of Algorithms and ACM Transactions on Algorithms.
An active leader in the theoretical computer science community, Johnson founded the ACM-SIAM (Society for Industrial and Applied Mathematics) Symposium on Discrete Algorithms (SODA) and the ongoing series of DIMACS (Center for Discrete Mathematics and Theoretical Computer Science) Implementation Challenges. He served on the ACM Council as Member-at-Large from 1996-2004, and chaired ACM SIGACT from 1987-1991. He was editor of the Journal of the Association for Computing Machinery (JACM) from 1983-1987, and ACM Transactions on Mathematical Software (TOMS) from 1991-2006. He has also served as associate editor of ACM Transactions on Algorithms(TALG) since its founding in 2004.
Johnson, a Fellow of ACM (, graduated summa cum laude from Amherst College and earned S.M. and Ph.D degrees from Massachusetts Institute of Technology (MIT) in mathematics.

The Knuth Prize is given every 18 months by ACM SIGACT and the IEEE Technical Committee on the Mathematical Foundations of Computer Science and includes a $5,000 award.

About ACM

ACM, the Association for Computing Machinery is the world’s largest educational and scientific computing society, uniting computing educators, researchers and professionals to inspire dialogue, share resources and address the field’s challenges. ACM strengthens the computing profession’s collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.  


The ACM Special Interest Group on Algorithms and Computation Theory fosters and promotes the discovery and dissemination of high quality research in the domain of theoretical computer science. The field includes algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor. 

# # #

Directory: press-room -> news-releases -> 2010 -> news-releases-word
news-releases-word -> Chinese and russian universities claim eight of top ten spots in acm international programming competition for top tech talent
news-releases-word -> Acm group honors software developer of versatile compilers used in advanced mobile devices
news-releases-word -> Acm group honors software developer of versatile compilers used in advanced mobile devices
news-releases-word -> Acm acm sigcomm
news-releases-word -> Acm council on women honors leader in improving performance of computer-aided design
news-releases-word -> Acm recognizes leaders who have raised awareness of computer science’s impact on innovation and competitiveness new york, April 14, 2010
news-releases-word -> For immediate release acm ieee computer Society
news-releases-word -> Acm group honors computer privacy and security experts for innovative research and practical realization camenisch and Thuraisingham Cited for Advances in Privacy-Enhancing Cryptography and Leadership in Counterterrorism Data and Applications Security
news-releases-word -> Acm awards recognize computer scientists for innovations that have real world impact
news-releases-word -> Uncovering One of Education’s Most Startling Paradoxes: k-12 Computer Science Education Declines While Society’s Need for Computing Rises

Download 12.82 Kb.

Share with your friends:

The database is protected by copyright © 2020
send message

    Main page