BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Nicholas Pippenger

Nicholas Pippenger contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.PRmath.COComputational ComplexityPerformanceComputational GeometryData Structures and AlgorithmsDiscrete MathematicsInformation Theorymath.ACmath.ITmath.STStatistics Theory

Trust snapshot

Quick read

Trust 21 - Emerging
20works
0followers
12topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

20 published item(s)

preprint2022arXiv

A Formula for the Determinant

We give a formula for the determinant of an $n\times n$ matrix with entries from a commutative ring with unit. The formula can be evaluated by a "straight-line program" performing only additions, subtractions and multiplications of ring elements; in particular it requires no divisions or conditional branching (as are required, for example, by Gaussian elimination). The number of operations performed is bounded by a fixed power of $n$, specifically $O(n^4\log n)$. Furthermore, the operations can be partitioned into "stages" in such a way that the operands of the operations in a given stage are either matrix entries or the results of operations in earlier stages, and the number of stages is bounded by a fixed power of the logarithm of $n$, specifically $O\big((\log n)^2\big)$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Carry Propagation in Multiplication by Constants

Suppose that a random n-bit number V is multiplied by an odd constant M, greater than or equal to 3, by adding shifted versions of the number V corresponding to the 1s in the binary representation of the constant M. Suppose further that the additions are performed by carry-save adders until the number of summands is reduced to two, at which time the final addition is performed by a carry-propagate adder. We show that in this situation the distribution of the length of the longest carry-propagation chain in the final addition is the same (up to terms tending to 0 as n tends to infinity) as when two independent n-bit numbers are added, and in particular the mean and variance are the same (again up to terms tending to 0). This result applies to all possible orders of performing the carry-save additions.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Enumeration of Interval Graphs

We present upper and lower bounds for the number $i_n$ of interval graphs on $n$ vertices. Answering a question posed by Hanlon, we show that the ordinary generating function $I(x) = \sum_{n\ge 0} i_n\,x^n$ for the number $i_n$ of $n$-vertex interval graphs has radius of convergence zero. We also show that the exponential generating function $J(x) = \sum_{n\ge 0} i_n\,x^n/n!$ has radius of convergence at least $1/2$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Asymptotic Analysis of Run-Length Encoding

