Nicholas Pippenger

Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger: M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns. FUN 2012: 198-209

Connor Ahlbach, Jeremy Usatine, Nicholas Pippenger: Efficient Algorithms for Zeckendorf Arithmetic. CoRR abs/1207.4497 (2012)

Mark McCann, Nicholas Pippenger: Fault Tolerance in Cellular Automata at Low Fault Rates. CoRR abs/1207.5550 (2012)

Alice Paul, Nicholas Pippenger: A Census of Vertices by Generations in Regular Tessellations of the Plane. Electr. J. Comb. 18(1) (2011)

Alexander Izsak, Nicholas Pippenger: Carry propagation in multiplication by constants. ACM Transactions on Algorithms 7(4): 54 (2011)

Nicholas Pippenger: Two Extensions of Results of Archimedes. The American Mathematical Monthly 118(1): 66-71 (2011)

Nicholas Pippenger: On-the-Fly Algorithms and Sequential Machines. IEEE Trans. Computers 60(9): 1372-1375 (2011)

Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger: The M/M/Infinity Service System with Ranked Servers in Heavy Traffic. CoRR abs/1107.1536 (2011)

Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger: Stochastic Service Systems, Random Interval Graphs and Search Algorithms. CoRR abs/1107.4113 (2011)

Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger: Analysis of an M/M/1 Queue Using Fixed Order of Search for Arrivals and Service. CoRR abs/1108.5356 (2011)

Kevin Fleming, Nicholas Pippenger: Large deviations and moments for the Euler characteristic of a random surface. Random Struct. Algorithms 37(4): 465-476 (2010)

A. H. Hunter, Nicholas Pippenger: Local versus Global Search in Channel Graphs. CoRR abs/1004.2526 (2010)

Krzysztof Majewski, Nicholas Pippenger: Attribute estimation and testing quasi-symmetry. Inf. Process. Lett. 109(4): 233-237 (2009)

Mark McCann, Nicholas Pippenger: Fault tolerance in cellular automata at high fault rates. J. Comput. Syst. Sci. 74(5): 910-918 (2008)

Krzysztof Majewski, Nicholas Pippenger: Attribute Estimation and Testing Quasi-Symmetry. CoRR abs/0708.2105 (2007)

Nicholas Pippenger, Kristin Schleich: Topological characteristics of random triangulated surfaces. Random Struct. Algorithms 28(3): 247-288 (2006)

Nicholas Pippenger: The Linking Probability of Deep Spider-Web Networks. SIAM J. Discrete Math. 20(1): 143-159 (2006)

Mark McCann, Nicholas Pippenger: SRT Division Algorithms as Dynamical Systems. SIAM J. Comput. 34(6): 1279-1301 (2005)

Nicholas Pippenger: The average amount of information lost in multiplication. IEEE Transactions on Information Theory 51(2): 684-687 (2005)

Nicholas Pippenger: Entropy and expected acceptance counts for finite automata. IEEE Transactions on Information Theory 50(1): 78-88 (2004)

Nicholas Pippenger: The shortest disjunctive normal form of a random Boolean function. Random Struct. Algorithms 22(2): 161-186 (2003)

Nicholas Pippenger: The inequalities of quantum information theory. IEEE Transactions on Information Theory 49(4): 773-789 (2003)

Mark McCann, Nicholas Pippenger: SRT Division Algorithms as Dynamical Systems. IEEE Symposium on Computer Arithmetic 2003: 46-53

Alex Brodsky, Nicholas Pippenger: The Boolean Functions Computed by Random Boolean Formulas OR How to Grow the Right Function. CoRR cs.DM/0302028 (2003)

Nicholas Pippenger: Galois theory for minors of finite functions. Discrete Mathematics 254(1-3): 405-419 (2002)

Nicholas Pippenger: Analysis of Carry Propagation in Addition: An Elementary Approach. J. Algorithms 42(2): 317-333 (2002)

Alex Brodsky, Nicholas Pippenger: Characterizations of 1-Way Quantum Finite Automata. SIAM J. Comput. 31(5): 1456-1478 (2002)

Nicholas Pippenger: Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs. SIAM J. Discrete Math. 16(1): 47-64 (2002)

