Nicholas Pippenger

According to our database1, Nicholas Pippenger authored at least 113 papers between 1975 and 2014.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Awards

ACM Fellow

ACM Fellow 1997, "For numerous contributions to the theory of computation, to communication theory and information theory, and to related areas of mathematics.".

IEEE Fellow

IEEE Fellow 1995, "For contributions to the design of switching networks, complexity theory, parallel computing, and reliable computation.".

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2014
Large-Deviation Bounds for Sampling without Replacement.
The American Mathematical Monthly, 2014

Stochastic service systems, random interval graphs and search algorithms.
Random Struct. Algorithms, 2014

Computational Aspects of M.C. Escher's Ribbon Patterns.
Theory Comput. Syst., 2014

2013
Local versus global search in channel graphs.
Networks, 2013

Fault tolerance in cellular automata at low fault rates.
J. Comput. Syst. Sci., 2013

Random Cyclations.
Electr. J. Comb., 2013

Barred Preferential Arrangements.
Electr. J. Comb., 2013

2012
M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns.
Proceedings of the Fun with Algorithms - 6th International Conference, 2012

2011
On-the-Fly Algorithms and Sequential Machines.
IEEE Trans. Computers, 2011

Two Extensions of Results of Archimedes.
The American Mathematical Monthly, 2011

Carry propagation in multiplication by constants.
ACM Trans. Algorithms, 2011

A Census of Vertices by Generations in Regular Tessellations of the Plane.
Electr. J. Comb., 2011

2010
Large deviations and moments for the Euler characteristic of a random surface.
Random Struct. Algorithms, 2010

2009
Attribute estimation and testing quasi-symmetry.
Inf. Process. Lett., 2009

2008
Fault tolerance in cellular automata at high fault rates.
J. Comput. Syst. Sci., 2008

2006
The Linking Probability of Deep Spider-Web Networks.
SIAM J. Discrete Math., 2006

Topological characteristics of random triangulated surfaces.
Random Struct. Algorithms, 2006

2005
The average amount of information lost in multiplication.
IEEE Trans. Information Theory, 2005

2004
Entropy and expected acceptance counts for finite automata.
IEEE Trans. Information Theory, 2004

2003
The inequalities of quantum information theory.
IEEE Trans. Information Theory, 2003

The shortest disjunctive normal form of a random Boolean function.
Random Struct. Algorithms, 2003

SRT Division Algorithms as Dynamical Systems.
Proceedings of the 16th IEEE Symposium on Computer Arithmetic (Arith-16 2003), 2003

2002
Quantum signal propagation in depolarizing channels.
IEEE Trans. Information Theory, 2002

Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs.
SIAM J. Discrete Math., 2002

Characterizations of 1-Way Quantum Finite Automata.
SIAM J. Comput., 2002

Analysis of Carry Propagation in Addition: An Elementary Approach.
J. Algorithms, 2002

Galois theory for minors of finite functions.
Discrete Mathematics, 2002

Expected Acceptance Counts for Finite Automata with Almost Uniform Input.
Proceedings of the Algorithms and Computation, 13th International Symposium, 2002

2001
Enumeration of Equicolorable Trees.
SIAM J. Discrete Math., 2001

1999
Entropy and enumeration of boolean functions.
IEEE Trans. Information Theory, 1999

Upper and lower bounds for the average-case complexity of path-search.
Networks, 1999

1998
On the Maximum Tolerable Noise for Reliable Computation by Formulas.
IEEE Trans. Information Theory, 1998

Average-Case Lower Bounds for Noisy Boolean Decision Trees.
SIAM J. Comput., 1998

Random interval graphs.
Random Struct. Algorithms, 1998

1997
Regular Languages and Stone Duality.
Theory Comput. Syst., 1997

The Computational Complexity of Knot and Link Problems.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Average-case bounds for the complexity of path-search.
Proceedings of the Advances in Switching Networks, 1997

Theories of computability.
Cambridge University Press, ISBN: 978-0-521-55380-3, 1997

1996
Routing algorithms for switching networks with probabilistic traffic.
Networks, 1996

Lower Bounds for Noisy Boolean Decision Trees.
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

Pure versus Impure LISP.
Proceedings of the Conference Record of POPL'96: The 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, 1996

1995
Analysis of a Recurrence Arising from a Construction for Nonblocking Networks.
SIAM J. Discrete Math., 1995

1994
Parallel Algorithms for Routing in Nonblocking Networks.
Mathematical Systems Theory, 1994

Symmetry in Self-Correcting Cellular Automata.
J. Comput. Syst. Sci., 1994

Juggling Networks.
Proceedings of the Parallel and Distributed Computing, 1994

1993
Self-routing superconcentrators.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992
The Asymptotic Optimality of Spider-Web Networks.
Discrete Applied Mathematics, 1992

An Elementary Approach to Some Analytic Asymptotics.
Proceedings of the Algorithm Theory, 1992

Fault-Tolerant Circuit-Switching Networks.
Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

Polynomial Hash Functions Are Reliable (Extended Abstract).
Proceedings of the Automata, Languages and Programming, 19th International Colloquium, 1992

1991
On a lower bound for the redundancy of reliable networks with noisy gates.
IEEE Trans. Information Theory, 1991

The Expected Capacity of Concentrators.
SIAM J. Discrete Math., 1991

