Publications
Publications are arranged by topic:
Epidemics and Percolation
Algorithms and Phase Transitions in Statistical Inference (other than community detection in networks)
Social and Biological Networks, MessagePassing Algorithms, Community Detection, and the Internet
Quantum Computation, the Hidden Subgroup Problem, Representation Theory, Quantum Walks, Quantum Circuits, and Pseudorandomness
Phase Transitions in NPComplete Problems, Random Structures, and Constructing Hard Instances
Statistical Physics, Markov Chains, and Glassy Systems
Braids in the nBody Problem
Computational Complexity of Prediction and Simulation in Statistical Physics and Cellular Automata
Parallel Complexity, Algebraic Circuits, Monoids, Quasigroups, and Loops
Tilings and Polyominoes
Combinatorial Games
TwoDimensional Languages, or "Picture Languages"
Analog Computation, Recurrent Neural Networks, and Dynamical Systems
Proof of Stake Blockchains
Miscellaneous
EPIDEMICS AND PERCOLATION
ALGORITHMS AND PHASE TRANSITIONS IN STATISTICAL INFERENCE (other than community detection)
 Belief propagation for permutations, rankings, and partial orders (with George Cantwell). Physical Review E 105, L052303 (2022).
 Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs
(with Afonso S. Bandeira, Jess Banks, Dmitriy Kunisky, and Alexander S. Wein). Proc. COLT 2021.

The Planted Matching Problem: Phase Transitions and Exact Results
(with Mehrdad Moharrami and Jiaming Xu).
Annals of Applied Probability 31(6): 26632720 (2021).

The Kikuchi Hierarchy and Tensor PCA
(with Alex Wein and Ahmed El Alaoui)
Proc. FOCS 2019.

Informationtheoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization
(with Jess Banks, Roman Vershynin, Nicolas Verzelen, and Jiaming Xu) Proc. ISIT 2017.
SOCIAL AND BIOLOGICAL NETWORKS, MESSAGEPASSING ALGORITHMS, COMMUNITY DETECTION, AND THE INTERNET

The Lovasz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
(with Jess Banks and Robert Kleinberg)
SIAM J. Computing 48(3) 10981119 (2019). Conference version in Proc. RANDOM '17, 128.

A physical model for efficient ranking in networks
(with Caterina De Bacco and Daniel Larremore)
Science Advances 4 (7) 2018.

The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness Bulletin of the EATCS, 121 (2017).

Community detection, link prediction, and layer interdependence in multilayer networks
(with Caterina De Bacco, Eleanor A. Power, and Daniel B. Larremore)
Phys. Rev. E 95, 042317 (2017).

Random graph models for dynamic networks
(with Xiao Zhang and Mark Newman)
European Physical Journal B, 90:200 (2017).

Accurate and scalable social recommendation using mixedmembership stochastic block models
(with Antonia GodoyLorite, Roger Guimera, and Marta SalesPardo) Proc. National Academy of Sciences 113 (50) 1420714212 (2016).

Informationtheoretic thresholds for community detection in sparse networks
(with Jess Banks, Joe Neeman, and Praneeth Netrapalli) Proc. COLT 2016, 383416.

Detectability thresholds and optimal algorithms for community structure in dynamic networks
(with Amir Ghasemian, Pan Zhang, Aaron Clauset, and Leto Peel)
Physical Review X 6, 031005 (2016).

Community detection in networks with unequal groups
(with Pan Zhang and Mark Newman)
Physical Review E 93 012303 (2016).

Untangling the roles of parasites in food webs with generative network models
(with Abigail Z. Jacobs, Jennifer A. Dunne, and Aaron Clauset) Preprint, 2015.

Scalable detection of statistically significant communities and hierarchies: messagepassing for modularity
(with Pan Zhang) Proc. National Academy of Sciences 111 (51) 1814418149 (2014).

Phase transitions in semisupervised clustering of sparse networks
(with Pan Zhang and Lenka Zdeborova) Physical Review E 90 052802 (2014).

Phase Transitions in Community Detection: A Solvable Toy Model
(with Greg Ver Steeg, Aram Galstyan, and Armen E. Allahverdyan)
Europhysics Letters 106 48004 (2014).

