The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts (2007)
Moore, Cristopher, Rockmore, Daniel, Russell, Alexander, Schulman, Leonard J.
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which an unknown subgroup $H$ of a group $G$ must be...
The power of choice in network growth (2007)
D'Souza, Raissa M., Krapivsky, Paul L., Moore, Cristopher
The "power of choice" has been shown to radically alter the behavior of a number of randomized algorithms. Here we explore the effects of choice on models of tree and network growth. In our models...
A classical one-way function to confound quantum adversaries (2007)
Moore, Cristopher, Russell, Alexander, Vazirani, Umesh
The promise of quantum computation and its consequences for complexity-theoretic cryptography motivates an immediate search for cryptosystems which can be implemented with current technology, but...
Moore, Cristopher, Russell, Alexander, Sniady, Piotr
It is known that any quantum algorithm for Graph Isomorphism that works within the framework of the hidden subgroup problem (HSP) must perform highly entangled measurements across \Omega(n \log n)...
Structural Inference of Hierarchies in Networks (2006)
Clauset, Aaron, Moore, Cristopher, Newman, M. E. J.
One property of networks that has received comparatively little attention is hierarchy, i.e., the property of having vertices that cluster together in groups, which then join to form groups of...
On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism (2006)
Moore, Cristopher, Russell, Alexander
It is known that any quantum algorithm for Graph Isomorphism that works within the framework of the hidden subgroup problem (HSP) must perform highly entangled measurements across Omega(n log n)...
Exact solutions for models of evolving networks with addition and deletion of nodes (2006)
Moore, Cristopher, Ghoshal, Gourab, Newman, M. E. J.
There has been considerable recent interest in the properties of networks, such as citation networks and the worldwide web, that grow by the addition of vertices, and a number of simple solvable...
Quantum Algorithms for Simon's Problem Over General Groups (2006)
Alagic, Gorjan, Moore, Cristopher, Russell, Alexander
Daniel Simon's 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (HSP) over Z_2^n provided one of the first algebraic problems for which quantum computers are...
Moore, Cristopher, Russell, Alexander
We establish a general method for proving bounds on the information that can be extracted via arbitrary entangled measurements on tensor products of hidden subgroup coset states. When applied to the...
New Periodic Orbits for the n-Body Problem (2005)
Moore, Cristopher, Nauenberg, Michael
Since the discovery of the figure-8 orbit for the three-body problem [Moore 1993] a large number of periodic orbits of the n-body problem with equal masses and beautiful symmetries have been...
Strong Fourier Sampling Fails over $G^n$ (2005)
Alagic, Gorjan, Moore, Cristopher, Russell, Alexander
We present a negative result regarding the hidden subgroup problem on the powers $G^n$ of a fixed group $G$. Under a condition on the base group $G$, we prove that strong Fourier sampling cannot...
Moore, Cristopher, Russell, Alexander
This article has been withdrawn by the authors.
Scale Invariance in Road Networks (2005)
Kalapala, Vamsi, Sanwalani, Vishal, Clauset, Aaron, Moore, Cristopher
We study the topological and geographic structure of the national road networks of the United States, England and Denmark. By transforming these networks into their dual representation, where roads...
Rapid Mixing for Lattice Colorings with Fewer Colors (2005)
Achlioptas, Dimitris, Molloy, Michael, Moore, Cristopher, Van Bussell, Frank
We provide an optimally mixing Markov chain for 6-colorings of the square lattice on rectangular regions with free, fixed, or toroidal boundary conditions. This implies that the uniform distribution...
Automatic Filters for the Detection of Coherent Structure in Spatiotemporal Systems (2005)
Shalizi, Cosma Rohilla, Haslinger, Robert, Rouquier, Jean-Baptiste, Klinkner, Kristina Lisa, Moore, Cristopher
Most current methods for identifying coherent structures in spatially-extended systems rely on prior information about the form which those structures take. Here we present two new approaches to...
Moore, Cristopher, Istrate, Gabriel, Demopoulos, Demetrios, Vardi, Moshe Y.
We compute the probability of satisfiability of a class of random Horn-SAT formulae, motivated by a connection with the nonemptiness problem of finite tree automata. In particular, when the maximum...
Explicit Multiregister Measurements for Hidden Subgroup Problems (2005)
Moore, Cristopher, Russell, Alexander
We present an explicit measurement in the Fourier basis that solves an important case of the Hidden Subgroup Problem, including the case to which Graph Isomorphism reduces. This entangled measurement...
Hiding Satisfying Assignments: Two are Better than One (2005)
Achlioptas, Dimitris, Jia, Haixia, Moore, Cristopher
The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k-SAT formulas whose...
Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively (2005)
Jia, Haixia, Moore, Cristopher, Strain, Doug
To test incomplete search algorithms for constraint satisfaction problems such as 3-SAT, we need a source of hard, but satisfiable, benchmark instances. A simple way to do this is to choose a random...
The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts (2005)
Moore, Cristopher, Rockmore, Daniel, Russell, Alexander, Schulman, Leonard J.
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a Hidden Subgroup problem, in which an unknown subgroup H of a group G must be...
On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs (2005)
Achlioptas, Dimitris, Clauset, Aaron, Kempe, David, Moore, Cristopher
Understanding the structure of the Internet graph is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining its graph...
Moore, Cristopher, Russell, Alexander
Recently Bacon, Childs and van Dam showed that the ``pretty good measurement'' (PGM) is optimal for the Hidden Subgroup Problem on the dihedral group D_n in the case where the hidden subgroup is...
The Symmetric Group Defies Strong Fourier Sampling: Part I (2005)
Moore, Cristopher, Russell, Alexander, Schulman, Leonard J.
We resolve the question of whether Fourier sampling can efficiently solve the hidden subgroup problem. Specifically, we show that the hidden subgroup problem over the symmetric group cannot be...
The Symmetric Group Defies Strong Fourier Sampling: Part II (2005)
Moore, Cristopher, Russell, Alexander
Part I of this paper showed that the hidden subgroup problem over the symmetric group--including the special case relevant to Graph Isomorphism--cannot be efficiently solved by strong Fourier...
How much backtracking does it take to color random graphs? Rigorous results on heavy tails (2004)
Jia, Haixia, Moore, Cristopher
Many backtracking algorithms exhibit heavy-tailed distributions, in which their running time is often much longer than their median. We analyze the behavior of two natural variants of the...
Accuracy and Scaling Phenomena in Internet Mapping (2004)
Clauset, Aaron, Moore, Cristopher
A great deal of effort has been spent measuring topological features of the Internet. However, it was recently argued that sampling based on taking paths or traceroutes through the network from a...
Finding community structure in very large networks (2004)
Clauset, Aaron, Newman, M. E. J., Moore, Cristopher
The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large...
From spin glasses to hard satisfiable formulas (2004)
Jia, Haixia, Moore, Cristopher, Selman, Bart
We introduce a highly structured family of hard satisfiable 3-SAT formulas corresponding to an ordered spin-glass model from statistical physics. This model has provably ``glassy'' behavior; that is,...
Why Mapping the Internet is Hard (2004)
Clauset, Aaron, Moore, Cristopher
Despite great effort spent measuring topological features of large networks like the Internet, it was recently argued that sampling based on taking paths through the network (e.g., traceroutes)...
The Chromatic Number of Random Regular Graphs (2004)
Achlioptas, Dimitris, Moore, Cristopher
Given any integer d >= 3, let k be the smallest integer such that d < 2k log k. We prove that with high probability the chromatic number of a random d-regular graph is k, k+1, or k+2, and that if...
Traceroute sampling makes random graphs appear to have power law degree distributions (2003)
Clauset, Aaron, Moore, Cristopher
The topology of the Internet has typically been measured by sampling traceroutes, which are roughly shortest paths from sources to destinations. The resulting measurements have been used to infer...
The Resolution Complexity of Random Graph k-Colorability (2003)
Paul Beame, Joseph Culberson, David Mitchell, Cristopher Moore
We consider the resolution proof complexity of propositional formulas which encode random instances of graph k-colorability. We obtain a tradeoff between the graph density and the resolution proof...
Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold (2003)
Achlioptas, Dimitris, Moore, Cristopher
Many NP-complete constraint satisfaction problems appear to undergo a "phase transition'' from solubility to insolubility when the constraint density passes through a critical threshold. In all such...
How Do Networks Become Navigable? (2003)
Clauset, Aaron, Moore, Cristopher
Networks created and maintained by social processes, such as the human friendship network and the World Wide Web, appear to exhibit the property of navigability: namely, not only do short paths exist...
Sampling Grid Colourings with Fewer Colours (2003)
Dimitris Achlioptas, Mike Molloy, Cristopher Moore, Frank Van Bussel
We provide an optimally mixing Markov chain for 6-colourings of the square grid.
Generic Quantum Fourier Transforms (2003)
Moore, Cristopher, Rockmore, Daniel, Russell, Alexander
The quantum Fourier transform (QFT) is the principal algorithmic tool underlying most efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits...
What Is a Macrostate? Subjective Observations and Objective Dynamics (2003)
Shalizi, Cosma Rohilla, Moore, Cristopher
We consider the question of whether thermodynamic macrostates are objective consequences of dynamics, or subjective reflections of our ignorance of a physical system. We argue that they are both;...
What Is a Macrostate? Subjective Observations and Objective Dynamics (2003)
Shalizi, Cosma Rohilla, Moore, Cristopher
We consider the question of whether thermodynamic macrostates are objective consequences of dynamics, or subjective reflections of our ignorance of a physical system. We argue that they are both;...
Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell
We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed...
A Note on the Representational Incompatibility (2002)
Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell
We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed...
The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling (2002)
Moore, Cristopher, Rockmore, Daniel, Russell, Alexander, Schulman, Leonard
Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a subgroup H of a group G must be determined...
The Asymptotic Order of the k-SAT Threshold (2002)
Achlioptas, Dimitris, Moore, Cristopher
Form a random k-SAT formula on n variables by selecting uniformly and independently m=rn clauses out of all 2^k (n choose k) possible k-clauses. The Satisfiability Threshold Conjecture asserts that...
The Asymptotic Order of the Random k-SAT Threshold (2002)
Dimitris Achlioptas, Cristopher Moore
Form a random k-SAT formula on n variables by selecting uniformly and independently m = rn clauses out of all 2 possible k-clauses. The Satisfiability Threshold Conjecture asserts that for each k...
Eric Allender, Sanjeev Arora, Michael Kearns, Cristopher Moore, Alexander Russell
We establish a new hardness result that shows that the difficulty of planning in factored Markov decision processes is representational rather than just computational. More precisely, we give a fixed...
One-Dimensional Peg Solitaire, and Duotaire (2002)
We solve the problem of one-dimensional Peg Solitaire. In particular, we show that the set of configurations that can be reduced to a single peg forms a regular language, and that a linear-time...
Polyabelian loops and Boolean completeness (2002)
This paper is organized as follows. Section 2 gives an introduction to the algebraic terms and concepts we will use. In Section 3 we de ne the functional closure of a groupoid, and show that simple...
On the 2-Colorability of Random Hypergraphs (2002)
Dimitris Achlioptas, Cristopher Moore
A 2-coloring of a hypergraph is a mapping from its vertices to a set of two colors such that no edge is monochromatic. Let Hk (n; m) be a random k-uniform hypergraph on n vertices formed by picking m...
Almost All Graphs With Average Degree 4 Are 3-Colorable (2002)
Dimitris Achlioptas, Cristopher Moore
The technique of using di#erential equations to approximate the mean path of Markov chains has proved very useful in the average-case analysis of algorithms. Here, we significantly expand the range...
Quantum and Stochastic Branching Programs of Bounded Width (2002)
Ablayev, Farid, Moore, Cristopher, Pollett, Chris
In this paper we show that one qubit polynomial time computations are at least as powerful as $\NC^1$ circuits. More precisely, we define syntactic models for quantum and stochastic branching...
An important objective of the algebraic theory of languages is to determine the combinatorial properties of the languages recognized by finite groups and semigroups. In [20], finite nilpotent groups...
Counting, Fanout, And The Complexity Of Quantum Acc (2001)
Frederic Green, Steven Homer, Cristopher Moore, Christopher Pollett
q are distinct primes, QACC[q] is strictly more powerful than its classical counterpart, as is QAC 0 when fanout is allowed. This adds to the growing list of quantum complexity classes which are...
Quantum Walks on the Hypercube (2001)
Cristopher Moore, Alexander Russell
Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical...
One-Dimensional Peg Solitaire, and Duotaire (2001)
Peg Solitaire, Cristopher Moore
We solve the problem of one-dimensional Peg Solitaire. In particular, we show that the set of congurations that can be reduced to a single peg forms a regular language, and that a linear-time...
An analog characterization of the Grzegorczyk hierarchy (2001)
Manuel Lameiras Campagnolo, Cristopher Moore
We study a restricted version of Shannon's General . . .
Computational Complexity in Physics (2001)
ally started to build computers | as Turing's ideas were joined with von Neumann's | the question became not just whether a set or problem is computable or not, but whether it is feasibly computable,...
Computational Complexity in Physics (2001)
This is a brief review paper summarizing talks at the NATO school on Complexity and Large Deviations in Geilo, Norway, 2001.
Tiling groups for Wang tiles (2001)
Cristopher Moore, Ivan Rapaport
We apply tiling groups and height functions to tilings of regions in the plane by Wang tiles, which are squares with colored boundaries where the colors of shared edges must match. We dene a set of...
Hard Tiling Problems with Simple Tiles (2001)
Cristopher Moore, John Michael Robson
It is well-known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on...
Counting, Fanout, and the Complexity of Quantum ACC (2001)
Green, Frederic, Homer, Steven, Moore, Cristopher, Pollett, Christopher
We propose definitions of $\QAC^0$, the quantum analog of the classical class $\AC^0$ of constant-depth circuits with AND and OR gates of arbitrary fan-in, and $\QACC[q]$, the analog of the class...
Ribbon Tile Invariants from Signed Area (2001)
. Ribbon tiles are polyominoes consisting of n squares laid out in a path, each step of which goes north or east. Tile invariants were first introduced in [P1], where a full basis of invariants of...
Quantum Walks on the Hypercube (2001)
Moore, Cristopher, Russell, Alexander
Recently, it has been shown that one-dimensional quantum walks can mix more quickly than classical random walks, suggesting that quantum Monte Carlo algorithms can outperform their classical...
The Phase Transition in 1-in-k SAT and NAE 3-SAT (2001)
Dimitris Achlioptas, Arthur Chtcherba, Gabriel Istrate, Cristopher Moore
this paper we study random instances of two other canonical variations of satisability, 1-in-k SAT and Not-All-Equal 3-SAT. Like random k-SAT, each generative model has one parameter c = m=n, the...
Ribbon Tile Invariants from Signed Area (2001)
Ribbon tiles are polyominoes consisting of n squares laid out in a path, each step of which goes north or east. Tile invariants were rst introduced in [P], where a full basis of invariants of ribbon...
Satisfiability of Systems of Equations over Finite Monoids (2000)
Cristopher Moore, Pascal Tesson
We study the computational complexity of determining whether a systems of equations over a fixed finite monoid has a solution. In [6], it was shown that in the restricted case of groups the problem...
Queues, Stacks, and Transcendentality at the Transition to Chaos (2000)
Cristopher Moore, Summary Bruno Salvy
) and its evolution as increases from 0 to 1. For instance, the language corresponding to in Figure 2 is L = 0 ? 1 ? (10) ? (1011) ? : This can be interpreted as follows: the rst iterates can be...
One-Dimensional Peg Solitaire, and Duotaire (2000)
Peg Solitaire, Cristopher Moore
. We solve the problem of one-dimensional Peg Solitaire. In particular, we show that the set of congurations that can be reduced to a single peg forms a regular language, and that a linear-time...
Ribbon Tile Invariants from Signed Area (2000)
. Ribbon tiles are polyominoes consisting of n squares laid out in a path, each step of which goes north or east. Tile invariants were rst introduced in [P], where a full basis of invariants of...
Ribbon Tile Invariants from Signed Area (2000)
. Ribbon tiles are polyominoes consisting of n squares laid out in a path, each step of which goes north or east. Tile invariants were first introduced in [P], where a full basis of invariants of...
Parallel Quantum Computation and Quantum Codes (2000)
. We study the class QNC of ecient parallel quantum circuits, the quantum analog of NC. We exhibit several useful gadgets and prove that various classes of circuits can be parallelized to logarithmic...
One-Dimensional Peg Solitaire, and Duotaire (2000)
Moore, Cristopher, Eppstein, David
We solve the problem of one-dimensional Peg Solitaire. In particular, we show that the set of configurations that can be reduced to a single peg forms a regular language, and that a linear-time...
Who Wins Domineering on Rectangular Boards? (2000)
Lachmann, Michael, Moore, Cristopher, Rapaport, Ivan
Using mostly elementary considerations, we find out who wins the game of Domineering on all rectangular boards of width 2, 3, 5, and 7. We obtain bounds on other boards as well, and prove the...
One-Dimensional Peg Solitaire (2000)
Moore, Cristopher, Eppstein, David
We solve the problem of one-dimensional peg solitaire. In particular, we show that the set of configurations that can be reduced to a single peg forms a regular language, and that a linear-time...
Exact Solution of Site and Bond Percolation on Small-World Networks (2000)
We study percolation on small-world networks, which has been proposed as a simple model of the propagation of disease. The occupation probabilities of sites and bonds correspond to the susceptibility...
Internal Diffusion-Limited Aggregation: Parallel Algorithms and Complexity (2000)
The computational complexity of internal di usion-limited aggregation (DLA) is examined from both a theoretical and a practical point of view. We show that for two or more dimensions, the problem of...
Complexity of Two-Dimensional Patterns (2000)
Kristian Lindgren, Cristopher Moore
In dynamical systems such as cellular automata and iterated maps, it is often useful to look at a language or set of symbol sequences produced by the system. There are well-established classification...
Who Wins Domineering on Rectangular Boards? (2000)
Michael Lachmann, Cristopher Moore, Ivan Rapaport
. Using mostly elementary considerations, we nd out who wins the game of Domineering on all rectangular boards of width 2, 3, 5, and 7. We obtain bounds on other boards as well, and prove the...
One-Dimensional Peg Solitaire (2000)
. We solve the problem of one-dimensional peg solitaire. In particular, we show that the set of congurations that can be reduced to a single peg forms a regular language, and that a linear-time...
Exact Solution of Site and Bond Percolation on Small-World Networks (2000)
We study percolation on small-world networks, which has been proposed as a simple model of the propagation of disease. The occupation probabilities of sites and bonds correspond to the susceptibility...
Hard Tiling Problems with Simple Tiles (2000)
Moore, Cristopher, Robson, John Michael
It is well-known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on...
Exact solution of site and bond percolation on small-world networks (2000)
Moore, Cristopher, Newman, M. E. J.
We study percolation on small-world networks, which has been proposed as a simple model of the propagation of disease. The occupation probabilities of sites and bonds correspond to the susceptibility...
Exact Solution of Site and Bond Percolation on Small-World Networks (2000)
We study percolation on small-world networks, which has been proposed as a simple model of the propagation of disease. The occupation probabilities of sites and bonds correspond to the susceptibility...
An Analog Characterization of the Subrecursive Functions (2000)
Manuel Lameiras Campagnolo, Cristopher Moore
We study a restricted version of Shannon's General Purpose Analog Computer in which we only allow the machine to solve linear differential equations. This corresponds to only allowing local feedback...