default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDNicholas Pippenger
Person information
- affiliation: Princeton University, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
[p2]Nicholas Pippenger:
Computation with Limited Space. Logic, Automata, and Computational Complexity 2023: 127-140- 2022
- [i11]Nicholas Pippenger:
A Formula for the Determinant. CoRR abs/2206.00134 (2022)
2010 – 2019
- 2015
- [i10]Nabil Zaman, Nicholas Pippenger:
Asymptotic Analysis of Run-Length Encoding. CoRR abs/1504.04070 (2015) - 2014
- [j89]Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger:
Computational Aspects of M.C. Escher's Ribbon Patterns. Theory Comput. Syst. 54(4): 640-658 (2014) - [j88]Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger:
Stochastic service systems, random interval graphs and search algorithms. Random Struct. Algorithms 45(3): 421-442 (2014) - [j87]Kyle Luh, Nicholas Pippenger:
Large-Deviation Bounds for Sampling without Replacement. Am. Math. Mon. 121(5): 449-454 (2014) - 2013
- [j86]Connor Ahlbach, Jeremy Usatine, Nicholas Pippenger:
Barred Preferential Arrangements. Electron. J. Comb. 20(2): 55 (2013) - [j85]Nicholas Pippenger:
Random Cyclations. Electron. J. Comb. 20(4): 9 (2013) - [j84]Mark McCann, Nicholas Pippenger:
Fault tolerance in cellular automata at low fault rates. J. Comput. Syst. Sci. 79(7): 1126-1143 (2013) - [j83]A. H. Hunter, Nicholas Pippenger:
Local versus global search in channel graphs. Networks 62(1): 27-34 (2013) - [i9]Connor Ahlbach, Jeremy Usatine, Nicholas Pippenger:
Gap Theorems for the Delay of Circuits Simulating Finite Automata. CoRR abs/1308.2970 (2013) - 2012
- [c30]Ellen Gethner, David G. Kirkpatrick, Nicholas Pippenger:
M.C. Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns. FUN 2012: 198-209 - [i8]Connor Ahlbach, Jeremy Usatine, Nicholas Pippenger:
Efficient Algorithms for Zeckendorf Arithmetic. CoRR abs/1207.4497 (2012) - [i7]Mark McCann, Nicholas Pippenger:
Fault Tolerance in Cellular Automata at Low Fault Rates. CoRR abs/1207.5550 (2012) - 2011
- [j82]Alice Paul, Nicholas Pippenger:
A Census of Vertices by Generations in Regular Tessellations of the Plane. Electron. J. Comb. 18(1) (2011) - [j81]Alexander Izsak, Nicholas Pippenger:
Carry propagation in multiplication by constants. ACM Trans. Algorithms 7(4): 54:1-54:11 (2011) - [j80]Nicholas Pippenger:
Two Extensions of Results of Archimedes. Am. Math. Mon. 118(1): 66-71 (2011) - [j79]Nicholas Pippenger:
On-the-Fly Algorithms and Sequential Machines. IEEE Trans. Computers 60(9): 1372-1375 (2011) - [i6]Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger:
The M/M/Infinity Service System with Ranked Servers in Heavy Traffic. CoRR abs/1107.1536 (2011) - [i5]Patrick Eschenfeldt, Ben Gross, Nicholas Pippenger:
Stochastic Service Systems, Random Interval Graphs and Search Algorithms. CoRR abs/1107.4113 (2011) - [i4]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) - 2010
- [j78]Kevin Fleming, Nicholas Pippenger:
Large deviations and moments for the Euler characteristic of a random surface. Random Struct. Algorithms 37(4): 465-476 (2010) - [i3]A. H. Hunter, Nicholas Pippenger:
Local versus Global Search in Channel Graphs. CoRR abs/1004.2526 (2010)
2000 – 2009
- 2009
- [j77]Krzysztof Majewski, Nicholas Pippenger:
Attribute estimation and testing quasi-symmetry. Inf. Process. Lett. 109(4): 233-237 (2009) - 2008
- [j76]Mark McCann, Nicholas Pippenger:
Fault tolerance in cellular automata at high fault rates. J. Comput. Syst. Sci. 74(5): 910-918 (2008) - 2007
- [i2]Krzysztof Majewski, Nicholas Pippenger:
Attribute Estimation and Testing Quasi-Symmetry. CoRR abs/0708.2105 (2007) - 2006
- [j75]Nicholas Pippenger, Kristin Schleich:
Topological characteristics of random triangulated surfaces. Random Struct. Algorithms 28(3): 247-288 (2006) - [j74]Nicholas Pippenger:
The Linking Probability of Deep Spider-Web Networks. SIAM J. Discret. Math. 20(1): 143-159 (2006) - 2005
- [j73]Mark McCann, Nicholas Pippenger:
SRT Division Algorithms as Dynamical Systems. SIAM J. Comput. 34(6): 1279-1301 (2005) - [j72]Nicholas Pippenger:
The average amount of information lost in multiplication. IEEE Trans. Inf. Theory 51(2): 684-687 (2005) - 2004
- [j71]Nicholas Pippenger:
Entropy and expected acceptance counts for finite automata. IEEE Trans. Inf. Theory 50(1): 78-88 (2004) - 2003
- [j70]Nicholas Pippenger:
The shortest disjunctive normal form of a random Boolean function. Random Struct. Algorithms 22(2): 161-186 (2003) - [j69]Nicholas Pippenger:
The inequalities of quantum information theory. IEEE Trans. Inf. Theory 49(4): 773-789 (2003) - [c29]Mark McCann, Nicholas Pippenger:
SRT Division Algorithms as Dynamical Systems. IEEE Symposium on Computer Arithmetic 2003: 46-53 - [i1]Alex Brodsky, Nicholas Pippenger:
The Boolean Functions Computed by Random Boolean Formulas OR How to Grow the Right Function. CoRR cs.DM/0302028 (2003) - 2002
- [j68]Nicholas Pippenger:
Galois theory for minors of finite functions. Discret. Math. 254(1-3): 405-419 (2002) - [j67]Nicholas Pippenger:
Analysis of Carry Propagation in Addition: An Elementary Approach. J. Algorithms 42(2): 317-333 (2002) - [j66]Alex Brodsky, Nicholas Pippenger:
Characterizations of 1-Way Quantum Finite Automata. SIAM J. Comput. 31(5): 1456-1478 (2002) - [j65]Nicholas Pippenger:
Enumeration of Matchings in the Incidence Graphs of Complete and Complete Bipartite Graphs. SIAM J. Discret. Math. 16(1): 47-64 (2002) - [j64]Nicholas Pippenger:
Quantum signal propagation in depolarizing channels. IEEE Trans. Inf. Theory 48(1): 276-278 (2002) - [c28]Nicholas Pippenger:
Expected Acceptance Counts for Finite Automata with Almost Uniform Input. ISAAC 2002: 636-646 - 2001
- [j63]Nicholas Pippenger:
Enumeration of Equicolorable Trees. SIAM J. Discret. Math. 14(1): 93-115 (2001)
1990 – 1999
- 1999
- [j62]Joel Hass, J. C. Lagarias, Nicholas Pippenger:
The Computational Complexity of Knot and Link Problems. J. ACM 46(2): 185-211 (1999) - [j61]Nicholas Pippenger:
Upper and lower bounds for the average-case complexity of path-search. Networks 33(4): 249-259 (1999) - [j60]Nicholas Pippenger:
Entropy and enumeration of boolean functions. IEEE Trans. Inf. Theory 45(6): 2096-2100 (1999) - 1998
- [j59]Nicholas Pippenger:
Random interval graphs. Random Struct. Algorithms 12(4): 361-380 (1998) - [j58]William S. Evans, Nicholas Pippenger:
Average-Case Lower Bounds for Noisy Boolean Decision Trees. SIAM J. Comput. 28(2): 433-446 (1998) - [j57]William S. Evans, Nicholas Pippenger:
On the Maximum Tolerable Noise for Reliable Computation by Formulas. IEEE Trans. Inf. Theory 44(3): 1299-1305 (1998) - 1997
- [b1]Nicholas Pippenger:
Theories of computability. Cambridge University Press 1997, ISBN 978-0-521-55380-3, pp. I-IX, 1-251 - [j56]Nicholas Pippenger:
Regular Languages and Stone Duality. Theory Comput. Syst. 30(2): 121-134 (1997) - [j55]Nicholas Pippenger:
Pure Versus Impure Lisp. ACM Trans. Program. Lang. Syst. 19(2): 223-238 (1997) - [c27]Nicholas Pippenger:
Average-case bounds for the complexity of path-search. Advances in Switching Networks 1997: 1-13 - [c26]Joel Hass, J. C. Lagarias, Nicholas Pippenger:
The Computational Complexity of Knot and Link Problems. FOCS 1997: 172-181 - 1996
- [j54]Nicholas Pippenger:
Self-Routing Superconcentrators. J. Comput. Syst. Sci. 52(1): 53-60 (1996) - [j53]Geng Lin, Nicholas Pippenger:
Routing algorithms for switching networks with probabilistic traffic. Networks 28(1): 21-29 (1996) - [c25]Nicholas Pippenger:
Pure versus Impure LISP. POPL 1996: 104-109 - [c24]William S. Evans, Nicholas Pippenger:
Lower Bounds for Noisy Boolean Decision Trees. STOC 1996: 620-628 - 1995
- [j52]Nicholas Pippenger:
Analysis of a Recurrence Arising from a Construction for Nonblocking Networks. SIAM J. Discret. Math. 8(2): 322-345 (1995) - 1994
- [j51]Nicholas Pippenger:
Symmetry in Self-Correcting Cellular Automata. J. Comput. Syst. Sci. 49(1): 83-95 (1994) - [j50]Geng Lin, Nicholas Pippenger:
Parallel Algorithms for Routing in Nonblocking Networks. Math. Syst. Theory 27(1): 29-40 (1994) - [j49]Nicholas Pippenger, Geng Lin:
Fault-Tolerant Circuit-Switching Networks. SIAM J. Discret. Math. 7(1): 108-118 (1994) - [c23]Nicholas Pippenger:
Juggling Networks. Canada-France Conference on Parallel and Distributed Computing 1994: 1-12 - 1993
- [c22]Nicholas Pippenger:
Self-routing superconcentrators. STOC 1993: 355-361 - 1992
- [j48]Nicholas Pippenger:
The Asymptotic Optimality of Spider-Web Networks. Discret. Appl. Math. 37/38: 437-450 (1992) - [c21]Martin Dietzfelbinger
, Joseph Gil, Yossi Matias, Nicholas Pippenger:
Polynomial Hash Functions Are Reliable (Extended Abstract). ICALP 1992: 235-246 - [c20]Nicholas Pippenger, Geng Lin:
Fault-Tolerant Circuit-Switching Networks. SPAA 1992: 229-235 - [c19]Nicholas Pippenger:
An Elementary Approach to Some Analytic Asymptotics. SWAT 1992: 53-61 - 1991
- [j47]Nicholas Pippenger:
The Blocking Probability of Spider-Web Networks. Random Struct. Algorithms 2(2): 121-150 (1991) - [j46]Nicholas Pippenger:
Selection Networks. SIAM J. Comput. 20(5): 878-887 (1991) - [j45]Nicholas Pippenger:
The Expected Capacity of Concentrators. SIAM J. Discret. Math. 4(1): 121-129 (1991) - [j44]Nicholas Pippenger, George D. Stamoulis, John N. Tsitsiklis:
On a lower bound for the redundancy of reliable networks with noisy gates. IEEE Trans. Inf. Theory 37(3): 639-643 (1991) - [c18]Geng Lin, Nicholas Pippenger:
Parallel Algorithms for Routing in Non-Blocking Networks. SPAA 1991: 272-277 - 1990
- [j43]Yossi Azar, Nicholas Pippenger:
Parallel selection. Discret. Appl. Math. 27(1-2): 49-58 (1990) - [c17]Mike Paterson, Nicholas Pippenger, Uri Zwick:
Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions. FOCS 1990: 642-650 - [c16]Nicholas Pippenger:
Selection Networks. SIGAL International Symposium on Algorithms 1990: 2-11 - [p1]Nicholas Pippenger:
Communication Networks. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity (A) 1990: 805-834
1980 – 1989
- 1989
- [j42]Nicholas Pippenger:
Analysis of Error Correction by Majority Voting. Adv. Comput. Res. 5: 171-198 (1989) - [j41]Nicholas Pippenger:
Knots in random walks. Discret. Appl. Math. 25(3): 273-278 (1989) - [j40]Nicholas Pippenger:
Invariance of complexity measures for networks with unreliable gates. J. ACM 36(3): 531-539 (1989) - [j39]Nicholas Pippenger, Joel H. Spencer:
Asymptotic behavior of the chromatic index for hypergraphs. J. Comb. Theory A 51(1): 24-42 (1989) - [j38]Nicholas Pippenger:
Random Sequential Adsorption on Graphs. SIAM J. Discret. Math. 2(3): 393-401 (1989) - 1988
- [j37]Nicholas Pippenger:
Correction to "Computational Complexity of Algebraic Functions". J. Comput. Syst. Sci. 37(3): 395-399 (1988) - [j36]Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal:
Fault Tolerance in Networks of Bounded Degree. SIAM J. Comput. 17(5): 975-988 (1988) - [j35]Paul Feldman, Joel Friedman, Nicholas Pippenger:
Wide-Sense Nonblocking Networks. SIAM J. Discret. Math. 1(2): 158-173 (1988) - [j34]Nicholas Pippenger:
Reliable computation by formulas in the presence of noise. IEEE Trans. Inf. Theory 34(2): 194-197 (1988) - 1987
- [j33]Joel Friedman, Nicholas Pippenger:
Expanding graphs contain all small trees. Comb. 7(1): 71-76 (1987) - [j32]Nicholas Pippenger:
The Complexity of Computations by Networks. IBM J. Res. Dev. 31(2): 235-243 (1987) - [j31]Nicholas Pippenger:
Sorting and Selecting in Rounds. SIAM J. Comput. 16(6): 1032-1038 (1987) - 1986
- [j30]Don Coppersmith, Maria M. Klawe, Nicholas Pippenger:
Alphabetic Minimax Trees of Degree at Most t. SIAM J. Comput. 15(1): 189-192 (1986) - [c15]Paul Feldman, Joel Friedman, Nicholas Pippenger:
Non-Blocking Networks (Preliminary Version). STOC 1986: 247-254 - [c14]Cynthia Dwork, David Peleg, Nicholas Pippenger, Eli Upfal:
Fault Tolerance in Networks of Bounded Degree (Preliminary Version). STOC 1986: 370-379 - 1985
- [j29]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) - [c13]Nicholas Pippenger:
On Networks of Noisy Gates. FOCS 1985: 30-38 - 1984
- [j28]H. James Hoover, Maria M. Klawe, Nicholas Pippenger:
Bounding Fan-out in Logical Networks. J. ACM 31(1): 13-18 (1984) - [c12]Nicholas Pippenger:
Parallel Communication with Limited Buffers (Preliminary Version). FOCS 1984: 127-136 - [c11]Maria M. Klawe, Wolfgang J. Paul, Nicholas Pippenger, Mihalis Yannakakis:
On Monotone Formulae with Restricted Depth (Preliminary Version). STOC 1984: 480-487 - 1983
- [j27]Allan Borodin, Stephen A. Cook, Nicholas Pippenger:
Parallel Computation for Well-Endowed Rings and Space-Bounded Probabilistic Machines. Inf. Control. 58(1-3): 113-136 (1983) - [c10]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 - [c9]Danny Dolev, Cynthia Dwork, Nicholas Pippenger, Avi Wigderson:
Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version). STOC 1983: 42-51 - 1982
- [j26]Nicholas Pippenger:
Superconcentrators of Depth 2. J. Comput. Syst. Sci. 24(1): 82-90 (1982) - [c8]Nicholas Pippenger:
Advances in Pebbling (Preliminary Version). ICALP 1982: 407-417 - [c7]Nicholas Pippenger:
Probabilistic Simulations (Preliminary Version). STOC 1982: 17-26 - 1981
- [j25]Nicholas Pippenger:
Algebraic Complexity Theory. IBM J. Res. Dev. 25(5): 825-832 (1981) - [j24]Nicholas Pippenger:
Computational Complexity of Algebraic Functions. J. Comput. Syst. Sci. 22(3): 454-470 (1981) - [j23]Nicholas Pippenger:
Pebbling with an Auxiliary Pushdown. J. Comput. Syst. Sci. 23(2): 151-165 (1981) - [j22]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) - [j21]Nicholas Pippenger:
Bounds on the performance of protocols for a multiple-access broadcast channel . IEEE Trans. Inf. Theory 27(2): 145-151 (1981) - 1980
- [j20]Nicholas Pippenger:
On the Evaluation of Powers and Monomials. SIAM J. Comput. 9(2): 230-250 (1980) - [j19]Nicholas Pippenger:
A New Lower Bound for the Number of Switches in Rearrangeable Networks. SIAM J. Algebraic Discret. Methods 1(2): 164-167 (1980) - [j18]Nicholas Pippenger:
On Another Boolean Matrix. Theor. Comput. Sci. 11: 49-56 (1980) - [c6]Nicholas Pippenger:
Comparative Schematology and Pebbling with Auxiliary Pushdowns (Preliminary Version). STOC 1980: 351-356
1970 – 1979
- 1979
- [j17]Nicholas Pippenger:
Communication: On the Application of Coding Theory to Hashing. IBM J. Res. Dev. 23(2): 225-226 (1979) - [j16]Nicholas Pippenger, Michael J. Fischer:
Relations Among Complexity Measures. J. ACM 26(2): 361-381 (1979) - [j15]Nicholas Pippenger:
The Minimum Number of Edges in Graphs with Prescribed Paths. Math. Syst. Theory 12: 325-346 (1979) - [j14]Raymond E. Miller, Nicholas Pippenger, Arnold L. Rosenberg, Lawrence Snyder:
Optimal 2, 3-Trees. SIAM J. Comput. 8(1): 42-59 (1979) - [j13]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) - [c5]Nicholas Pippenger:
Computational Complexity in Algebraic Function Fields (Preliminary Version). FOCS 1979: 61-65 - [c4]Nicholas Pippenger:
On Simultaneous Resource Bounds (Preliminary Version). FOCS 1979: 307-311 - 1978
- [j12]Nicholas Pippenger:
A Time-Space Trade-Off. J. ACM 25(3): 509-515 (1978) - [j11]Nicholas Pippenger:
On Rearrangeable and Non-Blocking Switching Networks. J. Comput. Syst. Sci. 17(2): 145-162 (1978) - [j10]Nicholas Pippenger:
The Complexity of Monotone Boolean Functions. Math. Syst. Theory 11: 289-316 (1978) - [j9]Nicholas Pippenger:
Generalized Connectors. SIAM J. Comput. 7(4): 510-514 (1978) - [j8]Mark Kleiman, Nicholas Pippenger:
An Explicit Construction of Short Monotone Formulae for the Monotone Symmetric Functions. Theor. Comput. Sci. 7: 325-332 (1978) - 1977
- [j7]Nicholas Pippenger:
An Information-Theoretic Method in Combinatorial Theory. J. Comb. Theory A 23(1): 99-104 (1977) - [j6]Nicholas Pippenger:
Information Theory and the Complexity of Boolean Functions. Math. Syst. Theory 10: 129-167 (1977) - [j5]Nicholas Pippenger:
Superconcentrators. SIAM J. Comput. 6(2): 298-304 (1977) - 1976
- [j4]Nicholas Pippenger, Leslie G. Valiant:
Shifting Graphs and Their Applications. J. ACM 23(3): 423-432 (1976) - [j3]Arnold Schönhage, Mike Paterson, Nicholas Pippenger:
Finding the Median. J. Comput. Syst. Sci. 13(2): 184-199 (1976) - [c3]Nicholas Pippenger:
On the Evaluation of Powers and Related Problems (Preliminary Version). FOCS 1976: 258-263 - [c2]Nicholas Pippenger:
The Realization of Monotone Boolean Functions (Preliminary Version). STOC 1976: 204-210 - 1975
- [j2]Nicholas Pippenger:
On Crossbar Switching Networks. IEEE Trans. Commun. 23(6): 646-659 (1975) - [c1]Nicholas Pippenger:
Information Theory and the Complexity of Switching Networks (Preliminary Version). FOCS 1975: 113-118 - 1974
- [j1]Nicholas Pippenger:
On the Complexity of Strictly Nonblocking Concentration Networks. IEEE Trans. Commun. 22(11): 1890-1892 (1974)
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-07-30 21:36 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