The Blocking Probability of Spider-Web Networks.
Random Struct. Algorithms, 1991

Parallel Algorithms for Routing in Non-Blocking Networks.
Proceedings of the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, 1991

1990
Parallel selection.
Discrete Applied Mathematics, 1990

Selection Networks.
Proceedings of the Algorithms, 1990

Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

Communication Networks.
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A), 1990

1989
Random Sequential Adsorption on Graphs.
SIAM J. Discrete Math., 1989

Asymptotic behavior of the chromatic index for hypergraphs.
J. Comb. Theory, Ser. A, 1989

Invariance of complexity measures for networks with unreliable gates.
J. ACM, 1989

Knots in random walks.
Discrete Applied Mathematics, 1989

Analysis of Error Correction by Majority Voting.
Advances in Computing Research, 1989

1988
Reliable computation by formulas in the presence of noise.
IEEE Trans. Information Theory, 1988

Wide-Sense Nonblocking Networks.
SIAM J. Discrete Math., 1988

Fault Tolerance in Networks of Bounded Degree.
SIAM J. Comput., 1988

Correction to "Computational Complexity of Algebraic Functions".
J. Comput. Syst. Sci., 1988

1987
Sorting and Selecting in Rounds.
SIAM J. Comput., 1987

The Complexity of Computations by Networks.
IBM Journal of Research and Development, 1987

Expanding graphs contain all small trees.
Combinatorica, 1987

1986
Alphabetic Minimax Trees of Degree at Most t.
SIAM J. Comput., 1986

Non-Blocking Networks (Preliminary Version)
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

Fault Tolerance in Networks of Bounded Degree (Preliminary Version)
Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986

1985
Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions.
Theor. Comput. Sci., 1985

On Networks of Noisy Gates
Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984
Bounding Fan-out in Logical Networks.
J. ACM, 1984

On Monotone Formulae with Restricted Depth (Preliminary Version)
Proceedings of the 16th Annual ACM Symposium on Theory of Computing, April 30, 1984

Parallel Communication with Limited Buffers (Preliminary Version)
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983
Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines
Information and Control, 1983

Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version)
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 1983

On Determinism versus Non-Determinism and Related Problems (Preliminary Version)
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982
Superconcentrators of Depth 2.
J. Comput. Syst. Sci., 1982

Probabilistic Simulations (Preliminary Version)
Proceedings of the 14th Annual ACM Symposium on Theory of Computing, 1982

Advances in Pebbling (Preliminary Version).
Proceedings of the Automata, 1982

1981
Bounds on the performance of protocols for a multiple-access broadcast channel .
IEEE Trans. Information Theory, 1981

A Fast Parallel Algorithm for Routing in Permutation Networks.
IEEE Trans. Computers, 1981

Pebbling with an Auxiliary Pushdown.
J. Comput. Syst. Sci., 1981

Computational Complexity of Algebraic Functions.
J. Comput. Syst. Sci., 1981

Algebraic Complexity Theory.
IBM Journal of Research and Development, 1981

1980
On Another Boolean Matrix.
Theor. Comput. Sci., 1980

A New Lower Bound for the Number of Switches in Rearrangeable Networks.
SIAM J. Matrix Analysis Applications, 1980

On the Evaluation of Powers and Monomials.
SIAM J. Comput., 1980

Comparative Schematology and Pebbling with Auxiliary Pushdowns (Preliminary Version)
Proceedings of the 12th Annual ACM Symposium on Theory of Computing, 1980

1979
Extendible Hashing - A Fast Access Method for Dynamic Files.
ACM Trans. Database Syst., 1979

Optimal 2, 3-Trees.
SIAM J. Comput., 1979

The Minimum Number of Edges in Graphs with Prescribed Paths.
Mathematical Systems Theory, 1979

Relations Among Complexity Measures.
J. ACM, 1979

Communication: On the Application of Coding Theory to Hashing.
IBM Journal of Research and Development, 1979

On Simultaneous Resource Bounds (Preliminary Version)
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

Computational Complexity in Algebraic Function Fields (Preliminary Version)
Proceedings of the 20th Annual Symposium on Foundations of Computer Science, 1979

1978
An Explicit Construction of Short Monotone Formulae for the Monotone Symmetric Functions.
Theor. Comput. Sci., 1978

Generalized Connectors.
SIAM J. Comput., 1978

The Complexity of Monotone Boolean Functions.
Mathematical Systems Theory, 1978

On Rearrangeable and Non-Blocking Switching Networks.
J. Comput. Syst. Sci., 1978

A Time-Space Trade-Off.
J. ACM, 1978

1977
Superconcentrators.
SIAM J. Comput., 1977

Information Theory and the Complexity of Boolean Functions.
Mathematical Systems Theory, 1977

An Information-Theoretic Method in Combinatorial Theory.
J. Comb. Theory, Ser. A, 1977

1976
Finding the Median.
J. Comput. Syst. Sci., 1976

Shifting Graphs and Their Applications.
J. ACM, 1976

The Realization of Monotone Boolean Functions (Preliminary Version)
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

On the Evaluation of Powers and Related Problems (Preliminary Version)
Proceedings of the 17th Annual Symposium on Foundations of Computer Science, 1976

1975
Information Theory and the Complexity of Switching Networks (Preliminary Version)
Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975


  Loading...