Model Selection for Degreecorrected Block Models
(with Xiaoran Yan, Cosma Shalizi, Jacob Jensen, Florent Krzakala, Lenka Zdeborova, Pan Zhang, and Yaojia Zhu) J. Stat. Mech. 5 P05007 (2014).

Oriented and Degreegenerated Block Models: Generating and Inferring Communities with Inhomogeneous Degree Distributions
(with Yaojia Zhu and Xiaoran Yan)
J. Complex Networks 2(1) 118 (2014).

Spectral redemption: clustering sparse networks
(with Florent Krzakala, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborova, and Pan Zhang) Proc. National Academy of Sciences 110 (52) 2093520940 (2013).

Scalable Text and Link Analysis with MixedTopic Link Models
(with Yaojia Zhu, Xiaoran Yan, and Lise Getoor)
Proc. KDD 2013.

Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
(with A. Decelle, F. Krzakala, and L. Zdeborova)
Physical Review E 84 (2011) 066106.
 Topological phase transition in a network model with preferential attachment and node removal.
(with H. Bauke, J.B. Rouquier, and D. Sherrington)
European Physical Journal B 83 (2011) 519524.

Inference and Phase Transitions in the Detection of Modules in Sparse Networks
(with A. Decelle, F. Krzakala, and L. Zdeborova) Physical Review Letters 107, 065701 (2011).

Active learning for node classification in assortative and disassortative networks (with X. Yan, Y. Zhu, J.B. Rouquier, and T. Lane) Proc. KDD 2011.
(KDD version here)

