Bounds on the quantum satisfibility threshold (2009)
Bravyi, Sergey, Moore, Cristopher, Russell, Alexander
Quantum k-SAT is the problem of deciding whether there is a n-qubit state which is perpendicular to a set of vectors, each of which lies in the Hilbert space of k qubits. Equivalently, the problem is...
Approximating the Permanent via Nonabelian Determinants (2009)
Moore, Cristopher, Russell, Alexander
Celebrated work of Jerrum, Sinclair, and Vigoda has established that the permanent of a {0,1} matrix can be approximated in randomized polynomial time by using a rapidly mixing Markov chain. A...
A Computational Approach to Animal Breeding (2008)
Abstract. We propose a computational model of mating strategies for controlled animal breeding programs. To the best of our knowledge, this is the first computational model of this problem. We focus...
A Computational Approach to Animal Breeding (2008)
Tanyay Berger-wolf, Cristopher Moore, Jared Saia, Cristopher Moore, Jared Saia
doi:10.1016/j.jtbi.2006.08.028 This is a PDF file of an unedited manuscript that has been accepted for publication. As a service to our customers we are providing this early version of the...
Hierarchical structure and the prediction of missing links in networks (2008)
Clauset, Aaron, Moore, Cristopher, Newman, M. E. J.
Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of science. Recent studies suggest that networks often exhibit hierarchical...
A simple constant-probability RP reduction from NP to Parity P (2008)
Moore, Cristopher, Russell, Alexander
The proof of Toda's celebrated theorem that the polynomial hierarchy is contained in $\P^{# P}$ relies on the fact that, under mild technical conditions on the complexity class $C$, we have $\exists...
Finding conjugate stabilizer subgroups of almost 3-transitive groups (2008)
Denney, Aaron, Moore, Cristopher, Russell, Alexander
We reduce a case of the hidden subgroup problem (HSP) in several families of finite groups of Lie type, such as SL_2(F_q), PSL_2(F_q), and PGL_2(F_q), to efficiently solvable HSPs in the affine group...
Introduction: Where Statistical Physics Meets Computation 1 Background (2008)
Allon G. Percus, Gabriel Istrate, Cristopher Moore
Computer science and physics have been closely linked since the birth of modern computing.
Hierarchical structure and the prediction of missing links in networks (2008)
Clauset, Aaron, Moore, Cristopher, Newman, M. E. J.
Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of science(1-3). Recent studies suggest that networks often exhibit...
Cristopher Moore, Alexander Russell
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...
On the Computational Power of Probabilistic and Quantum Branching Programs (2008)
Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, Christopher Pollett
In this paper we show that one-qubit polynomial time computations are as powerful as NC 1 circuits. More generally, we define syntactic models for quantum and stochastic branching programs of bounded...
Comment.Math.Univ.Carolinae 38,?(1997)671{687 671 Polyabelian loops and Boolean completeness (2008)
Francois Lemieux, Cristopher Moore, Denis Therien
Abstract. We consider the question of which loops are capable of expressing arbitrary Boolean functions through expressions of constants and variables. We call this property Boolean completeness. It...
Eric Allender, Michael Kearns, Sanjeev Arora, Alexander Russell, Cristopher Moore
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...
Abstract Tiling groups for Wang tiles ∗ (2008)
Cristopher Moore, Ivan Rapaport, Eric Rémila
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 define a set of...
Eric Allender, Michael Kearns, Sanjeev Arora, Alexander Russell, Cristopher Moore
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...
On the Computational Power of Probabilistic and Quantum Branching Programs (Revised Version) (2008)
Farid Ablayev, Aida Gainutdinova, Marek Karpinski, Cristopher Moore, Christopher Pollett
In this paper we show that one-qubit polynomial time computations are as powerful as NC 1 circuits. More generally, we define syntactic models for quantum and stochastic branching programs of bounded...
Abstract GENERIC QUANTUM FOURIER TRANSFORMS (2008)
The quantum Fourier transform (QFT) is the principal ingredient of most efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by...
Adaptive power topology control (APTC) is a local algorithm for constructing a one-parameter family of θ-graphs, where each node increases power until it has a neighbor in every θ sector around it....
Cristopher Moore, Mats G. Nordahl
Abstract. We show that predicting the HPP or FHP III lattice gas for finite time is equivalent to calculating the output of an arbitrary Boolean circuit, and is therefore P-complete: that is, it is...
Cristopher Moore, Timothy Boykett
Abstract. We study the algebraic conditions under which two onedimensional cellular automata can commute. We show that if either rule is permutive, i.e. one-to-one in its leftmost and rightmost...
The Physical Limits of Communication (2007)
Michael Lachmann, Cristopher Moore
It has been well-known since the pioneering work of Claude Shannon in the 1940s that a message transmitted with optimal eciency over a channel of limited bandwidth is indistinguishable from random...
Some Polyomino Tilings of the Plane (2007)
We calculate the generating functions for the number of tilings of rectangles of various widths by the right tromino, the L tetromino, and the T tetromino. This allows us to place lower bounds on the...
Upper and Lower Bounds on Continuous-Time Computation (2007)
Manuel Lameiras Campagnolo, Cristopher Moore
We consider various extensions and modifications of Shannon's General Purpose Analog Computer, which is a model of computation by differential equations in continuous time. We show that several...
Who Wins Domineering on Rectangular Boards? (2007)
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...
Internal Diffusion-Limited Aggregation: Parallel Algorithms and Complexity (2007)
Cristopher Moore, Jonathan Machta
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...
Another Way to Perform the Quantum Fourier Transform in Linear Parallel Time (2007)
. We exhibit a quantum circuit that performs the Quantum Fourier Transform on n qubits in O(n) depth. Thus, a parallel quantum computer can carry out the QFT in linear time. Griffiths and Niu have...
Upper and Lower Bounds on Continuous-Time Computation (2007)
Manuel Lameiras Campagnolo, Cristopher Moore
We consider various extensions and modifications of Shannon's General Purpose Analog Computer, which is a model of computation by differential equations in continuous time. We show that several...
Iteration, Inequalities, and Differentiability in Analog Computers (2007)
Manuel Lameiras Campagnolo, Cristopher Moore, José Félix Costa
Shannon's General Purpose Analog Computer (GPAC) is an elegant model of analog computation in continuous time. In this paper, we consider whether the set G of GPAC-computable functions is closed...
Polyabelian loops and Boolean completeness (2007)
François Lemieux, Cristopher Moore, Denis Thérien
This paper is organized as follows. Section 2 gives an introduction to the algebraic terms and concepts we will use. In Section 3 we dene the functional closure of a groupoid, and show that simple...
Queues, Stacks, and Transcendentality at the Transition to Chaos (2007)
Cristopher Moore, Porus Lakdawala
. We examine the one-humped map at the period-doubling transition to chaos, and ask whether its long-term memory is stack-like (last-in, rst-out) or queue-like (rst-in, rst-out). We show that it can...
Quantum Circuits: Fanout, Parity, and Counting (2007)
We propose definitions of QAC0, the quantum analog of the classical class AC0 of constant-depth circuits with AND and OR gates of arbitrary fan-in, and QACC0[q], where n-ary MODq gates are also...
Eric Allender, Michael Kearns, Sanjeev Arora, Alexander Russell, Cristopher Moore
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...
More Games of No Chance MSRI Publications (2007)
Cristopher Moore, David Eppstein
Abstract. 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...
Abstract. It is well-known that the question of whether a given nite 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...
Analog Computers and the Iteration Functional (2007)
Campo Gr, Manuel Lameiras Campagnolo, Manuel Lameiras Campagnolo, Cristopher Moore, Cristopher Moore
The les are stored in PDF, with the report number as lename. Alternatively, reports are available by post from the above address.
Polyabelian loops and Boolean completeness (2007)
Cristopher Moore, Denis Therien
In the preface of his book, The theory of groups ([10]), H. Zassenhaus enumerates the main elements used to understand the algebraic structure of nite groups: We are referring to the consistent...
Computational complexity in physics (2007)
There are many denitions of the word \complexity. " These fall into three main categories: Information and thermodynamic entropy, as in Shannon and Gibbs, with extensions by Crutcheld and...
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...
c Rinton Press COUNTING, FANOUT, AND THE COMPLEXITY OF QUANTUM ACC (2007)
Frederic Green, Steven Homer, Cristopher Moore, Christopher Pollett
We propose denitions of QAC
Michael Lachmann, Cristopher Moore, Ivan Rapaport
Abstract. 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...
Analog Computers and the Iteration Functional* (2007)
Manuel Lameiras Campagnolo, Manuel Lameiras Campagnolo, Cristopher Moore, Cristopher Moore, José Félix Costa, José Félix Costa
are available by post from the above address.
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 classication...
Another Way to Perform the Quantum Fourier (2007)
Transform In Linear, Cristopher Moore
We exhibit a quantum circuit that performs the Quantum Fourier Transform on n qubits in O(n) depth. Thus, a parallel quantum computer can carry out the QFT in linear time. Griffiths and Niu have...
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...
Dimitris Achlioptas, David Kempe, Aaron Clauset, Cristopher Moore
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...
Random k-SAT: two moments suffice to cross a sharp threshold (2006)
Dimitris Achlioptas, Cristopher Moore
Abstract. 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....
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...
Generating hard satisfiable formulas by hiding solutions deceptively (2005)
Haixia Jia, Cristopher Moore, Doug Strain
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 symmetric group defies strong Fourier sampling (2005)
Cristopher Moore, Alexander Russell, Leonard J. Schulman
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 (2005)
Cristopher Moore, Alexander Russell
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...
Cristopher Moore, Gabriel Istrate, Demetrios Demopoulos, Moshe Y. Vardi
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...
Journal of Statistical Mechanics: An IOP and SISSA journal Theory and Experiment (2005)
Dimitris Achlioptas, Cristopher Moore, Frank Van Bussel
Rapid mixing for lattice colourings with fewer colours
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...
How much backtracking does it take to color random graphs? Rigorous results on heavy tails (2004)
Abstract. For many backtracking search algorithms, the running time has been found experimentally to have a heavy-tailed distribution, in which it is often much greater than its median. We analyze...
The chromatic number of random regular graphs (2004)
Dimitris Achlioptas, Cristopher Moore
Abstract. 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 +...
Hiding satisfying assignments: two are better than one (2004)
Dimitris Achlioptas, Haixia Jia, Cristopher Moore
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...
Rectangles and squares recognized by two-dimensional automata (2004)
We consider sets of rectangles and squares recognized by deterministic and non-deterministic two-dimensional finite-state automata. We show that NFAs are strictly more powerful than DFAs, even for...
Rectangles and Squares Recognized By Two-Dimensional Automata (2004)
this paper, we resolve this question and show that NFAs are not closed under complement. In addition, we show that NFAs are more powerful than DFAs, even for rectangles of a single symbol. We note...
The Chromatic Number of Random Regular Graphs (2004)
Dimitris Achlioptas, Cristopher Moore
Given any integer d 1, 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.
Hiding Satisfying Assignments: Two are Better than One (2004)
Dimitris Achlioptas, Haixia Jia, Cristopher Moore
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...
The hidden subgroup problem in affine groups: Basis selection in Fourier sampling (2004)
Cristopher Moore, Daniel Rockmore, Er Russell, Leonard J
Abstract. 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...
Building the components for a biomolecular (2004)
Clint Morgan, Darko Stefanovic, Cristopher Moore, Milan N. Stojanovic
computer
The chromatic number of random regular graphs (2004)
Dimitris Achlioptas, Cristopher Moore
Abstract. 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,ork +2. 1
Building the components for a biomolecular (2004)
Clint Morgan, Darko Stefanovic, Cristopher Moore, Milan N. Stojanovic
computer
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...
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...
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;...
One-dimensional Peg Solitaire, and Duotaire (2003)
Abstract. 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...
One-dimensional Peg Solitaire, and Duotaire (2003)
Abstract. 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...
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. Furthermore, this implies that the uniform distribution on the set of such colourings has strong spatial mixing. 4 and...
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...
Paul Beame, David Mitchell, Joseph Culberson, 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...
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...
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...
On the 2-colorability of Random Hypergraphs (2002)
Dimitris Achlioptas, Cristopher Moore
Abstract. 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...
Almost all graphs with average degree 4 are 3-colorable (2002)
Dimitris Achlioptas, Cristopher Moore
We analyze a randomized version of the Brelaz heuristic on sparse random graphs. We prove that almost all graphs with average degree d 4.03, i.e. G(n, p = d/n), are 3-colorable and that a constant...
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...
An analog characterization of the Grzegorczyk hierarchy (2002)
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 dierential equations. This corresponds to only allowing local...
Quantum walks on the hypercube (2002)
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...
Almost all graphs with average degree 4 are 3-colorable (2002)
We analyze a randomized version of the Brelaz heuristic on sparse random graphs. We prove that almost all graphs with average degree dp4:03; i.e., Gðn; p d=nÞ; are 3-colorable and that a constant...
On the 2-colorability of Random Hypergraphs (2002)
Dimitris Achlioptas, Cristopher Moore
Abstract. A2-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...
A Note on the Representational Incompatibility (2002)
Of Function Approximation, 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...
Almost all graphs with average degree 4 are 3-colorable (2002)
Dimitris Achlioptas, Cristopher Moore
The technique of approximating the mean path of Markov chains by differential equations has proved to be a useful tool in analyzing the performance of heuristics on random graph instances. However,...
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.
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...
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
Determining bounds for the random k-SAT threshold has been an active area of research in recent years [1, 3]. Yet, in spite of signicant eorts,
New Results on Alternating and Non-Deterministic Two-Dimensional Finite-State Automata (2001)
. We resolve several long-standing open questions regarding the power of various types of nite-state automata to recognize \picture languages," i.e. sets of two-dimensional arrays of symbols. We...
The phase transition in 1-in-k SAT and NAE 3-SAT (2001)
Dimitris Achlioptas, Arthur Chtcherba, Gabriel Istrate, Cristopher Moore
Determining bounds for the random k-SAT thresh-old has been an active area of research in recent years [1, 3]. Yet, in spite of significant efforts, nei-ther a tight analysis nor the structural...
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...
An n-dimensional generalization of the rhombus tiling (2001)
Joakim Linde, Cristopher Moore, Mats G. Nordahl
Several classic tilings, including rhombuses and dominoes, possess height functions which allow us to 1) prove ergodicity and polynomial mixing times for Markov chains based on local moves, 2) use...
Upper and lower bounds on continuous-time computation (2001)
Manuel Lameiras Campagnolo, Cristopher Moore
Abstract. We consider various extensions and modifications of Shannon’s General Purpose Analog Computer, which is a model of computation by differential equations in continuous time. We show that...
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...
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...
Who wins domineering on rectangular boards (2000)
Michael Lachmann, Cristopher Moore, Ivan Rapaport
Abstract. 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...
An analog characterization of the subrecursive functions (2000)
Manuel Lameiras Campagnolo, Cristopher Moore, Joséfélix Costa
Abstract. 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...
Ribbon tile invariants from signed area (2000)
Abstract. 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...
Ribbon tile invariants from signed area (2000)
Abstract. 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...
We study the four-state antiferromagnetic Potts model on the triangular lattice. We show that the model has six types of defects which diuse and annihilate according to certain conservation laws...
Quantum automata and quantum grammars (2000)
Abstract. To study quantum computation, it might be helpful to generalize structures from language and automata theory to the quantum case. To that end, we propose quantum versions of nite-state and...
Ribbon tile invariants from signed area (2000)
Abstract. 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...
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...
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...
An Analog Characterization of the Subrecursive Functions (2000)
Manuel Lameiras Campagnolo, Cristopher Moore, José Félix Costa
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...
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...
Equation Satisfiability and Program Satisfiability for Finite Monoids (2000)
Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis Thérien
We study the computational complexity of solving equations and of determining the satisfiability of programs over a fixed finite monoid. We partially answer an open problem of [4] by exhibiting...
Epidemics and percolation in small-world networks (1999)
Moore, Cristopher, Newman, M. E. J.
We study some simple models of disease transmission on small-world networks, in which either the probability of infection by a disease or the probability of its transmission is varied, or both. The...
Internal Diffusion-Limited Aggregation: Parallel Algorithms and Complexity (1999)
Moore, Cristopher, Machta, Jonathan
The computational complexity of internal diffusion-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...
The physical limits of communication (1999)
Lachmann, Michael, Newman, M. E. J., Moore, Cristopher
It has been well-known since the pioneering work of Claude Shannon in the 1940s that a message transmitted with optimal efficiency over a channel of limited bandwidth is indistinguishable from random...
Some Polyomino Tilings of the Plane (1999)
We calculate the generating functions for the number of tilings of rectangles of various widths by the right tromino, the $L$ tetromino, and the $T$ tetromino. This allows us to place lower bounds on...
Quantum Circuits: Fanout, Parity, and Counting (1999)
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^0[q], where n-ary Mod-q gates are also...
Moore, Cristopher, Newman, M. E. J.
We study the four-state antiferromagnetic Potts model on the triangular lattice. We show that the model has six types of defects which diffuse and annihilate according to certain conservation laws...
Moore, Cristopher, Nordahl, Mats G., Minar, Nelson, Shalizi, Cosma
We study the dynamics of topological defects in the triangular Ising antiferromagnet, a related model on the square lattice equivalent to the six-vertex ice model, and the three-state...
Glassy Dynamics in an Exactly Solvable Spin Model (1999)
We introduce a simple two-dimensional spin model with short-range interactions which shows glassy behavior despite a Hamiltonian which is completely homogeneous and possesses no randomness. We solve...
Closed-form Analytic Maps in One and Two Dimensions Can Simulate Universal Turing Machines (1999)
Pascal Koiran, Cristopher Moore
We show closed-form analytic functions consisting of a nite number of trigonometric terms can simulate Turing machines, with exponential slowdown in one dimension or in real time in two or more.
Queues, Stacks, and Transcendentality at the Transition to Chaos (1998)
Moore, Cristopher, Lakdawala, Porus
We examine the one-humped map at the period-doubling transition to chaos, and ask whether its long-term memory is stack-like (last-in, first-out) or queue-like (first-in, first-out). We show that it...
The Computational Complexity of Sandpiles (1998)
Moore, Cristopher, Nilsson, Martin
Given an initial distribution of sand in an Abelian sandpile, what final state does it relax to after all possible avalanches have taken place? In d >= 3, we show that this problem is P-complete, so...
Parallel Quantum Computation and Quantum Codes (1998)
Moore, Cristopher, Nilsson, Martin
We propose a definition of QNC, the quantum analog of the efficient parallel class NC. We exhibit several useful gadgets and prove that various classes of circuits can be parallelized to logarithmic...
Some Notes on Parallel Quantum Computation (1998)
Moore, Cristopher, Nilsson, Martin
We exhibit some simple gadgets useful in designing shallow parallel circuits for quantum algorithms. We prove that any quantum circuit composed entirely of controlled-not gates or of diagonal gates...
Complexity of Two-Dimensional Patterns (1998)
Lindgren, Kristian, Moore, Cristopher, Nordahl, Mats G.
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...
Another Way to Perform the Quantum Fourier Transform in Linear Parallel Time (1998)
This paper has been withdrawn.
Dynamical recognizers: Real-time language recognition by analog computers (1998)
We consider a model of analog computation which can recognize various languages in real time. We encode an input word as a point in R d by composing iterated maps, and then apply inequalities to the...
Some Notes on Parallel Quantum Computation (1998)
Cristopher Moore, Martin Nilsson
. We exhibit some simple gadgets useful in designing shallow parallel circuits for quantum algorithms. We prove that any quantum circuit composed entirely of controlled-not gates or of diagonal gates...
Dynamical Recognizers: Real-time Language Recognition by Analog Computers (1998)
We consider a model of analog computation which can recognize various languages in real time. We encode an input word as a point in R d by composing iterated maps, and then apply inequalities to the...
Glassy dynamics and aging in an exactly solvable spin model (1997)
Newman, M. E. J., Moore, Cristopher
We introduce a simple two-dimensional spin model with short-range interactions which shows glassy behavior despite a Hamiltonian which is completely homogeneous and possesses no randomness. We solve...
Quantum Automata and Quantum Grammars (1997)
Moore, Cristopher, Crutchfield, James P.
To study quantum computation, it might be helpful to generalize structures from language and automata theory to the quantum case. To that end, we propose quantum versions of finite-state and...
Lattice Gas Prediction is P-complete (1997)
Moore, Cristopher, Nordahl, Mats G.
We show that predicting the HPP or FHP III lattice gas for finite time is equivalent to calculating the output of an arbitrary Boolean circuit, and is therefore P-complete: that is, it is just as...
Quasi-Linear Cellular Automata (1997)
Simulating a cellular automaton (CA) for t time-steps into the future requires t^2 serial computation steps or t parallel ones. However, certain CAs based on an Abelian group, such as addition mod 2,...
Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness (1997)
We study cellular automata where the state at each site is decided by a majority vote of the sites in its neighborhood. These are equivalent, for a restricted set of initial conditions, to non-zero...
Predicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones (1997)
We show that a wide variety of non-linear cellular automata (CAs) can be decomposed into a quasidirect product of linear ones. These CAs can be predicted by parallel circuits of depth O(log^2 t)...
Majority-vote cellular automata, Ising dynamics, and P-completeness (1997)
We study cellular automata where the state at each site is decided by a majority vote of the sites in its neighborhood. These are equivalent, for a restricted set of initial conditions, to non-zero...
Majority-Vote Cellular Automata, Ising Dynamics, and (1997)
Completeness Cristopher, Cristopher Moore
We study cellular automata where the state at each site is decided by a majority vote of the sites in its neighborhood. These are equivalent, for a restricted set of initial conditions, to non-zero...
Quasi-Linear Cellular Automata (1997)
Simulating a cellular automaton (CA) for t time-steps into the future requires t 2 serial computation steps or t parallel ones. However, certain CAs based on an Abelian group, such as addition mod 2,...
Complexity of Two-Dimensional Patterns (1997)
Kristian Lindgren, Cristopher Moore, Mats Nordahl
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...
Predicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones (1997)
We show that a wide variety of non-linear cellular automata (CAs) can be decomposed into a quasidirect product of linear ones. These CAs can be predicted by parallel circuits of depth O(log 2 t)...
Life Without Death is P-complete (1997)
David Griffeath, Cristopher Moore
. We show that if a cellular automaton in two or more dimensions supports growing "ladders" which can turn or block each other, then it can express arbitrary Boolean circuits. Then the...
Predicting Lattice Gases is P-complete (1997)
Cristopher Moore, Mats G. Nordahl
. We show that predicting the HPP or FHP III lattice gas for finite time is equivalent to calculating the output of an arbitrary Boolean circuit, and is therefore P-complete: that is, it is just as...
Quasi-Linear Cellular Automata (1997)
Cristopher Moore Santa, Cristopher Moore
Simulating a cellular automaton (CA) for t time-steps into the future requires t serial computation steps or t parallel ones. However, certain CAs based on an Abelian group, such as addition mod 2,...
Algebraic Properties of the Block Transformation on Cellular Automata (1996)
Cristopher Moore, Arthur A. Drisko
By grouping several sites together into one, a cellular automaton can be transformed into another with more states and a smaller neighborhood; if the neighborhood has just two sites, we can think of...
Closed-form Analytic Maps in One and Two Dimensions Can Simulate Turing Machines (1996)
Pascal Koiran, Cristopher Moore
We show closed-form analytic functions consisting of a finite number of trigonometric terms can simulate Turing machines, with exponential slowdown in one dimension or in real time in two or more. 1...
Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness (1996)
We study cellular automata where the state at each site is decided by a majority vote of the sites in its neighborhood. These are equivalent, for a restricted set of initial conditions, to non-zero...
Non-Abelian Cellular Automata (1995)
We show that a wide variety of non-linear cellular automata can be written as a semidirect product of linear ones, and that these CAs can be predicted in parallel time O(log t). This class includes...
Recursion Theory on the Reals and Continuous-time Computation (1995)
We define a class of recursive functions on the reals analogous to the classical recursive functions on the natural numbers, corresponding to a conceptual analog computer that operates in continuous...
Almost All Graphs of Degree 4 are 3-colorable
Dimitris Achlioptas, Cristopher Moore
The technique of approximating the mean path of Markov chains by differential equations has proved to be a useful tool in analyzing the performance of heuristics on random graph instances. However,...
Cristopher Moore, Ivan Rapaport, Eric Rémila
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 define a set of...
Quantum Walks on the Hypercube
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...
New Results on Alternating and Non-Deterministic Two-Dimensional Finite-State Automata
We resolve several long-standing open questions regarding the power of various types of finite-state automata to recognize "picture languages," i.e. sets of two-dimensional arrays of symbols. We show...
One-Dimensional Peg Solitaire, and Duotaire
Cristopher Moore, David Eppstein
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...
Rectangles and Squares Recognized by Two-Dimensional Automata
We consider sets of rectangles and squares recognized by deterministic and non-deterministic two-dimensional finite-state automata. We show that NFAs are strictly more powerful than DFAs, even for...
Upper and Lower Bounds on Continuous-Time Computation
Manuel Campagnolo, Cristopher Moore
We consider various extensions and modifications of Shannon's General Purpose Analog Computer, which is a model of computation by differential equations in continuous time. We show that several...
Equation Satisfiability and Program Satisfiablity for Finite Monoids
David Bix Barrington, Pierre McKenzie, Cristopher Moore, Pascal Tesson, Denis ThŽrien
We study the computational complexity of solving equations and of determining the satisfiability of programs over a fixed finite monoid. We partially answer an open problem of [4] by exhibiting...
Who Wins Domineering on Rectangular Boards?
Michael Lachmann, Cristopher Moore, Ivan Rapaport
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...
Hard Tiling Problems with Simple Tiles
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...
Exact Solution of Site and Bond Percolation on Small-World Networks
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
Manuel Lameiras Campagnolo, Cristopher Moore, José Félix Costa
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...
Epidemics and Percolation in Small-World Networks
We study some simple models of disease transmission on small-world networks, in which either the probability of infection by a disease or the probability of its transmission is varied, or both. The...
The Physical Limits of Communication
Michael Lachmann, Cristopher Moore
It has been well-known since the pioneering work of Claude Shannon in the 1940s that a message transmitted with optimal efficiency over a channel of limited bandwidth is indistinguishable from random...
Iteration, Inequalities, and Differentiability in Analog Computers
Manuel Lameiras Campagnolo, Cristopher Moore, José Félix Costa
Shannon's General Purpose Analog Computer (GPAC) is an elegant model of analog computation in continuous time. In this paper, we consider whether the set G of GPAC-computable functions is closed...
Some Polyomino Tilings of the Plane
We calculate the generating functions for the number of tilings of rectangles of various widths by the right tromino, the L tetromino, and the T tetromino. This allows us to place lower bounds on the...
Quantum Circuits: Fanout, Parity, and Counting
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^0[q], where n-ary Mod-q gates are also...
We study the four-state antiferromagnetic Potts model on the triangular lattice. We show that the model has six types of defects which diffuse and annihilate according to certain conservation laws...
Entropic Coulomb Forces in Ising and Potts Antiferromagnets and Ice Models
Cristopher Moore, Mats G. Nordahl, Nelson Minar, Cosma Shalizi
We study topological defects in the triangular Ising antiferromagnet, a related model on the square lattice equivalent to the six-vertex ice model, and the three-state antiferromagnetic Potts model...
Queues, Stacks, and Transcendentality at the Transition to Chaos
Cristopher Moore, Porus Lakdawala
We examine the one-humped map at the period-doubling transition to chaos, and ask whether its long-term memory is stack-like (last-in, first-out) or queue-like (first-in, first-out). We show that it...
The Computational Complexity of Sandpiles
Cristopher Moore, Martin Nilsson
Given an initial distribution of sand in an Abelian sandpile, what final state does it relax to after all possible avalanches have taken place? In d >= 3*, we show that this problem is P-complete, so...
Parallel Quantum Computation and Quantum Codes
Cristopher Moore, Martin Nilsson
We propose a definition of QNC, the quantum analog of the efficient parallel class NC. We exhibit several useful gadgets and prove that various classes of circuits can be parallelized to logarithmic...
Some Notes on Parallel Quantum Computation
Cristopher Moore, Martin Nilsson
We exhibit some simple gadgets useful in designing shallow parallel circuits for quantum algorithms. We prove that any quantum circuit composed entirely of controlled-not gates or of diagonal gates...
Performing the Quantum Fourier Transform in Linear Parallel Time
We exhibit a quantum circuit that performs the Quantum Fourier Transform on $n$ qubits in $ (n)$ depth. Thus, a parallel quantum computer can carry out the QFT in linear time. We conjecture that this...
Cristopher Moore, Timothy Boykett
We study the algebraic conditions under which two cellular automata can commute. We show that if either rule is permutive, i.e., one-to-one on its leftmost and rightmost inputs, then the other rule...
Glassy Behavior in an Exactly Solvable Spin Model
We introduce a simple spin model which shows glassy behavior at low temperatures, despite a Hamiltonian which is completely homogeneous and possesses no randomness; ergodicity breaking in this model...
Quantum Automata and Quantum Grammars
Cristopher Moore, James P. Crutchfield
To study quantum computation, it might be helpful to generalize structures from language and automata theory to the quantum case. To that end, we propose quantum versions of finite-state and...
Life Without Death is P-Complete
David Griffeath, Cristopher Moore
We show that if a cellular automaton in two or more dimensions supports growing "ladders" which can turn or block each other, then it can express arbitrary Boolean circuits. Then the problem of...
Lattice Gas Prediction is P-Complete
Kristian Lindgren, Cristopher Moore, Mats G. Nordahl
We show that predicting the HPP or FHP III lattice gas for finite time is equivalent to calculating the output of an arbitrary Boolean circuit, and is therefore P-complete: that is, it is just as...
Complexity of Two-Dimensional Patterns
Kristian Lindgren, Cristopher Moore, Mats Nordahl
In dynamical systems such as cellular automata and iterated maps, it is often useful to look at a {\it language} or set of symbol sequences produced by the system. There are well-established...
Circuits and Expressions with Non-Associative Gates
Joshua Berman, Arthur Drisko, Francois Lemieux, Cristopher Moore, Denis Therien
We consider circuits and expressions whose gates carry out multiplication in a non-associative algebra such as a quasigroup or loop. We define a class we call the polyabelian algebras, formed by...
Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness
We study cellular automata where the state at each site is decided by a majority vote of the sites in its neighborhood. These are equivalent, for a restricted set of initial conditions, to non-zero...
Closed-form Analytic Maps in One and Two Dimensions Can Simulate Turing Machines
Pascal Koiran, Cristopher Moore
We show closed-form analytic functions consisting of a finite number of trigonometric terms can simulate Turing machines, with exponential slowdown in one dimension or in real time in two or more. ...
Dynamical Recognizers: Real-Time Language Recognition by Analog Computers
Following Pollack, we consider a model of analog computer which can recognize various languages in real time. We encode an input word as a point in R[super d] by composing iterated maps, and then...
We show that a wide variety of nonlinear cellular automata can be written as a semidirect product of linear ones, and that these CAs can be predicted in parallel time [cal O](log[super 2] t). This...
Algebraic Properties of the Block Transformation on Cellular Automata
Cristopher Moore, Arthur A. Drisko
By grouping several sites together into one, a cellular automaton can be transformed into another with more states and a smaller neighborhood; if the neighborhood has just two sites, we can think of...
Recursion Theory on the Reals and Continuous-Time Computation
We define a case of recursive functions on the reals analogous to the classical recursive functions on the natural numbers, corresponding to a conceptual analog computer that operates in continuous...
Quasi-Linear Cellular Automata
Simulating a cellular automata (CA) for t time-steps into the future requires t[super 2] serial computation steps or t parallel ones. However, certain CAs based on an Abelian group, such as addition...
Circuits and Expressions with Non-Associative Gates (Extended Abstract)
Joshua Berman, Non-associative Gates, Arthur Drisko, Cristopher Moore, Denis Thérien, Francois Lemieux
) ? Joshua Berman 1 , Arthur Drisko 2 , Francois Lemieux 3 , Cristopher Moore 4 , and Denis Th'erien 3 1 State University of New York at Binghamton 2 National Security Agency 3 McGill University...
Quantum Automata and Quantum Grammars
Cristopher Moore, James P. Crutchfield
. To study quantum computation, it might be helpful to generalize structures from language and automata theory to the quantum case. To that end, we propose quantum versions of finite-state and...
Algebraic Properties of the Block Transformation on Cellular Automata
By grouping 2r sites together into one, a cellular automaton with radius r can be transformed into one with a two-site neighborhood, which can be thought of as a binary algebra. We show that if this...