Nick Pippenger

Last updated
Nick Pippenger
Alma materB.S., Shimer College
Ph.D., Massachusetts Institute of Technology
Spouse(s) Maria Klawe, 1980
ChildrenTwo children
Scientific career
Fields Computer science
Institutions Harvey Mudd College,
Princeton University,
University of British Columbia

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, British Columbia, 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, former President of Harvey Mudd College. In 1997 he was inducted as a Fellow of the Association for Computing Machinery. [1] In 2013 he became a fellow of the American Mathematical Society. [2]

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. [3] [4]

Pippenger became one of the most recent mathematicians to write a technical article in Latin, when he published a brief derivation of a new formula for e , [5] [6] [ non-primary source needed ] whereby the Wallis product for π is modified by taking roots of its terms:

Related Research Articles

The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membership group, reporting nearly 110,000 student and professional members as of 2022. Its headquarters are in New York City.

In computational complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors. In other words, a problem with input size n is in NC if there exist constants c and k such that it can be solved in time O((log n)c) using O(nk) parallel processors. Stephen Cook coined the name "Nick's class" after Nick Pippenger, who had done extensive research on circuits with polylogarithmic depth and polynomial size.

<span class="mw-page-title-main">Stephen Cook</span> American-Canadian computer scientist, contributor to complexity theory

Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.

<span class="mw-page-title-main">Richard M. Karp</span> American mathematician

Richard Manning Karp is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing Award in 1985, The Benjamin Franklin Medal in Computer and Cognitive Science in 2004, and the Kyoto Prize in 2008.

<span class="mw-page-title-main">Juris Hartmanis</span> American computer scientist (1928–2022)

Juris Hartmanis was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which established the foundations for the field of computational complexity theory".

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a deterministic Turing machine to the Boolean satisfiability problem.

Shmuel Winograd was an Israeli-American computer scientist, noted for his contributions to computational complexity. He has proved several major results regarding the computational aspects of arithmetic; his contributions include the Coppersmith–Winograd algorithm and an algorithm for the fast Fourier transform which transforms it into a problem of computing convolutions which can be solved with another Winograd's algorithm.

<span class="mw-page-title-main">Maria Klawe</span> Canadian-American computer scientist

Maria Margaret Klawe is a computer scientist and served as the fifth president of Harvey Mudd College from 2006 to 2023. Born in Toronto in 1951, she became a naturalized U.S. citizen in 2009. She was previously Dean of the School of Engineering and Applied Science at Princeton University. She is known for her advocacy for women in STEM fields.

<span class="mw-page-title-main">Michael Sipser</span> American theoretical computer scientist (born 1954)

Michael Fredric Sipser is an American theoretical computer scientist who has made early contributions to computational complexity theory. He is a professor of applied mathematics and was the dean of science at the Massachusetts Institute of Technology.

<span class="mw-page-title-main">Circuit complexity</span> Model of computational complexity

In theoretical computer science, circuit complexity is a branch of computational complexity theory in which Boolean functions are classified according to the size or depth of the Boolean circuits that compute them. A related notion is the circuit complexity of a recursive language that is decided by a uniform family of circuits .

<span class="mw-page-title-main">Ronald Fagin</span> American mathematician and computer scientist

Ronald Fagin is an American mathematician and computer scientist, and IBM Fellow at the IBM Almaden Research Center. He is known for his work in database theory, finite model theory, and reasoning about knowledge.

<span class="mw-page-title-main">Georg Gottlob</span> Austrian computer scientist

Georg Gottlob FRS is an Austrian-Italian computer scientist who works in the areas of database theory, logic, and artificial intelligence and is Professor of Informatics at the University of Calabria. He was Professor at the University of Oxford.

<span class="mw-page-title-main">Scott Aaronson</span> American computer scientist (born 1981)

Scott Joel Aaronson is an American theoretical computer scientist and Schlumberger Centennial Chair of Computer Science at the University of Texas at Austin. His primary areas of research are computational complexity theory and quantum computing.

<span class="mw-page-title-main">Kenneth L. Clarkson</span> American computer scientist

Kenneth Lee Clarkson is an American computer scientist known for his research in computational geometry. He is a researcher at the IBM Almaden Research Center, and co-editor-in-chief of Discrete and Computational Geometry and of the Journal of Computational Geometry.

<span class="mw-page-title-main">Sanjeev Arora</span> Theoretical computer scientist

Sanjeev Arora is an Indian American theoretical computer scientist who works in AI and Machine learning.

Eli Upfal is a computer science researcher, currently the Rush C. Hawkins Professor of Computer Science at Brown University. He completed his undergraduate studies in mathematics and statistics at the Hebrew University, Israel in 1978, received an M.Sc. in computer science from the Feinberg Graduate School of the Weizmann Institute of Science, Israel in 1980, and completed his PhD in computer science at the Hebrew University in 1983 under Eli Shamir. He has made contributions in a variety of areas. Most of his work involves randomized and/or online algorithms, stochastic processes, or the probabilistic analysis of deterministic algorithms. Particular applications include routing and communications networks, computational biology, and computational finance.

In mathematics and computer science, a pebble game is a type of mathematical game played by placing "pebbles" or "markers" on a directed acyclic graph according to certain rules:

<span class="mw-page-title-main">Constantinos Daskalakis</span> Greek computer scientist

Constantinos Daskalakis is a Greek theoretical computer scientist. He is a professor at MIT's Electrical Engineering and Computer Science department and a member of the MIT Computer Science and Artificial Intelligence Laboratory. He was awarded the Rolf Nevanlinna Prize and the Grace Murray Hopper Award in 2018.

Phokion G. KolaitisACM is a computer scientist who is currently a Distinguished Research Professor at UC Santa Cruz and a Principal Research Staff Member at the IBM Almaden Research Center. His research interests include principles of database systems, logic in computer science, and computational complexity.

<span class="mw-page-title-main">Alan Selman</span> American complexity theorist (1941–2021)

Alan Louis Selman was a mathematician and theoretical computer scientist known for his research on structural complexity theory, the study of computational complexity in terms of the relation between complexity classes rather than individual algorithmic problems.

References

  1. ↑ "ACM: Fellow Awards / Nicholas Pippenger". ACM Fellows. Association for Computing Machinery. Archived from the original on 2012-03-01. Retrieved 2010-01-24.
  2. ↑ List of Fellows of the American Mathematical Society Archived 2012-12-05 at archive.today , retrieved 2013-05-05.
  3. ↑ Papadimitriou, Christos (1993). "Section 15.3: The class NC". Computational Complexity (1st ed.). Addison Wesley. pp. 375–381. ISBN   978-0-201-53082-7.
  4. ↑ Kozen, Dexter (2006). "Lecture 12: Relation of NC to Time-Space Classes". Theory of Computation. Springer. ISBN   978-1-84628-297-3.
  5. ↑ Pippinger, Nicholas (1976). "Formula nova pro numero cujus logarithmus hyperbolicus unitas est". IBM Research Report RC 6217.
  6. ↑ Pippenger, N. (1976). "Formula Nova Pro Numero Cujus Logarithmus Hyperbolicus Unitas Est - N. Pippenger - Google Books" . Retrieved 2020-06-19.


This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.