DAVID S. JOHNSON'S RESUME

(Last Revised on 20 March 2006)

Address

Room C239
AT&T Labs - Research
Florham Park, NJ 07932-0971

Phone: (973) 360-8440
FAX: (973) 360-8178
Email Address: dsj@research.att.com
Home Page: http://www.research.att.com/~dsj/

Personal

Date and Place of Birth: December 9, 1945, Washington D.C.
Marital Status: Married, one child

Education

June 1973	Ph.D. (Mathematics)	MIT, Cambridge, MA
	Thesis Advisor:	Prof. Michael J. Fischer
	Thesis Title:	Near-optimal bin packing algorithms

Aug 1968	S.M. (Mathematics)	MIT, Cambridge, MA
	Thesis Advisor:	Prof. Seymour Papert
	Thesis Title:	Look-ahead strategies in one person games with randomly generated game trees

June 1967	B.A. (Mathematics)	Amherst College, Amherst, MA (Summa cum laude)

Experience

Jan 96 - Present	Head, Algorithms and Optimization Dept.
	AT&T Labs, Florham Park, NJ

Mar 88 - Jan 96	Head, Mathematical Foundations of Computing Dept.
	AT&T Bell Laboratories, Murray Hill

Sep 86 - Mar 88	Supervisor in Mathematical Foundations of Computing Dept.
	AT&T Bell Laboratories, Murray Hill, NJ

Aug 80 - May 81	Visiting Professor, Computer Science Department
	University of Wisconsin, Madison, WI

Jan 78 - May 78	Visiting Lecturer, Computer Science Department
	Rutgers University, New Brunswick, NJ

June 73 - Sep 86	Member Technical Staff, Mathematics and Statistics Research Center
	AT&T Bell Laboratories, Murray Hill, NJ

Feb 69 - Aug 71	U.S. Army (1LT)

Awards

Papers in Awerbuch Annual Best Computer Papers (1975, 1976)
Lanchester Prize of the Operations Research Society of America (1979)
Bell Laboratories Distinguished Technical Staff Award (1983)
AT&T Bell Laboratories Research Affirmative Action Award (1992)
ACM Fellow (1994)
1st ACM-SIGACT Distinguished Service Award (1997)
AT&T Outstanding Mentor Award (1998)
AT&T Fellow (2005)
INFORMS Computing Society 2007 ICS Prize for Research Excellence in the
Interface Between Operations Research and Computer Science for the paper
On the Sum-of-Squares Algorithm for Bin Packing

Distinguished Lecturer

Carnegie-Mellon University (1983)
Cornell (1987)
Massachusetts Institute of Technology (1989)
University of Arizona (1992)
University of Washington (1995)
Lawrence Livermore National Labs (2000)
New Jersey Institute of Technology 1st Annual Pioneers of Computing Symposium (2004)
Research Triangle Distinguished Lecture Series (2005)

Plenary Speaker

University of Montreal Optimization Days Conference (1996)
Third Metaheuristics International Conference (1999)
Fifth INFORMS Telecommunications Conference (2000)
Workshop on Experimental Algorithms (2008)
SIAM Conference on Discrete Mathematics (2008)

Professional Activities

Member-at-Large, ACM Council, 1996-2004
Board Member, Computing Research Association, 1997-2000
Chairman, ACM-SIGACT, 1987-91
Secretary-Treasurer ACM-SIGACT, 1983-87
Program Committee Chair, ACM Symposium on Theory of Computing, 1983
Program Committee Chair, ACM-SIAM Symposium on Discrete Algorithms, 1990
Program Committee Member, ACM Symposium on Theory of Computing, 1979
Program Committee Member, ACM-SIAM Symposium on Discrete Algorithms, 1997, 2004
Program Committee Member, Algorithms and Experiments, 1998
Program Committee Member, Workshop on Algorithm Engineering, 1998
Program Committee Member, Workshop on Algorithm Engineering and Experimentation, 1998, 2008
Program Committee Member, Workshop on Stochastic Local Search, 2007
Founder and Co-Conference Chair, ACM-SIAM Symposium on Discrete Algorithms, 1990-Present
Conference Chair, ACM Symposium on Theory of Computing, 1993, 1996, 2007
Chair, Federated Computing Research Conference, 1999
Steering Committee Chair and Chief Scheduler, Federated Computing Research Conference, 2003
ORSA Lanchester Prize Committee Member, 1985
ACM Thesis Award Committee Member, 1985 - 1987 (Chair: 1987)
ACM-SIGACT Awards Committee Chair, 1994 - 2000
ACM-SIGACT Godel Prize Committee Member, 1995 - 1998
ACM Kanellakis Award Committee Member, 1996-2001 (Chair: 1999, 2000)
ACM Awards Committee Member, 1999-2001
Founder and Organizer, DIMACS Implementation Challenges, 1990-Present
Co-Organizer, DIMACS 1996-97 Special Year on Networks
PostDoc Committee, DIMACS, 1989-Present (Chair, 1994-95)
Executive Committee, DIMACS, 1994-Present
Editor:
- Journal of Algorithms, 1979 - 2004
- Mathematics of Operations Research, 1980 - 1997
- Mathematical Programming, 1980 - 1997
- Information and Computation, 1982 - 2000
- Journal of the Association Computing Machinery, 1983 - 1987
- Algorithmica, 1984 - Present
- ACM Transactions on Mathematical Software, 1991 - 2006
- ACM Transactions on Algorithms, 2004 - Present

Courses Taught

Approximation Algorithms (Graduate Course, Rutgers)
Analysis of Algorithms (Graduate Course, UW)
Algorithms and Complexity Seminar (Graduate Course, UW)
Introduction to Data Structures (Undergraduate Course, UW)

Research Interests

Computational complexity and the theory of NP-completeness
Worst-case, probabilistic, and experimental analysis of algorithms
Approximation algorithms
Bin packing
The Traveling Salesman Problem
Network Design
Graph Partitioning and Coloring