Nicholas Pippenger: Quantum signal propagation in depolarizing channels. IEEE Transactions on Information Theory 48(1): 276-278 (2002)

Nicholas Pippenger: Expected Acceptance Counts for Finite Automata with Almost Uniform Input. ISAAC 2002: 636-646

Nicholas Pippenger: Enumeration of Equicolorable Trees. SIAM J. Discrete Math. 14(1): 93-115 (2001)

Joel Hass, J. C. Lagarias, Nicholas Pippenger: The Computational Complexity of Knot and Link Problems. J. ACM 46(2): 185-211 (1999)

Nicholas Pippenger: Upper and lower bounds for the average-case complexity of path-search. Networks 33(4): 249-259 (1999)

Nicholas Pippenger: Entropy and enumeration of boolean functions. IEEE Transactions on Information Theory 45(6): 2096-2100 (1999)

Nicholas Pippenger: Random interval graphs. Random Struct. Algorithms 12(4): 361-380 (1998)

William S. Evans, Nicholas Pippenger: Average-Case Lower Bounds for Noisy Boolean Decision Trees. SIAM J. Comput. 28(2): 433-446 (1998)

William S. Evans, Nicholas Pippenger: On the Maximum Tolerable Noise for Reliable Computation by Formulas. IEEE Transactions on Information Theory 44(3): 1299-1305 (1998)

Nicholas Pippenger: Theories of computability. Cambridge University Press 1997, isbn 978-0-521-55380-3, pp. I-IX, 1-251

Nicholas Pippenger: Regular Languages and Stone Duality. Theory Comput. Syst. 30(2): 121-134 (1997)

Nicholas Pippenger: Pure Versus Impure Lisp. ACM Trans. Program. Lang. Syst. 19(2): 223-238 (1997)

Joel Hass, J. C. Lagarias, Nicholas Pippenger: The Computational Complexity of Knot and Link Problems. FOCS 1997: 172-181

Nicholas Pippenger: Self-Routing Superconcentrators. J. Comput. Syst. Sci. 52(1): 53-60 (1996)

Geng Lin, Nicholas Pippenger: Routing algorithms for switching networks with probabilistic traffic. Networks 28(1): 21-29 (1996)

Nicholas Pippenger: Pure versus Impure LISP. POPL 1996: 104-109

William S. Evans, Nicholas Pippenger: Lower Bounds for Noisy Boolean Decision Trees. STOC 1996: 620-628

Nicholas Pippenger: Analysis of a Recurrence Arising from a Construction for Nonblocking Networks. SIAM J. Discrete Math. 8(2): 322-345 (1995)

Nicholas Pippenger: Symmetry in Self-Correcting Cellular Automata. J. Comput. Syst. Sci. 49(1): 83-95 (1994)

Geng Lin, Nicholas Pippenger: Parallel Algorithms for Routing in Nonblocking Networks. Mathematical Systems Theory 27(1): 29-40 (1994)

Nicholas Pippenger, Geng Lin: Fault-Tolerant Circuit-Switching Networks. SIAM J. Discrete Math. 7(1): 108-118 (1994)

Nicholas Pippenger: Juggling Networks. Canada-France Conference on Parallel and Distributed Computing 1994: 1-12

Nicholas Pippenger: Self-routing superconcentrators. STOC 1993: 355-361

Nicholas Pippenger: The Asymptotic Optimality of Spider-Web Networks. Discrete Applied Mathematics 37/38: 437-450 (1992)

Martin Dietzfelbinger, Joseph Gil, Yossi Matias, Nicholas Pippenger: Polynomial Hash Functions Are Reliable (Extended Abstract). ICALP 1992: 235-246

Nicholas Pippenger, Geng Lin: Fault-Tolerant Circuit-Switching Networks. SPAA 1992: 229-235

Nicholas Pippenger: An Elementary Approach to Some Analytic Asymptotics. SWAT 1992: 53-61

Nicholas Pippenger: The Blocking Probability of Spider-Web Networks. Random Struct. Algorithms 2(2): 121-150 (1991)

Nicholas Pippenger: Selection Networks. SIAM J. Comput. 20(5): 878-887 (1991)

Nicholas Pippenger: The Expected Capacity of Concentrators. SIAM J. Discrete Math. 4(1): 121-129 (1991)

