2 citations · 2 across the 4 of their papers we have counts for
6 papers
The Linking Probability of Deep Spider-Web Networks
Nicholas Pippenger
We consider crossbar switching networks with base (that is, constructed from crossbar switches), scale (that is, with inputs, outputs and link…
The average amount of information lost in multiplication
Nicholas Pippenger
We show that if X and Y are integers independently and uniformly distributed in the set {1, ..., N}, then the information lost in forming their product (which is given by the equiv…
Random cyclations
Nicholas Pippenger
Consider n unit intervals, say [1,2], [3,4], ..., [2n-1,2n]. Identify their endpoints in pairs at random, with all (2n-1)!! = (2n-1) (2n-3) ... 3 1 pairings being equally likely. T…
Topological Characteristics of Random Surfaces Generated by Cubic Interactions
Nicholas Pippenger, Kristin Schleich
We consider random topologies of surfaces generated by cubic interactions. Such surfaces arise in various contexts in 2-dimensional quantum gravity and as world-sheets in string th…
Characterizations of 1-Way Quantum Finite Automata
Alex Brodsky, Nicholas Pippenger
The 2-way quantum finite automaton introduced by Kondacs and Watrous can accept non-regular languages with bounded error in polynomial time. If we restrict the head of the automato…
The Computational Complexity of Knot and Link Problems
Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger
We consider the problem of deciding whether a polygonal knot in 3-dimensional Euclidean space is unknotted, capable of being continuously deformed without self-intersection so that…