Nicholas Pippenger

134 papers A* 21B 3C 1Misc 1Journal 101Unranked 4
YearRankTypeTitle / Venue / Authors
2023 — ch.
Computation with Limited Space.
Logic, Automata, and Computational Complexity
Nicholas Pippenger
2022 J jnl
A Formula for the Determinant.
CoRR
Nicholas Pippenger
2015 J jnl
Asymptotic Analysis of Run-Length Encoding.
CoRR
Nabil Zaman, Nicholas Pippenger
2014 J jnl
Computational Aspects of M.C. Escher's Ribbon Patterns.
Theory Comput. Syst.
Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger
2014 J jnl
Large-Deviation Bounds for Sampling without Replacement.
Am. Math. Mon.
Kyle Luh, Nicholas Pippenger
2014 J jnl
Stochastic service systems, random interval graphs and search algorithms.
Random Struct. Algorithms
Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger
2013 J jnl
Barred Preferential Arrangements.
Electron. J. Comb.
Connor Ahlbach, Jeremy Usatine, Nicholas Pippenger
2013 J jnl
Fault tolerance in cellular automata at low fault rates.
J. Comput. Syst. Sci.
Mark McCann, Nicholas Pippenger
2013 J jnl
Gap Theorems for the Delay of Circuits Simulating Finite Automata.
CoRR
Connor Ahlbach, Jeremy Usatine, Nicholas Pippenger
2013 J jnl
Local versus global search in channel graphs.
Networks
A. H. Hunter, Nicholas Pippenger
2013 J jnl
Random Cyclations.
Electron. J. Comb.
Nicholas Pippenger
2012 J jnl
Efficient Algorithms for Zeckendorf Arithmetic
CoRR
Connor Ahlbach, Jeremy Usatine, Nicholas Pippenger
2012 J jnl
Fault Tolerance in Cellular Automata at Low Fault Rates
CoRR
Mark McCann, Nicholas Pippenger
2012 Misc conf
M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns.
FUN
Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger
2011 J jnl
A Census of Vertices by Generations in Regular Tessellations of the Plane.
Electron. J. Comb.
Alice Paul, Nicholas Pippenger
2011 J jnl
Analysis of an M/M/1 Queue Using Fixed Order of Search for Arrivals and Service
CoRR
Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger
2011 J jnl
Carry propagation in multiplication by constants.
ACM Trans. Algorithms
Alexander Izsak, Nicholas Pippenger
2011 J jnl
On-the-Fly Algorithms and Sequential Machines.
IEEE Trans. Computers
Nicholas Pippenger
2011 J jnl
Stochastic Service Systems, Random Interval Graphs and Search Algorithms
CoRR
Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger
2011 J jnl
The M/M/Infinity Service System with Ranked Servers in Heavy Traffic
CoRR
Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger
2011 J jnl
Two Extensions of Results of Archimedes.
Am. Math. Mon.
Nicholas Pippenger
2010 J jnl
Large deviations and moments for the Euler characteristic of a random surface.
Random Struct. Algorithms
Kevin Fleming, Nicholas Pippenger
2010 J jnl
Local versus Global Search in Channel Graphs
CoRR
A. H. Hunter, Nicholas Pippenger
2009 J jnl
Attribute estimation and testing quasi-symmetry.
Inf. Process. Lett.
Krzysztof Majewski, Nicholas Pippenger
2008 J jnl
Fault tolerance in cellular automata at high fault rates.
J. Comput. Syst. Sci.
Mark McCann, Nicholas Pippenger
2007 J jnl
A method for entity identification in open source documents with partially redacted attributes.
J. Comput. Sci. Coll.
Ningning Wu, John R. Talburt, Christopher Heien, Nicholas Pippenger, Chia-Chu Chiang, Elizabeth M. Pierce, Ebony Gulley, JaMia Moore
2007 J jnl
Attribute Estimation and Testing Quasi-Symmetry
CoRR
Krzysztof Majewski, Nicholas Pippenger
2006 J jnl
The Linking Probability of Deep Spider-Web Networks.
SIAM J. Discret. Math.
Nicholas Pippenger
2006 J jnl
Topological characteristics of random triangulated surfaces.
Random Struct. Algorithms
Nicholas Pippenger, Kristin Schleich
2005 J jnl
SRT Division Algorithms as Dynamical Systems.
SIAM J. Comput.
Mark McCann, Nicholas Pippenger
2005 J jnl
The average amount of information lost in multiplication.
IEEE Trans. Inf. Theory
Nicholas Pippenger
2004 J jnl
Entropy and expected acceptance counts for finite automata.
IEEE Trans. Inf. Theory
Nicholas Pippenger
2003 C conf
SRT Division Algorithms as Dynamical Systems.
IEEE Symposium on Computer Arithmetic
Mark McCann, Nicholas Pippenger
2003 J jnl
The Boolean Functions Computed by Random Boolean Formulas OR How to Grow the Right Function
CoRR
Alex Brodsky, Nicholas Pippenger
2003 J jnl
The inequalities of quantum information theory.
IEEE Trans. Inf. Theory
Nicholas Pippenger
2003 J jnl
The shortest disjunctive normal form of a random Boolean function.
Random Struct. Algorithms
Nicholas Pippenger
2002 J jnl
Analysis of Carry Propagation in Addition: An Elementary Approach.
J. Algorithms
Nicholas Pippenger
2002 J jnl
Characterizations of 1-Way Quantum Finite Automata.
SIAM J. Comput.
Alex Brodsky, Nicholas Pippenger
2002 J jnl
Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs.
SIAM J. Discret. Math.
Nicholas Pippenger
2002 B conf
Expected Acceptance Counts for Finite Automata with Almost Uniform Input.
ISAAC
Nicholas Pippenger
2002 J jnl
Galois theory for minors of finite functions.
Discret. Math.
Nicholas Pippenger
2002 J jnl
Quantum signal propagation in depolarizing channels.
IEEE Trans. Inf. Theory
Nicholas Pippenger
2001 J jnl
Enumeration of Equicolorable Trees.
SIAM J. Discret. Math.
Nicholas Pippenger
1999 J jnl
Entropy and enumeration of boolean functions.
IEEE Trans. Inf. Theory
Nicholas Pippenger
1999 J jnl
The Computational Complexity of Knot and Link Problems.
J. ACM
Joel Hass, J. C. Lagarias, Nicholas Pippenger
1999 J jnl
Upper and lower bounds for the average-case complexity of path-search.
Networks
Nicholas Pippenger
1998 J jnl
Average-Case Lower Bounds for Noisy Boolean Decision Trees.
SIAM J. Comput.
William S. Evans, Nicholas Pippenger
1998 J jnl
On the Maximum Tolerable Noise for Reliable Computation by Formulas.
IEEE Trans. Inf. Theory
William S. Evans, Nicholas Pippenger
1998 J jnl
Random interval graphs.
Random Struct. Algorithms
Nicholas Pippenger
1997 — conf
Average-case bounds for the complexity of path-search.
Advances in Switching Networks
Nicholas Pippenger
1997 J jnl
Pure Versus Impure Lisp.
ACM Trans. Program. Lang. Syst.
Nicholas Pippenger
1997 J jnl
Regular Languages and Stone Duality.
Theory Comput. Syst.
Nicholas Pippenger
1997 A* conf
The Computational Complexity of Knot and Link Problems.
FOCS
Joel Hass, J. C. Lagarias, Nicholas Pippenger
1997 — book
Theories of computability.
Nicholas Pippenger
1996 A* conf
Lower Bounds for Noisy Boolean Decision Trees.
STOC
William S. Evans, Nicholas Pippenger
1996 A* conf
Pure versus Impure LISP.
POPL
Nicholas Pippenger
1996 J jnl
Routing algorithms for switching networks with probabilistic traffic.
Networks
Geng Lin, Nicholas Pippenger
1996 J jnl
Self-Routing Superconcentrators.
J. Comput. Syst. Sci.
Nicholas Pippenger
1995 J jnl
Analysis of a Recurrence Arising from a Construction for Nonblocking Networks.
SIAM J. Discret. Math.
Nicholas Pippenger
1994 J jnl
Fault-Tolerant Circuit-Switching Networks.
SIAM J. Discret. Math.
Nicholas Pippenger, Geng Lin
1994 — conf
Juggling Networks.
Canada-France Conference on Parallel and Distributed Computing
Nicholas Pippenger
1994 J jnl
Parallel Algorithms for Routing in Nonblocking Networks.
Math. Syst. Theory
Geng Lin, Nicholas Pippenger
1994 J jnl
Symmetry in Self-Correcting Cellular Automata.
J. Comput. Syst. Sci.
Nicholas Pippenger
1993 A* conf
Self-routing superconcentrators.
STOC
Nicholas Pippenger
1992 — conf
An Elementary Approach to Some Analytic Asymptotics.
SWAT
Nicholas Pippenger
1992 B conf
Fault-Tolerant Circuit-Switching Networks.
SPAA
Nicholas Pippenger, Geng Lin
1992 A* conf
Polynomial Hash Functions Are Reliable (Extended Abstract).
ICALP
Martin Dietzfelbinger, Joseph Gil, Yossi Matias, Nicholas Pippenger
1992 J jnl
The Asymptotic Optimality of Spider-Web Networks.
Discret. Appl. Math.
Nicholas Pippenger
1991 J jnl
On a lower bound for the redundancy of reliable networks with noisy gates.
IEEE Trans. Inf. Theory
Nicholas Pippenger, George D. Stamoulis, John N. Tsitsiklis
1991 B conf
Parallel Algorithms for Routing in Non-Blocking Networks.
SPAA
Geng Lin, Nicholas Pippenger
1991 J jnl
Selection Networks.
SIAM J. Comput.
Nicholas Pippenger
1991 J jnl
The Blocking Probability of Spider-Web Networks.
Random Struct. Algorithms
Nicholas Pippenger
1991 J jnl
The Expected Capacity of Concentrators.
SIAM J. Discret. Math.
Nicholas Pippenger
1990 — ch.
Communication Networks.
Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A)
Nicholas Pippenger
1990 A* conf
Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions
FOCS
Mike Paterson, Nicholas Pippenger, Uri Zwick
1990 J jnl
Parallel selection.
Discret. Appl. Math.
Yossi Azar, Nicholas Pippenger
1990 — conf
Selection Networks.
SIGAL International Symposium on Algorithms
Nicholas Pippenger
1989 J jnl
Analysis of Error Correction by Majority Voting.
Adv. Comput. Res.
Nicholas Pippenger
1989 J jnl
Asymptotic behavior of the chromatic index for hypergraphs.
J. Comb. Theory A
Nicholas Pippenger, Joel H. Spencer
1989 J jnl
Invariance of complexity measures for networks with unreliable gates.
J. ACM
Nicholas Pippenger
1989 J jnl
Knots in random walks.
Discret. Appl. Math.
Nicholas Pippenger
1989 J jnl
Random Sequential Adsorption on Graphs.
SIAM J. Discret. Math.
Nicholas Pippenger
1988 J jnl
Correction to "Computational Complexity of Algebraic Functions".
J. Comput. Syst. Sci.
Nicholas Pippenger
1988 J jnl
Fault Tolerance in Networks of Bounded Degree.
SIAM J. Comput.
Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal
1988 J jnl
Reliable computation by formulas in the presence of noise.
IEEE Trans. Inf. Theory
Nicholas Pippenger
1988 J jnl
Wide-Sense Nonblocking Networks.
SIAM J. Discret. Math.
Paul Feldman, Joel Friedman, Nicholas Pippenger
1987 J jnl
Expanding graphs contain all small trees.
Comb.
Joel Friedman, Nicholas Pippenger
1987 J jnl
Sorting and Selecting in Rounds.
SIAM J. Comput.
Nicholas Pippenger
1987 J jnl
The Complexity of Computations by Networks.
IBM J. Res. Dev.
Nicholas Pippenger
1986 J jnl
Alphabetic Minimax Trees of Degree at Most t.
SIAM J. Comput.
Don Coppersmith, Maria M. Klawe, Nicholas Pippenger
1986 A* conf
Fault Tolerance in Networks of Bounded Degree (Preliminary Version)
STOC
Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal
1986 A* conf
Non-Blocking Networks (Preliminary Version)
STOC
Paul Feldman, Joel Friedman, Nicholas Pippenger
1985 J jnl
Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions.
Theor. Comput. Sci.
Ronald Fagin, Maria M. Klawe, Nicholas Pippenger, Larry J. Stockmeyer
1985 A* conf
On Networks of Noisy Gates
FOCS
Nicholas Pippenger
1984 J jnl
Bounding Fan-out in Logical Networks.
J. ACM
H. James Hoover, Maria M. Klawe, Nicholas Pippenger
1984 A* conf
On Monotone Formulae with Restricted Depth (Preliminary Version)
STOC
Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, Mihalis Yannakakis
1984 A* conf
Parallel Communication with Limited Buffers (Preliminary Version)
FOCS
Nicholas Pippenger
1983 A* conf
On Determinism versus Non-Determinism and Related Problems (Preliminary Version)
FOCS
Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter
1983 J jnl
Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines
Inf. Control.
Allan Borodin, Stephen A. Cook, Nicholas Pippenger
1983 A* conf
Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version)
STOC
Danny Dolev, Cynthia Dwork, Nicholas Pippenger, Avi Wigderson
1982 A* conf
Advances in Pebbling (Preliminary Version).
ICALP
Nicholas Pippenger
1982 A* conf
Probabilistic Simulations (Preliminary Version)
STOC
Nicholas Pippenger
1982 J jnl
Superconcentrators of Depth 2.
J. Comput. Syst. Sci.
Nicholas Pippenger
1981 J jnl
A Fast Parallel Algorithm for Routing in Permutation Networks.
IEEE Trans. Computers
Gavriela Freund Lev, Nicholas Pippenger, Leslie G. Valiant
1981 J jnl
Algebraic Complexity Theory.
IBM J. Res. Dev.
Nicholas Pippenger
1981 J jnl
Bounds on the performance of protocols for a multiple-access broadcast channel .
IEEE Trans. Inf. Theory
Nicholas Pippenger
1981 J jnl
Computational Complexity of Algebraic Functions.
J. Comput. Syst. Sci.
Nicholas Pippenger
1981 J jnl
Pebbling with an Auxiliary Pushdown.
J. Comput. Syst. Sci.
Nicholas Pippenger
1980 J jnl
A New Lower Bound for the Number of Switches in Rearrangeable Networks.
SIAM J. Algebraic Discret. Methods
Nicholas Pippenger
1980 A* conf
Comparative Schematology and Pebbling with Auxiliary Pushdowns (Preliminary Version)
STOC
Nicholas Pippenger
1980 J jnl
On Another Boolean Matrix.
Theor. Comput. Sci.
Nicholas Pippenger
1980 J jnl
On the Evaluation of Powers and Monomials.
SIAM J. Comput.
Nicholas Pippenger
1979 J jnl
Communication: On the Application of Coding Theory to Hashing.
IBM J. Res. Dev.
Nicholas Pippenger
1979 A* conf
Computational Complexity in Algebraic Function Fields (Preliminary Version)
FOCS
Nicholas Pippenger
1979 J jnl
Extendible Hashing - A Fast Access Method for Dynamic Files.
ACM Trans. Database Syst.
Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong
1979 A* conf
On Simultaneous Resource Bounds (Preliminary Version)
FOCS
Nicholas Pippenger
1979 J jnl
Optimal 2, 3-Trees.
SIAM J. Comput.
Raymond E. Miller, Nicholas Pippenger, Arnold L. Rosenberg, Lawrence Snyder
1979 J jnl
Relations Among Complexity Measures.
J. ACM
Nicholas Pippenger, Michael J. Fischer
1979 J jnl
The Minimum Number of Edges in Graphs with Prescribed Paths.
Math. Syst. Theory
Nicholas Pippenger
1978 J jnl
A Time-Space Trade-Off.
J. ACM
Nicholas Pippenger
1978 J jnl
An Explicit Construction of Short Monotone Formulae for the Monotone Symmetric Functions.
Theor. Comput. Sci.
Mark Kleiman, Nicholas Pippenger
1978 J jnl
Generalized Connectors.
SIAM J. Comput.
Nicholas Pippenger
1978 J jnl
On Rearrangeable and Non-Blocking Switching Networks.
J. Comput. Syst. Sci.
Nicholas Pippenger
1978 J jnl
The Complexity of Monotone Boolean Functions.
Math. Syst. Theory
Nicholas Pippenger
1977 J jnl
An Information-Theoretic Method in Combinatorial Theory.
J. Comb. Theory A
Nicholas Pippenger
1977 J jnl
Information Theory and the Complexity of Boolean Functions.
Math. Syst. Theory
Nicholas Pippenger
1977 J jnl
Superconcentrators.
SIAM J. Comput.
Nicholas Pippenger
1976 J jnl
Finding the Median.
J. Comput. Syst. Sci.
Arnold Schönhage, Mike Paterson, Nicholas Pippenger
1976 A* conf
On the Evaluation of Powers and Related Problems (Preliminary Version)
FOCS
Nicholas Pippenger
1976 J jnl
Shifting Graphs and Their Applications.
J. ACM
Nicholas Pippenger, Leslie G. Valiant
1976 A* conf
The Realization of Monotone Boolean Functions (Preliminary Version)
STOC
Nicholas Pippenger
1975 A* conf
Information Theory and the Complexity of Switching Networks (Preliminary Version)
FOCS
Nicholas Pippenger
1975 J jnl
On Crossbar Switching Networks.
IEEE Trans. Commun.
Nicholas Pippenger
1974 J jnl
On the Complexity of Strictly Nonblocking Concentration Networks.
IEEE Trans. Commun.
Nicholas Pippenger