Nick Pippenger

From Wikipedia, the free encyclopedia

This article does not cite any references or sources. (October 2007)
Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.

Nicholas John Pippenger is a researcher in computer science. He has produced a number of fundamental results many of which are being widely used in the field of theoretical computer science, database processing and compiler optimization. He has also achieved the rank of IBM Fellow at Almaden IBM Research Center in San Jose, California. He has taught at the University of British Columbia in Vancouver, Canada and at Princeton University in the US. In the Fall of 2006 Pippenger joined the faculty of Harvey Mudd College.

Pippenger holds a B.S. in Natural Sciences from Shimer College and a PhD from the Massachusetts Institute of Technology. He is married to Maria Klawe, President of Harvey Mudd College. In 1997 he was inducted as a Fellow of the Association for Computing Machinery.

The complexity class, Nick's Class (NC), of problems quickly solvable on a parallel computer, was named by Stephen Cook after Nick Pippenger for his research on circuits with polylogarithmic depth and polynomial size.

[edit] References

Heribert Vollmer. Introduction to Circuit Complexity -- A Uniform Approach. ISBN 3-540-64310-9
Christos Papadimitriou (1993). Computational Complexity, 1st edition, Addison Wesley. ISBN 0-201-53082-1. Section 15.3: The class NC, pp.375–381.
Dexter Kozen (2006). Theory of Computation. Springer. ISBN 1-84628-297-7. Lecture 12: Relation of NC to Time-Space Classes