Zobrazeno 1 - 10
of 236
pro vyhledávání: '"Pippenger, Nicholas"'
Autor:
Pippenger, Nicholas
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
Externí odkaz:
http://arxiv.org/abs/2206.00134
Autor:
Yang, Joyce C., Pippenger, Nicholas
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
Externí odkaz:
http://arxiv.org/abs/1609.02479
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 s
Externí odkaz:
http://arxiv.org/abs/1508.05992
Autor:
Zaman, Nabil, Pippenger, Nicholas
Gallager and Van Voorhis have found optimal prefix-free codes $\kappa(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}[{\#\kappa
Externí odkaz:
http://arxiv.org/abs/1504.04070
Autor:
Choi, John, Pippenger, Nicholas
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 tha
Externí odkaz:
http://arxiv.org/abs/1310.1357
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
Externí odkaz:
http://arxiv.org/abs/1308.2970
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 o
Externí odkaz:
http://arxiv.org/abs/1211.0652
Autor:
Pippenger, Nicholas
We give simple proofs, under minimal hypotheses, of the Weak Law of Large Numbers and the Central Limit Theorem for independent identically distributed random variables. These proofs use only the elementary calculus, together with the most basic noti
Externí odkaz:
http://arxiv.org/abs/1207.6078
Autor:
McCann, Mark, Pippenger, Nicholas
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 tr
Externí odkaz:
http://arxiv.org/abs/1207.5550
We study the problem of addition and subtraction using the Zeckendorf representation of integers. We show that both operations can be performed in linear time; in fact they can be performed by combinational logic networks with linear size and logarit
Externí odkaz:
http://arxiv.org/abs/1207.4497