Hierarchical structure and the prediction of missing links in networks
(with Aaron Clauset and Mark Newman) Nature 454 98101 (2008).
 The Power of Choice in Network Growth (with Raissa D'Souza and Paul Krapivsky) European Journal of Physics B 59 535543 (2007).
 Exact solutions for models of evolving networks with addition and deletion of nodes (with Gourab Ghoshal and Mark Newman) Physical Review E 74 (2006) 036121.
 Global connectivity from local geometric constraints for sensor networks with various wireless footprints (with Raissa D'Souza, David Galvin, and Dana Randall) Proc. IPSN 2006.

Scale invariance in road networks
(with V. Kalapala, V. Sanwalani, and A. Clauset)
Physical Review E 73 (2006) 026130.

On the Bias of Traceroute Sampling; or, Powerlaw Degree Distributions in Regular Graphs
(with Dimitris Achlioptas, Aaron Clauset, and David Kempe)
Proc. STOC 2005. Journal version in J. ACM 56(4) (2009) 128.

Accuracy and Scaling Phenomena in Internet Mapping
(with Aaron Clauset) Physical Review Letters 94 (2005) 018701.

Finding Community Structure in Very Large Networks
(with Aaron Clauset and Mark Newman)
Physical Review E 70 (2004) 066111.

How Do Networks Become Navigable?
(with Aaron Clauset) Preprint, 2003.

Meanfield Solution of the SmallWorld Network Model
(with Mark Newman and Duncan Watts) Physical Review Letters 84
(2000) 32013204.
STATISTICAL PHYSICS, MARKOV CHAINS, AND GLASSY SYSTEMS
QUANTUM COMPUTATION, THE HIDDEN SUBGROUP PROBLEM, REPRESENTATION THEORY, QUANTUM WALKS, QUANTUM CIRCUITS, AND PSEUDORANDOMNESS

Dmitriy Kunisky and Cristopher Moore,
The spectrum of the GrigorievLaurent pseudomoments. Preprint.

Optimal epsilonbiased sets with just a little randomness
(with Alexander Russell)
SIAM J. Discrete Math. 29 (3) 13031311 (2015).

Group representations that resist random sampling
(with Shachar Lovett and Alexander Russell)
Random Struct. Algorithms 47(3): 605614 (2015).

Approximate representations, approximate homomorphisms, and lowdimensional embeddings of groups
(with Alexander Russell)
SIAM J. Discrete Math. 29 (1) 182197 (2015).

Limitations of single coset states and quantum algorithms for code equivalence
(with Hang Dinh and Alexander Russell)
Quantum Information and Computation 15 260294 (2015).
 Tree Codes and a Conjecture on Exponential Sums (with Leonard J. Schulman) Proc. ITCS 2014.

An entropic proof of Chang's lemma
(with Russell Impagliazzo and Alexander Russell)
SIAM J. Discrete Math., 281 (2014) 173176

SmallBias Sets for Nonabelian Groups: Derandomizing the AlonRoichman Theorem
(with Sixia Chen and Alexander Russell)
Proc. RANDOM '13, 436451

The complexity of the fermionant, and immanants of constant width
(with Stephan Mertens)
Theory of Computation 9 (6) 273282 (2013).

Approximating the permanent via nonabelian determinants
(with Alex Russell)
SIAM J. Computing (2012) 332355.

A graph integral formulation of the circuit partition polynomial
(with Alexander Russell)
Combinatorics, Probability, and Computing 20 (2011) 911920.

The McEliece cryptosystem resists quantum Fourier sampling attacks (with Hang Dinh and Alexander Russell) Proc. CRYPTO 2011. See also followup here.

Bounds on the quantum satisfiability threshold (with Sergey Bravyi and Alexander Russell) Proc. ICS 2010.

Finding conjugate stabilizer subgroups in PSL(2; q) and related groups (with Aaron Denney and Alexander Russell) Quantum Information and Communication 10(34) (2010) 282291.

On the Impossibility of a Quantum Sieve Algorithm for Graph Isomorphism
(with Alexander Russell and Piotr Sniady)
Proc. STOC 2007.

Quantum Algorithms for Simon's Problem over General Groups
(with Gorjan Alagic and Alexander Russell)
Proc. SODA 2007.

For Distinguishing Conjugate Hidden Subgroups, the Pretty Good Measurement is as Good as it Gets
(with Alexander Russell) Quantum Information and Computation 7 (2007) 752765.
 Limits of Quantum Coset States for Graph Isomorphism
(with Sean Hallgren, Martin Roetteler, Alexander Russell, and Pranab Sen)
Proc. STOC 2006.

The Symmetric Group Defies Strong Fourier Sampling: Part I
(with Alexander Russell and Leonard J. Schulman) Proc. FOCS 2005.
Journal version in SIAM J. Computing, 37 (2008) 18421864.

The Symmetric Group Defies Strong Fourier Sampling: Part II
(with Alexander Russell) Preprint, 2005.

Explicit Multiregister Measurements for Hidden Subgroup Problems; or, Fourier Sampling Strikes Back
(with Alexander Russell) Preprint, 2005.

Generic Quantum Fourier Transforms
(with Dan Rockmore and Alexander Russell) Proc. SODA 2004.

The Power of Basis Selection in Fourier Sampling:
Hidden Subgroup Problems in Affine Groups
(with Dan Rockmore, Alexander Russell, and Leonard J. Schulman)
Proc. SODA 2004.

Quantum Walks on the Hypercube (with Alexander Russell)
Proc. RANDOM 2002.

Quantum and Stochastic Branching Programs of Bounded Width
(with Farid Ablayev and Christopher Pollett) Proc. ICALP 2002.

Counting, Fanout, and the Complexity of Quantum ACC
(with Frederic Green, Steven Homer, and Christopher Pollett)
Quantum Information and Computation 2(1) (2002) 3565.

Parallel Quantum Computation and Quantum Codes (with Martin Nilsson)
SIAM Journal on Computing 31(3) (2002) 799815.

Quantum Automata and Quantum Grammars
(with J.P. Crutchfield) Theoretical Computer Science 237 (2000) 275306.
PHASE TRANSITIONS IN NPCOMPLETE PROBLEMS, RANDOM STRUCTURES, AND CONSTRUCTING HARD INSTANCES

Codes, Lower Bounds, and Phase Transitions in the Symmetric Rendezvous Problem.
(with Varsha Dani, Thomas Hayes, and Alexander Russell)
Random Structures and Algorithms 49(4) 742765 (2016).

The phase transition in random regular exact cover.
Annales l'Institut Henri Poincare D, Combinatorics, Physics and their Interactions, 3 (3) 349362 (2016).

The Power of Choice for Random Satisfiability
(with Varsha Dani, Josep Diaz, and Thomas Hayes)
Proc. RANDOM '13, 484496.

Tight bounds on the threshold for permuted kcolorability
(with Varsha Dani and Anna Olson) Proc. RANDOM '12, 505516.

Independent sets in random graphs from the weighted second moment method (with Varsha Dani) Proc. RANDOM '11, 472482.

The rigidity transition in random graphs
(with S. Kasiviswanathan and L. Theran)
Proc. 22nd Symp. on Discrete Algorithms (SODA '11) 12371252.

A ContinuousDiscontinuous SecondOrder Transition in the Satisfiability of Random HornSAT Formulas
(with Gabriel Istrate, Demetrios Demopoulos, and Moshe Y. Vardi)
Proc. RANDOM 2005.

Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively
(with Haixia Jia and Douglas Strain) Proc. AAAI 2005.

Hiding Satisfying Assignments: Two are Better than One
(with Dimitris Achlioptas and Haixia Jia) Journal of Artificial
Intelligence Research 24 (2005) 623639. Preliminary version appeared in AAAI 2004.

Random kSAT: Two Moments Suffice to Cross a Sharp Threshold
(with Dimitris Achlioptas) SIAM J. Computing 36 (2006) 740762.

The Resolution Complexity of Random Graph kColorability
(with Paul Beame, Joseph Culberson, and David Mitchell)
Discrete Applied Mathematics 153 (2005) 2547.

How Much Backtracking Does It Take to Color a Random Graph?
Rigorous Results on Heavy Tails
(with Haixia Jia) Proc. CP 2004.

From Spin Glasses to Hard Satisfiable Instances
(with Haixia Jia and Bart Selman) Proc. SAT 2004.

The Chromatic Number of Random Regular Graphs
(with Dimitris Achlioptas) Proc. RANDOM 2004.

Counting Connected Graphs and Hypergraphs via the Probabilistic Method
(with Amin CojaOghlan and Vishal Sanwalani) Proc. RANDOM 2004.

MAX kCUT and Approximating the Chromatic Number of Random Graphs
(with Amin CojaOghlan and Vishal Sanwalani)
Proc. ICALP 2003.

On the 2Colorability of Random Hypergraphs
(with Dimitris Achlioptas)
Proc. RANDOM 2002.

The Asymptotic Order of the kSAT Threshold
(with Dimitris Achlioptas)
Proc. Foundations of Computer Science (FOCS) 2002.

Almost All Graphs of Degree 4 are 3Colorable
(with Dimitris Achlioptas)
Proc. Symposium on the Theory of Computing (STOC) 2002, and
an invited paper in
Journal of Computer and System Sciences 67 (2003) 441471,
special issue for STOC 2002.

The Phase Transition in NAESAT and 1ink SAT
(with Dimitris Achlioptas, Arthur Chtcherba, and Gabriel Istrate)
Proc. Symposium on Discrete Algorithms (SODA) 2001.
BRAIDS IN THE NBODY PROBLEM
COMPUTATIONAL COMPLEXITY OF PREDICTION AND SIMULATION IN STATISTICAL PHYSICS AND CELLULAR AUTOMATA
PARALLEL COMPLEXITY, ALGEBRAIC CIRCUITS, MONOIDS, QUASIGROUPS, AND LOOPS
TILINGS AND POLYOMINOES
COMBINATORIAL GAMES
TWODIMENSIONAL LANGUAGES, OR "PICTURE LANGUAGES"
ANALOG COMPUTATION, RECURRENT NEURAL NETWORKS, AND DYNAMICAL SYSTEMS
PROOFOFSTAKE BLOCKCHAINS
MISCELLANEOUS

On the universal structure of human lexical semantics
(with Hyejin Youn, Logan Sutton, Eric Smith, Jon F. Wilkins, Ian Maddieson, William Croft, and Tanmoy Bhattacharya)
Proc. National Academy of Sciences, 113(7) 17661771 (2016).
 Stability analysis of financial contagion due to overlapping portfolios.
(with Fabio Caccioli, Munik Shrestha, and J. Doyne Famer)
J. Banking and Finance 46, 233245 (2014).
 A Complex Legacy. Nature Physics 7, 828830 (2011). Commentary on Turing's centenary.

Frugal and truthful auctions for vertex covers, flows, and cuts.
(with D. Kempe and M. Salek)
Proc. 51st. Foundations of Computer Science (FOCS '10) 745754.

The Physical Limits of Communication.
(with Michael Lachmann and Mark Newman)
American Journal of Physics 72 (2004) 12901293.
 What Is a Macrostate? Subjective Observations and Objective Dynamics. (with Cosma Shalizi)
 Comment on `Spacetime as a Causal Set'.
Physical Review Letters 60 (1988) 655.
Copyright 2003 by Cris Moore. All rights reserved.