Nicholas Pippenger, George D. Stamoulis, John N. Tsitsiklis: On a lower bound for the redundancy of reliable networks with noisy gates. IEEE Transactions on Information Theory 37(3): 639-643 (1991)

Geng Lin, Nicholas Pippenger: Parallel Algorithms for Routing in Non-Blocking Networks. SPAA 1991: 272-277

Yossi Azar, Nicholas Pippenger: Parallel selection. Discrete Applied Mathematics 27(1-2): 49-58 (1990)

Nicholas Pippenger: Communication Networks. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 805-834

Mike Paterson, Nicholas Pippenger, Uri Zwick: Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions. FOCS 1990: 642-650

Nicholas Pippenger: Selection Networks. SIGAL International Symposium on Algorithms 1990: 2-11

Nicholas Pippenger: Knots in random walks. Discrete Applied Mathematics 25(3): 273-278 (1989)

Nicholas Pippenger: Invariance of complexity measures for networks with unreliable gates. J. ACM 36(3): 531-539 (1989)

Nicholas Pippenger, Joel H. Spencer: Asymptotic behavior of the chromatic index for hypergraphs. J. Comb. Theory, Ser. A 51(1): 24-42 (1989)

Nicholas Pippenger: Random Sequential Adsorption on Graphs. SIAM J. Discrete Math. 2(3): 393-401 (1989)

Nicholas Pippenger: Correction to "Computational Complexity of Algebraic Functions". J. Comput. Syst. Sci. 37(3): 395-399 (1988)

Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal: Fault Tolerance in Networks of Bounded Degree. SIAM J. Comput. 17(5): 975-988 (1988)

Paul Feldman, Joel Friedman, Nicholas Pippenger: Wide-Sense Nonblocking Networks. SIAM J. Discrete Math. 1(2): 158-173 (1988)

Nicholas Pippenger: Reliable computation by formulas in the presence of noise. IEEE Transactions on Information Theory 34(2): 194-197 (1988)

Joel Friedman, Nicholas Pippenger: Expanding graphs contain all small trees. Combinatorica 7(1): 71-76 (1987)

Nicholas Pippenger: The Complexity of Computations by Networks. IBM Journal of Research and Development 31(2): 235-243 (1987)

Nicholas Pippenger: Sorting and Selecting in Rounds. SIAM J. Comput. 16(6): 1032-1038 (1987)

Don Coppersmith, Maria M. Klawe, Nicholas Pippenger: Alphabetic Minimax Trees of Degree at Most t. SIAM J. Comput. 15(1): 189-192 (1986)

Paul Feldman, Joel Friedman, Nicholas Pippenger: Non-Blocking Networks (Preliminary Version). STOC 1986: 247-254

Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal: Fault Tolerance in Networks of Bounded Degree (Preliminary Version). STOC 1986: 370-379

Ronald Fagin, Maria M. Klawe, Nicholas Pippenger, Larry J. Stockmeyer: Bounded-Depth, Polynomial-Size Circuits for Symmetric Functions. Theor. Comput. Sci. 36: 239-250 (1985)

Nicholas Pippenger: On Networks of Noisy Gates. FOCS 1985: 30-38

H. James Hoover, Maria M. Klawe, Nicholas Pippenger: Bounding Fan-out in Logical Networks. J. ACM 31(1): 13-18 (1984)

Nicholas Pippenger: Parallel Communication with Limited Buffers (Preliminary Version). FOCS 1984: 127-136

Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, Mihalis Yannakakis: On Monotone Formulae with Restricted Depth (Preliminary Version). STOC 1984: 480-487

Allan Borodin, Stephen A. Cook, Nicholas Pippenger: Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines. Information and Control 58(1-3): 113-136 (1983)

Wolfgang J. Paul, Nicholas Pippenger, Endre Szemerédi, William T. Trotter: On Determinism versus Non-Determinism and Related Problems (Preliminary Version). FOCS 1983: 429-438

Danny Dolev, Cynthia Dwork, Nicholas Pippenger, Avi Wigderson: Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version). STOC 1983: 42-51

Nicholas Pippenger: Superconcentrators of Depth 2. J. Comput. Syst. Sci. 24(1): 82-90 (1982)

Nicholas Pippenger: Advances in Pebbling (Preliminary Version). ICALP 1982: 407-417