Gallager and Van Voorhis have found optimal prefix-free codes $κ(K)$ for a random variable $K$ that is geometrically distributed: $\Pr[K=k] = p(1-p)^k$ for $k\ge 0$. We determine the asymptotic behavior of the expected length ${\rm Ex}[{\#κ(K)}]$ of these codes as $p\to 0$: $${\rm Ex}[{\#κ(K)}] = \log_2 {1\over p} + \log_2 \log 2 + 2 + f\left(\log_2 {1\over p} + \log_2 \log 2\right) + O(p),$$ where $$f(z) = 4\cdot 2^{-2^{1-\{z\}}} - \{z\} - 1,$$ and $\{z\} = z - \lfloor z\rfloor$ is the fractional part of $z$. The function $f(z)$ is a periodic function (with period $1$) that exhibits small oscillations (with magnitude less than $0.005$) about an even smaller average value (less than $0.0005$).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Self-intersections of Two-Dimensional Equilateral Random Walks and Polygons

We study the mean and variance of the number of self-intersections of the equilateral isotropic random walk in the plane, as well as the corresponding quantities for isotropic equilateral random polygons (random walks conditioned to return to their starting point after a given number of steps). The expected number of self-intersections is $(2/π^2)n\log n + O(n)$ for both walks and polygons with $n$ steps. The variance is $O(n^2 \log n)$ for both walks and polygons, which shows that the number of self-intersections exhibits concentration around the mean.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Counting the Angels and Devils in Escher's Circle Limit IV

We derive the rational generating function that enumerates the angels and devils in M. C. Escher's {\it Circle Limit IV} according to their combinatorial distance from the six creatures whose feet meet at the center of the disk. This result shows that the base of the exponential rate of growth is $1.582\ldots$ (the largest root of the polynomial $1 - z^2 - 2z^3 - z^4 + z^6$).

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Gap Theorems for the Delay of Circuits Simulating Finite Automata

We study the delay (also known as depth) of circuits that simulate finite automata, showing that only certain growth rates (as a function of the number $n$ of steps simulated) are possible. A classic result due to Ofman (rediscovered and popularized by Ladner and Fischer) says that delay $O(\log n)$ is always sufficient. We show that if the automaton is "generalized definite", then delay O(1) is sufficient, but otherwise delay $Ω(\log n)$ is necessary; there are no intermediate growth rates. We also consider "physical" (rather than "logical") delay, whereby we consider the lengths of wires when inputs and outputs are laid out along a line. In this case, delay O(n) is clearly always sufficient. We show that if the automaton is "definite", then delay O(1) is sufficient, but otherwise delay $Ω(n)$ is necessary; again there are no intermediate growth rates. Inspired by an observation of Burks, Goldstein and von Neumann concerning the average delay due to carry propagation in ripple-carry adders, we derive conditions for the average physical delay to be reduced from O(n) to $O(\log n)$, or to O(1), when the inputs are independent and uniformly distributed random variables; again there are no intermediate growth rates. Finally we consider an extension of this last result to a situation in which the inputs are not independent and uniformly distributed, but rather are produced by a non-stationary Markov process, and in which the computation is not performed by a single automaton, but rather by a sequence of automata acting in alternating directions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

A Combinatorial Interpretation of the Joint Cumulant

In this paper, we apply the combinatorial proof technique of Description, Involution, Exceptions (DIE) to prove various known identities for the joint cumulant. Consider a set of random variables $S = \{X_1,..., X_n\} $. Motivated by the definition of the joint cumulant, we define $ \sC(S) $ as the set of cyclically arranged partitions of $S$, allowing us to express the joint cumulant of $ S $ as a weighted, alternating sum over $\sC(S)$. We continue to define other combinatorial objects that allow us to rewrite expressions originally in terms of the joint cumulant as weighted sums over the set of these combinatorial objects. Then by constructing weight-preserving, sign-reversing involutions on these objects, we evaluate the original expressions to prove the identities, demonstrating the utility of DIE.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Barred Preferential Arrangements

A preferential arrangement of a set is a total ordering of the elements of that set with ties allowed. A barred preferential arrangement is one in which the tied blocks of elements are ordered not only amongst themselves but also with respect to one or more bars. We present various combinatorial identities for r_{m,l}, the number of barred preferential arrangements of l elements with m bars, using both algebraic and combinatorial arguments. Our main result is an expression for r_{m,l} as a linear combination of the r_k (= r_{0,k}, the number of unbarred preferential arrangements of k elements) for l <= k<=l+m. We also study those arrangements in which the sections, into which the blocks are segregated by the bars, must be nonempty. We conclude with an expression of r_l as an infinite series that is both convergent and asymptotic.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Fault Tolerance in Cellular Automata at Low Fault Rates

A commonly used model for fault-tolerant computation is that of cellular automata. The essential difficulty of fault-tolerant computation is present in the special case of simply remembering a bit in the presence of faults, and that is the case we treat in this paper. The conceptually simplest mechanism for correcting errors in a cellular automaton is to determine the next state of a cell by taking a majority vote among its neighbors (including the cell itself, if necessary to break ties). We are interested in which regular two-dimensional tessellations can tolerate faults using this mechanism, when the fault rate is sufficiently low. We consider both the traditional transient fault model (where faults occur independently in time and space) and a recently introduced combined fault model which also includes manufacturing faults (which occur independently in space, but which affect cells for all time). We completely classify regular two-dimensional tessellations as to whether they can tolerate combined transient and manufacturing faults, transient faults but not manufacturing faults, or not even transient faults.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A Bound on the Variance of the Waiting Time in a Queueing System

Kingman has shown, under very weak conditions on the interarrival- and sevice-time distributions, that First-Come-First-Served minimizes the variance of the waiting time among possible service disciplines. We show, under the same conditions, that Last-Come-First-Served maximizes the variance of the waiting time, thereby giving an upper bound on the variance among all disciplines.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Analysis of an M/M/1 Queue Using Fixed Order of Search for Arrivals and Service

We analyze an M/M/1 queue with a service discipline in which customers, upon arriving when the server is busy, search a sequence of stations for a vacant station at which to wait, and in which the server, upon becoming free when one or more customers are waiting, searches the stations in the same order for a station occupied by a customer to serve. We show how to find complete asymptotic expansions for all the moments of the waiting time in the heavy traffic limit. We show in particular that the variance of the waiting time for this discipline is more similar to that of last-come-first-served (which has a pole of order three as the arrival rate approaches the service rate) than that of first-come-first-served (which has pole of order two).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Asymptotic Behavior of the Moments of the Maximum Queue Length During a Busy Period

We give a simple derivation of the distribution of the maximum L of the length of the queue during a busy period for the M/M/1 queue with lambda<1 the ratio between arrival rate and service rate. We observe that the asymptotic behavior of the moments of L is related to that of Lambert series for the generating functions for the sums of powers of divisors of positive integers. We show how to obtain asymptotic expansions for these moments with error terms having order as large a power of 1-lambda as desired.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Martingale Couplings and Bounds on the Tails of Probability Distributions

Hoeffding has shown that tail bounds on the distribution for sampling from a finite population with replacement also apply to the corresponding cases of sampling without replacement. (A special case of this result is that binomial tail bounds apply to the corresponding hypergeometric tails.) We give a new proof of Hoeffding&#39;s result by constructing a martingale coupling between the sampling distributions. This construction is given by an explicit combinatorial procedure involving balls and urns. We then apply this construction to create martingale couplings between other pairs of sampling distributions, both without replacement and with &#34;surreplacement&#34; (that is, sampling in which not only is the sampled individual replaced, but some number of &#34;copies&#34; of that individual are added to the population).

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Stochastic Service Systems, Random Interval Graphs and Search Algorithms

We consider several stochastic service systems, and study the asymptotic behavior of the moments of various quantities that have application to models for random interval graphs and algorithms for searching for an idle server or empty waiting station. In two cases the moments turn out to involve Lambert series for the generating functions for the sums of powers of divisors of positive integers. For these cases we are able to obtain complete asymptotic expansions for the moments of the quantities in question.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The M/M/Infinity Service System with Ranked Servers in Heavy Traffic

We consider an M/M/Infinity service system in which an arriving customer is served by the first idle server in an infinite sequence S_1, S_2, ... of servers. We determine the first two terms in the asymptotic expansions of the moments of L as lambda tends to infinity, where L is the index of the server S_L serving a newly arriving customer in equilibrium, and lambda is the ratio of the arrival rate to the service rate. The leading terms of the moments show that L/lambda tends to a uniform distribution on [0,1].

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

A Census of Vertices by Generations in Regular Tessellations of the Plane

We consider regular tessellations of the plane as infinite graphs in which $q$ edges and $q$ faces meet at each vertex, and in which $p$ edges and $p$ vertices surround each face. For $1/p + 1/q = 1/2$, these are tilings of the Euclidean plane; for $1/p + 1/q < 1/2 $, they are tilings of the hyperbolic plane. We choose a vertex as the origin, and classify vertices into generations according to their distance (as measured by the number of edges in a shortest path) from the origin. For all $p\ge 3$ and $q \ge 3$ with $1/p + 1/q \le 1/2 $, we determine the rational generating function giving the number of vertices in each generation.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Local versus Global Search in Channel Graphs

Previous studies of search in channel graphs has assumed that the search is global; that is, that the status of any link can be probed by the search algorithm at any time. We consider for the first time local search, for which only links to which an idle path from the source has already been established may be probed. We show that some well known channel graphs may require exponentially more probes, on the average, when search must be local than when it may be global.

0 citations0 reviewsNo code linkedOpen access