# Nick Pippenger

#12,169

Most Influential Person Now

Computer scientist

## Nick Pippenger's AcademicInfluence.com Rankings

Nick Pippengercomputer-science Degrees

Computer Science

#843

World Rank

#874

Historical Rank

#459

USA Rank

Database

#523

World Rank

#547

Historical Rank

#203

USA Rank

## Download Badge

Computer Science

## Nick Pippenger's Degrees

- PhD Computer Science Stanford University
- Masters Computer Science Stanford University
- Bachelors Computer Science Stanford University

## Similar Degrees You Can Earn

## Why Is Nick Pippenger Influential?

(Suggest an Edit or Addition)According to Wikipedia, 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.

## Nick Pippenger's Published Works

### Published Works

- Extendible hashing—a fast access method for dynamic files (1979) (735)
- Relations Among Complexity Measures (1979) (378)
- A fast parallel algorithm for routing in permutation networks (1981) (279)
- On simultaneous resource bounds (1979) (275)
- The computational complexity of knot and link problems (1997) (231)
- Finding the Median (1976) (207)
- Asymptotic behavior of the chromatic index for hypergraphs (1989) (196)
- On networks of noisy gates (1985) (183)
- Expanding graphs contain all small trees (1987) (172)
- Fault tolerance in networks of bounded degree (1986) (169)
- Characterizations of 1-Way Quantum Finite Automata (1999) (159)
- Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines (1984) (156)
- Knots in random walks (1989) (144)
- On determinism versus non-determinism and related problems (1983) (122)
- On the Evaluation of Powers and Monomials (1980) (121)
- Reliable computation by formulas in the presence of noise (1988) (114)
- Theories of computability (1997) (113)
- Polynomial Hash Functions Are Reliable (Extended Abstract) (1992) (100)
- Galois theory for minors of finite functions (1998) (98)
- Bounds on the performance of protocols for a multiple-access broadcast channel (1981) (96)
- Wide-Sense Nonblocking Networks (1988) (92)
- On the Maximum Tolerable Noise for Reliable Computation by Formulas (1998) (85)
- Bounding Fan-out in Logical Networks (1984) (84)
- Superconcentrators, generalizers and generalized connectors with limited depth (1983) (80)
- Sorting and Selecting in Rounds (1987) (79)
- An optimal brain can be composed of conflicting agents. (2006) (75)
- On a lower bound for the redundancy of reliable networks with noisy gates (1991) (71)
- Shifting Graphs and Their Applications (1976) (71)
- On the evaluation of powers and related problems (1976) (70)
- The inequalities of quantum information theory (2003) (68)
- Reliable Computation in the Presence of Noise (1986) (68)
- Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions (1985) (66)
- The inducibility of graphs (1975) (64)
- Topological characteristics of random triangulated surfaces (2006) (64)
- Sex, mixability, and modularity (2010) (63)
- On Random Knots (1994) (57)
- Invariance of complexity measures for networks with unreliable gates (1989) (53)
- On monotone formulae with restricted depth (1984) (52)
- Rearrangeable Networks with Limited Depth (1982) (50)
- On Rearrangeable and Non-Blocking Switching Networks (1978) (45)
- Parallel Communication with Limited Buffers (Preliminary Version) (1984) (44)
- The Complexity of Computations by Networks (1987) (44)
- Developments in "The synthesis of reliable organ-isms from unreliable components (1990) (41)
- Optimal 2, 3-Trees (1979) (40)
- Self-routing superconcentrators (1993) (40)
- On Another Boolean Matrix (1980) (40)
- On Simultaneous Resource Bounds (Preliminary Version) (1979) (40)
- An Information-Theoretic Method in Combinatorial Theory (1977) (38)
- On Crossbar Switching Networks (1975) (38)
- Advances in Pebbling (Preliminary Version) (1982) (36)
- Optimal carry save networks (1992) (36)
- A Time-Space Trade-Off (1978) (34)
- Superconcentrators of Depth 2 (1982) (33)
- The Complexity Theory of Switching Networks. (1973) (32)
- Pure versus impure Lisp (1997) (31)
- Faster circuits and shorter formulae for multiple addition, multiplication and symmetric Boolean functions (1990) (28)
- Parallel selection (1990) (26)
- The minimum number of edges in graphs with prescribed paths (1978) (26)
- Non-blocking networks (1986) (25)
- The Hypercube of Resistors, Asymptotic Expansions, and Preferential Arrangements (2009) (25)
- Some Graph-Colouring Theorems with Applications to Generalized Connection Networks (1985) (23)
- Selection Networks (1990) (22)
- Entropy and enumeration of boolean functions (1999) (21)
- Communication Networks (1991) (20)
- Information theory and the complexity of boolean functions (1976) (20)
- Analysis of Carry Propagation in Addition: An Elementary Approach (2001) (18)
- Fault-tolerant circuit-switching networks (1992) (18)
- Barred Preferential Arrangements (2012) (16)
- Average-Case Lower Bounds for Noisy Boolean Decision Trees (1999) (15)
- Fault tolerance in cellular automata at high fault rates (2007) (15)
- The shortest disjunctive normal form of a random Boolean function (2003) (15)
- Generalized Connectors (1978) (14)
- ASYMPTOTIC ANALYSIS OF OPTIMAL NESTED GROUP-TESTING PROCEDURES (2016) (14)
- An Elementary Approach to Some Analytic Asymptotics (1992) (14)
- Systematic mistakes are likely in bounded optimal decision-making systems. (2008) (14)
- The Boolean functions computed by random Boolean formulas or how to grow the right function (2003) (14)
- The Asymptotic Optimality of Spider-Web Networks (1992) (14)
- Pebbling with an Auxiliary Pushdown (1981) (13)
- Efficient Algorithms for Zeckendorf Arithmetic (2012) (13)
- Symmetry in Self-Correcting Cellular Automata (1994) (13)
- An Infinite Product for e (1980) (13)
- Alphabetic Minimax Trees of Degree at Most t (1986) (13)
- Comparative schematology and pebbling with auxiliary pushdowns (Preliminary Version) (1980) (12)
- The average amount of information lost in multiplication (2004) (12)
- On the Complexity of Strictly Nonblocking Concentration Networks (1974) (12)
- A New Lower Bound for the Number of Switches in Rearrangeable Networks (1980) (11)
- Analysis of Error Correction by Majority Voting (1989) (10)
- Computational Complexity of Algebraic Functions (1981) (10)
- The complexity of monotone boolean functions (1977) (10)
- An Explicit Construction of Short Monotone Formulae for the Monotone Symmetric Functions (1978) (10)
- Lower bounds for noisy Boolean decision trees (1996) (9)
- Parallel Computation for Well-Endowed Rings (1983) (9)
- Large-Deviation Bounds for Sampling without Replacement (2014) (9)
- Fault Tolerance in Networks of Bounded Degree (Preliminary Version) (1986) (9)
- Probabilistic simulations (Preliminary Version) (1982) (8)
- On Monotone Formulae with Restricted Depth (Preliminary Version) (1984) (8)
- Pure versus impure Lisp (1996) (8)
- Juggling Networks (1994) (8)
- Topological characteristics of random surfaces generated by cubic interactions (2003) (8)
- The Blocking Probability of Spider-Web Networks (1991) (7)
- Large deviations and moments for the Euler characteristic of a random surface (2009) (7)
- On-the-Fly Algorithms and Sequential Machines (2011) (6)
- On the Enumeration of Interval Graphs (2016) (6)
- A Census of Vertices by Generations in Regular Tessellations of the Plane (2010) (6)
- Comparative Schematology and Pebbling with Auxiliary Pushdowns (1980) (6)
- Attribute estimation and testing quasi-symmetry (2007) (5)
- Routing algorithms for switching networks with probabilistic traffic (1996) (5)
- The Realization of Monotone Boolean Functions (1976) (5)
- Computational complexity in algebraic function fields (1979) (5)
- The realization of monotone Boolean functions (Preliminary Version) (1976) (5)
- Information theory and the complexity of switching networks (1975) (5)
- CHAPTER 15 – Communication Networks (1990) (5)
- The Expected Capacity of Concentrators (1991) (4)
- Fault tolerance in cellular automata at low fault rates (2012) (4)
- Boundary Cycles in Random Triangulated Surfaces (2008) (4)
- Random interval graphs (1998) (4)
- Parallel algorithms for routing in non-blocking networks (1991) (4)
- Algebraic Complexity Theory (1981) (4)
- The Linking Probability of Deep Spider-Web Networks (2005) (4)
- A Combinatorial Interpretation of the Joint Cumulant (2012) (4)
- SRT division algorithms as dynamical systems (2003) (4)
- Random Cyclations (2004) (4)
- Fields Medals and Nevanlinna Prize Presented at ICM-94 in Zurich (1974) (3)
- Enumeration of Equicolorable Trees (2001) (3)
- Detecting Covert Members of Terrorist Networks (2012) (3)
- Correction to "Computational Complexity of Algebraic Functions" (1988) (3)
- Stochastic service systems, random interval graphs and search algorithms (2011) (3)
- Upper and lower bounds for the average-case complexity of path-search (1999) (3)
- Asymptotic Behavior of the Moments of the Maximum Queue Length During a Busy Period (2011) (2)
- A Bound on the Variance of the Waiting Time in a Queueing System (2011) (2)
- Random Sequential Adsorption on Graphs (1989) (2)
- Analysis of a Recurrence Arising from a Construction for Nonblocking Networks (1995) (2)
- Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs (2002) (1)
- M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns (2012) (1)
- Information Theory and the Complexity of Switching Networks (Preliminary Version) (1975) (1)
- Asymptotic Analysis of Run-Length Encoding (2015) (1)
- Counting the Angels and Devils in Escher's Circle Limit IV (2013) (1)
- Carry propagation in multiplication by constants (2008) (1)
- Self-intersections of Two-Dimensional Equilateral Random Walks and Polygons (2015) (1)
- Martingale Couplings and Bounds on Tails of Probability Distributions (2011) (1)
- Elementary Proofs of the Main Limit Theorems of Probability (2012) (1)
- Computational Aspects of M.C. Escher’s Ribbon Patterns (2014) (1)
- Two Extensions of Results of Archimedes (2011) (1)
- Computational aspects of escher tilings (2002) (1)
- Communication: On the Application of Coding Theory to Hashing (1979) (1)
- COMPUTATIONAL COMPLEXITY IN ALGEBRAIC FUNCTION FIELDS (Preliminary Version) (1979) (1)
- Extracting Numerical Information about Corn Composition from Texts (2015) (1)
- A Formula for the Determinant (2022) (1)
- The M/M/Infinity Service System with Ranked Servers in Heavy Traffic (2011) (1)
- Research Proposal: Proving Reed's Conjecture for Certain Classes of Graphs (2013) (0)
- Extended Canonical Recoding (2002) (0)
- Local versus global search in channel graphs (2010) (0)
- Finding an Optimal Routing Policy on Simple Client-Server Models (1999) (0)
- Rigid Divisibility Sequences Generated by Polynomial Iteration (2008) (0)
- Enumeration of Equicolourable Trees (2000) (0)
- Computational Aspects of M.C. Escher’s Ribbon Patterns (2013) (0)
- Gap Theorems for the Delay of Circuits Simulating Finite Automata (2013) (0)
- Non-Blocking Networks (Preliminary Version) (1986) (0)
- Extortion and Evolution in the Iterated Prisoner ’ s Dilemma (2013) (0)
- Entropy and expected acceptance counts for finite automata (2004) (0)
- Randomized Algorithms for Preconditioner Selection with Applications to Kernel Regression (2019) (0)
- Parallel algorithms for routing in nonblocking networks (2005) (0)
- Fibonomial Tilings and Other Up-Down Tilings (2019) (0)
- HOW MANY PA RS OF PRODUCTS OF CONSECUT VE NTEGERS HAVE THE SAME (2004) (0)
- 1-1-1988 Wide-Sense Nonblocking Networks (2016) (0)
- A Combinatorial Exploration of Elliptic Curves Matt Lam (2017) (0)
- Research Proposal: Asymptotic Bounds of the Hypergeometric Distribution (2010) (0)
- Geometric Unified Method in 3D Object Classification (2020) (0)
- 1-1-1979 Optimal 2 , 3-Trees (2016) (0)
- Invited talk: the memory-refresh problem (1988) (0)
- Research Proposal: Continued Fractions (2010) (0)
- Optimal Carry Save (2007) (0)
- 1-1-1982 Probabilistic Simulations (2016) (0)
- Average-case bounds for the complexity of path-search (1997) (0)
- SRT Division Algortihms as Dynamical Systems (2003) (0)
- Structured Matrices and the Algebra of Displacement Operators (2013) (0)
- Sequential Probing With a Random Start (2019) (0)
- Quantum signal propagation in depolarizing channels (2002) (0)
- Hypergraph Capacity with Applications to Matrix Multiplication (2013) (0)
- Random Sequential Absorption on Graphs (1989) (0)
- Expected Acceptance Counts for Finite Automata with Almost Uniform Input (2002) (0)
- Analysis of an M/M/1 Queue Using Fixed Order of Search for Arrivals and Service (2011) (0)
- Entropy and Expected Acceptance Counts for (2004) (0)
- Cyclation.tex Random Cyclations (2004) (0)
- 1-1-1993 An Elementary Approach to Some Analytic Asymptotics (2016) (0)

This paper list is powered by the following services:

## Other Resources About Nick Pippenger

## What Schools Are Affiliated With Nick Pippenger?

Nick Pippenger is affiliated with the following schools: