329 citations · 345 across the 8 of their papers we have counts for
8 papers
The Promise Polynomial Hierarchy
Adam Chalcraft, Samuel Kutin, David Petrie Moulton
The polynomial hierarchy is a grading of problems by difficulty, including P, NP and coNP as the best known classes. The promise polynomial hierarchy is similar, but extended to in…
Graph pegging numbers
Geir Helleloid, Madeeha Khalid, David Petrie Moulton +1
In graph pegging, we view each vertex of a graph as a hole into which a peg can be placed, with checker-like ``pegging moves'' allowed. Motivated by well-studied questions in graph…
Simple formulas for lattice paths avoiding certain periodic staircase boundaries
Robin J. Chapman, Timothy Y. Chow, Amit Khetan +2
There is a strikingly simple classical formula for the number of lattice paths avoiding the line x = ky when k is a positive integer. We show that the natural generalization of thi…
Computation at a distance
Samuel A. Kutin, David Petrie Moulton, Lawren M. Smithline
We consider a model of computation motivated by possible limitations on quantum computers. We have a linear array of n wires, and we may perform operations only on pairs of adjacen…
A new quantum ripple-carry addition circuit
Steven A. Cuccaro, Thomas G. Draper, Samuel A. Kutin +1
We present a new linear-depth ripple-carry quantum addition circuit. Previous addition circuits required linearly many ancillary qubits; our new adder uses only a single ancillary…
Flows that are sums of hamiltonian cycles in Cayley graphs on abelian groups
Dave Morris, Joy Morris, David P. Moulton
If X is any connected Cayley graph on any finite abelian group, we determine precisely which flows on X can be written as a sum of hamiltonian cycles. (This answers a question of B…