Publications (128)
Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts
David Kempe, Mahyar Salek, Cristopher Moore
Lower Bounds on the Critical Density in the Hard Disk Model via Optimized Metrics
Thomas P. Hayes, Cristopher Moore
Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively
Haixia Jia, Cristopher Moore, Doug Strain
The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks
Hang Dinh, Cristopher Moore, Alexander Russell
Spatial Mixing for Independent Sets in Poisson Random Trees
Varsha Dani, Thomas P. Hayes, Cristopher Moore
Information-theoretic thresholds for community detection in sparse networks
Jess Banks, Cristopher Moore
Approximate Representations and Approximate Homomorphisms
Cristopher Moore, Alexander Russell
Continuum Percolation Thresholds in Two Dimensions
Stephan Mertens, Cristopher Moore
Epidemics and percolation in small-world networks
Cristopher Moore, M. E. J. Newman
Transdisciplinary electric power grid science
Charles D. Brummitt, Paul D. H. Hines, Ian Dobson +2
Bounds on the quantum satisfiability threshold
Sergey Bravyi, Cristopher Moore, Alexander Russell
Stability analysis of financial contagion due to overlapping portfolios
Fabio Caccioli, Munik Shrestha, Cristopher Moore +1
Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman Theorem
Sixia Chen, Cristopher Moore, Alexander Russell
A message-passing approach for threshold models of behavior in networks
Munik Shrestha, Cristopher Moore
The physical limits of communication
Michael Lachmann, M. E. J. Newman, Cristopher Moore
Quantum Walks on the Hypercube
Cristopher Moore, Alexander Russell
A classical one-way function to confound quantum adversaries
Cristopher Moore, Alexander Russell, Umesh Vazirani
The rigidity transition in random graphs
Shiva Prasad Kasiviswanathan, Cristopher Moore, Louis Theran
Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
Aurelien Decelle, Florent Krzakala, Cristopher Moore +1
Scalable detection of statistically significant communities and hierarchies, using message-passing for modularity
Pan Zhang, Cristopher Moore
Community detection, link prediction, and layer interdependence in multilayer networks
Caterina De Bacco, Eleanor A. Power, Daniel B. Larremore +1
Quantum Algorithms for Simon's Problem Over General Groups
Gorjan Alagic, Cristopher Moore, Alexander Russell
Why Mapping the Internet is Hard
Aaron Clauset, Cristopher Moore
For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets
Cristopher Moore, Alexander Russell
Hard Tiling Problems with Simple Tiles
Cristopher Moore, John Michael Robson
Quantum Circuits: Fanout, Parity, and Counting
Cristopher Moore
Phase transitions in semisupervised clustering of sparse networks
Pan Zhang, Cristopher Moore, Lenka Zdeborová
Accurate and scalable social recommendation using mixed-membership stochastic block models
Antonia Godoy-Lorite, Roger Guimera, Cristopher Moore +1
Circuit partitions and #P-complete products of inner products
Cristopher Moore, Alexander Russell
Matrix multiplication algorithms from group orbits
Joshua A. Grochow, Cristopher Moore
Untangling the roles of parasites in food webs with generative network models
Abigail Z. Jacobs, Jennifer A. Dunne, Cristopher Moore +1
Lecture Notes on Automata, Languages, and Grammars
Cristopher Moore
Codes, Lower Bounds, and Phase Transitions in the Symmetric Rendezvous Problem
Varsha Dani, Thomas P. Hayes, Cristopher Moore +1
Optimal epsilon-biased sets with just a little randomness
Cristopher Moore, Alexander Russell
Active Learning for Node Classification in Assortative and Disassortative Networks
Cristopher Moore, Xiaoran Yan, Yaojia Zhu +2
Vortex Dynamics and Entropic Coulomb Forces in Ising and Potts Antiferromagnets and Ice Models
Cristopher Moore, Mats G. Nordahl, Nelson Minar +1
Counting, Fanout, and the Complexity of Quantum ACC
Frederic Green, Steven Homer, Cristopher Moore +1
From spin glasses to hard satisfiable formulas
Haixia Jia, Cristopher Moore, Bart Selman
A simple constant-probability RP reduction from NP to Parity P
Cristopher Moore, Alexander Russell
Tight Results on Multiregister Fourier Sampling: Quantum Measurements for Graph Isomorphism Require Entanglement
Cristopher Moore, Alexander Russell
Internal Diffusion-Limited Aggregation: Parallel Algorithms and Complexity
Cristopher Moore, Jonathan Machta
Lattice Gas Prediction is P-complete
Cristopher Moore, Mats G. Nordahl
How Do Networks Become Navigable?
Aaron Clauset, Cristopher Moore
Detectability thresholds and optimal algorithms for community structure in dynamic networks
Amir Ghasemian, Pan Zhang, Aaron Clauset +2
One-Dimensional Peg Solitaire, and Duotaire
Cristopher Moore, David Eppstein
A message-passing approach for recurrent-state epidemic models on networks
Munik Shrestha, Samuel V. Scarpino, Cristopher Moore
Who Wins Domineering on Rectangular Boards?
Michael Lachmann, Cristopher Moore, Ivan Rapaport
Quantum Automata and Quantum Grammars
Cristopher Moore, James P. Crutchfield
On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs
Dimitris Achlioptas, Aaron Clauset, David Kempe +1
The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness
Cristopher Moore
Exact solution of site and bond percolation on small-world networks
Cristopher Moore, M. E. J. Newman
Structural Inference of Hierarchies in Networks
Aaron Clauset, Cristopher Moore, M. E. J. Newman
On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
Cristopher Moore, Alexander Russell
Parallel Complexity of Random Boolean Circuits
Jon Machta, Simon DeDeo, Stephan Mertens +1
The Asymptotic Order of the k-SAT Threshold
Dimitris Achlioptas, Cristopher Moore
Scalable Text and Link Analysis with Mixed-Topic Link Models
Yaojia Zhu, Xiaoran Yan, Lise Getoor +1
Percolation Thresholds in Hyperbolic Lattices
Stephan Mertens, Cristopher Moore
The Chromatic Number of Random Regular Graphs
Dimitris Achlioptas, Cristopher Moore
Quantum and Stochastic Branching Programs of Bounded Width
Farid Ablayev, Cristopher Moore, Chris Pollett
On the impossibility of a quantum sieve algorithm for graph isomorphism: unconditional results
Cristopher Moore, Alexander Russell, Piotr Sniady
The Symmetric Group Defies Strong Fourier Sampling: Part I
Cristopher Moore, Alexander Russell, Leonard J. Schulman
Generic Quantum Fourier Transforms
Cristopher Moore, Daniel Rockmore, Alexander Russell
Quasi-Linear Cellular Automata
Cristopher Moore
Phase transition in the detection of modules in sparse networks
Aurelien Decelle, Florent Krzakala, Cristopher Moore +1
Explicit Multiregister Measurements for Hidden Subgroup Problems
Cristopher Moore, Alexander Russell
The power of choice in network growth
Raissa M. D'Souza, Paul L. Krapivsky, Cristopher Moore
Queues, Stacks, and Transcendentality at the Transition to Chaos
Cristopher Moore, Porus Lakdawala
On the universal structure of human lexical semantics
Hyejin Youn, Logan Sutton, Eric Smith +5
Active Learning for Hidden Attributes in Networks
Xiaoran Yan, Yaojia Zhu, Jean-Baptiste Rouquier +1
The Hidden Subgroup Problem in Affine Groups: Basis Selection in Fourier Sampling
Cristopher Moore, Daniel Rockmore, Alexander Russell +1
Height representation, critical exponents, and ergodicity in the four-state triangular Potts antiferromagnet
Cristopher Moore, M. E. J. Newman
Topological phase transition in a network model with preferential attachment and node removal
Heiko Bauke, Cristopher Moore, Jean-Baptiste Rouquier +1
Automatic Filters for the Detection of Coherent Structure in Spatiotemporal Systems
Cosma Rohilla Shalizi, Robert Haslinger, Jean-Baptiste Rouquier +2
Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
Jess Banks, Cristopher Moore, Nicolas Verzelen +2
How close can we come to a parity function when there isn't one?
Cristopher Moore, Alexander Russell
A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT Formulas
Cristopher Moore, Gabriel Istrate, Demetrios Demopoulos +1
Percolation Thresholds and Fisher Exponents in Hypercubic Lattices
Stephan Mertens, Cristopher Moore
Group representations that resist random sampling
Shachar Lovett, Cristopher Moore, Alexander Russell
The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts
Cristopher Moore, Daniel Rockmore, Alexander Russell +1
Series Expansion of the Percolation Threshold on Hypercubic Lattices
Stephan Mertens, Cristopher Moore
Glassy dynamics and aging in an exactly solvable spin model
M. E. J. Newman, Cristopher Moore
Quantum Measurements for Graph Isomorphism Require Entanglement: Tight Results on Multiregister Fourier Sampling (Withdrawn)
Cristopher Moore, Alexander Russell
Oriented and Degree-generated Block Models: Generating and Inferring Communities with Inhomogeneous Degree Distributions
Yaojia Zhu, Xiaoran Yan, Cristopher Moore
One-Dimensional Peg Solitaire
Cristopher Moore, David Eppstein
Exact solutions for models of evolving networks with addition and deletion of nodes
Cristopher Moore, Gourab Ghoshal, M. E. J. Newman
Traceroute sampling makes random graphs appear to have power law degree distributions
Aaron Clauset, Cristopher Moore
Finding community structure in very large networks
Aaron Clauset, M. E. J. Newman, Cristopher Moore
Approximating the Permanent via Nonabelian Determinants
Cristopher Moore, Alexander Russell
Computational Complexity in Physics
Cristopher Moore
Some Polyomino Tilings of the Plane
Cristopher Moore
Graph Isomorphism and Circuit Size
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek +2
Finding conjugate stabilizer subgroups in PSL(2; q) and related groups
Aaron Denney, Cristopher Moore, Alexander Russell
Independent sets in random graphs from the weighted second moment method
Varsha Dani, Cristopher Moore
Minimum Circuit Size, Graph Isomorphism, and Related Problems
Eric Allender, Joshua A. Grochow, Dieter van Melkebeek +2
Heat and Noise on Cubes and Spheres: The Sensitivity of Randomly Rotated Polynomial Threshold Functions
Cristopher Moore, Alexander Russell
Regarding a Representation-Theoretic Conjecture of Wigderson
Cristopher Moore, Alexander Russell
Complexity of Two-Dimensional Patterns
Kristian Lindgren, Cristopher Moore, Mats G. Nordahl
Predicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones
Cristopher Moore
Designing Strassen's algorithm
Joshua A. Grochow, Cristopher Moore
Information-theoretic thresholds for community detection in sparse networks
Jess Banks, Cristopher Moore, Joe Neeman +1