Nicholas Pippenger: Probabilistic Simulations (Preliminary Version). STOC 1982: 17-26

Nicholas Pippenger: Algebraic Complexity Theory. IBM Journal of Research and Development 25(5): 825-832 (1981)

Nicholas Pippenger: Computational Complexity of Algebraic Functions. J. Comput. Syst. Sci. 22(3): 454-470 (1981)

Nicholas Pippenger: Pebbling with an Auxiliary Pushdown. J. Comput. Syst. Sci. 23(2): 151-165 (1981)

Gavriela Freund Lev, Nicholas Pippenger, Leslie G. Valiant: A Fast Parallel Algorithm for Routing in Permutation Networks. IEEE Trans. Computers 30(2): 93-100 (1981)

Nicholas Pippenger: Bounds on the performance of protocols for a multiple-access broadcast channel . IEEE Transactions on Information Theory 27(2): 145-151 (1981)

Nicholas Pippenger: On the Evaluation of Powers and Monomials. SIAM J. Comput. 9(2): 230-250 (1980)

Nicholas Pippenger: On Another Boolean Matrix. Theor. Comput. Sci. 11: 49-56 (1980)

Nicholas Pippenger: Comparative Schematology and Pebbling with Auxiliary Pushdowns (Preliminary Version). STOC 1980: 351-356

Nicholas Pippenger: Communication: On the Application of Coding Theory to Hashing. IBM Journal of Research and Development 23(2): 225-226 (1979)

Nicholas Pippenger, Michael J. Fischer: Relations Among Complexity Measures. J. ACM 26(2): 361-381 (1979)

Nicholas Pippenger: The Minimum Number of Edges in Graphs with Prescribed Paths. Mathematical Systems Theory 12: 325-346 (1979)

Raymond E. Miller, Nicholas Pippenger, Arnold L. Rosenberg, Lawrence Snyder: Optimal 2, 3-Trees. SIAM J. Comput. 8(1): 42-59 (1979)

Ronald Fagin, Jürg Nievergelt, Nicholas Pippenger, H. Raymond Strong: Extendible Hashing - A Fast Access Method for Dynamic Files. ACM Trans. Database Syst. 4(3): 315-344 (1979)

Nicholas Pippenger: Computational Complexity in Algebraic Function Fields (Preliminary Version). FOCS 1979: 61-65

Nicholas Pippenger: On Simultaneous Resource Bounds (Preliminary Version). FOCS 1979: 307-311

Nicholas Pippenger: A Time-Space Trade-Off. J. ACM 25(3): 509-515 (1978)

Nicholas Pippenger: On Rearrangeable and Non-Blocking Switching Networks. J. Comput. Syst. Sci. 17(2): 145-162 (1978)

Nicholas Pippenger: The Complexity of Monotone Boolean Functions. Mathematical Systems Theory 11: 289-316 (1978)

Nicholas Pippenger: Generalized Connectors. SIAM J. Comput. 7(4): 510-514 (1978)

Mark Kleiman, Nicholas Pippenger: An Explicit Construction of Short Monotone Formulae for the Monotone Symmetric Functions. Theor. Comput. Sci. 7: 325-332 (1978)

Nicholas Pippenger: An Information-Theoretic Method in Combinatorial Theory. J. Comb. Theory, Ser. A 23(1): 99-104 (1977)

Nicholas Pippenger: Information Theory and the Complexity of Boolean Functions. Mathematical Systems Theory 10: 129-167 (1977)

Nicholas Pippenger: Superconcentrators. SIAM J. Comput. 6(2): 298-304 (1977)

Nicholas Pippenger, Leslie G. Valiant: Shifting Graphs and Their Applications. J. ACM 23(3): 423-432 (1976)

Arnold Schönhage, Mike Paterson, Nicholas Pippenger: Finding the Median. J. Comput. Syst. Sci. 13(2): 184-199 (1976)

Nicholas Pippenger: On the Evaluation of Powers and Related Problems (Preliminary Version). FOCS 1976: 258-263

Nicholas Pippenger: The Realization of Monotone Boolean Functions (Preliminary Version). STOC 1976: 204-210

Nicholas Pippenger: Information Theory and the Complexity of Switching Networks (Preliminary Version). FOCS 1975: 113-118