Publications

Publications are arranged by topic:

Algorithmic Fairness and Criminal Justice

Algorithms and Phase Transitions in Statistical Inference (other than community detection in networks)

Social and Biological Networks, Message-Passing Algorithms, Community Detection, and the Internet

Quantum Computation, the Hidden Subgroup Problem, Representation Theory, Quantum Walks, Quantum Circuits, and Pseudorandomness

Phase Transitions in NP-Complete Problems, Random Structures, and Constructing Hard Instances

Statistical Physics, Markov Chains, and Glassy Systems

Braids in the n-Body 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

Two-Dimensional Languages, or "Picture Languages"

Analog Computation, Recurrent Neural Networks, and Dynamical Systems

Proof of Stake Blockchains

Miscellaneous

ALGORITHMIC FAIRNESS AND CRIMINAL JUSTICE

Pretrial Risk Assessment on the Ground: Algorithms, Judgments, Meaning, and Policy (with Elise Ferguson and Paul Guerin) MIT Case Studies in Social and Ethical Responsibilities of Computing, Summer 2023.
How Much Risk, and Risk of What? A Closer Look at Pretrial Rearrest and Risk Assessment (with Elise Ferguson and Paul Guerin) Preprint.
How Accurate are Rebuttable Presumptions of Pretrial Dangerousness? A Natural Experiment from New Mexico (with Elise Ferguson and Paul Guerin) J. Empirical Legal Studies 20(2) 377-408 (2023).

EPIDEMICS, NETWORKS, AND PERCOLATION

Compressing the chronology of a temporal network with graph commutators (with Andrea J. Allen (first author) and Laurent Hebert-Dufresne) Physical Review Letters 132, 077402 (2024).
The role of directionality, heterogeneity and correlations in epidemic risk and spread (with Antoine Allard, Samuel V. Scarpino, Benjamin M. Althouse, and Laurent Hebert-Dufresne) SIAM Review 65(2) 471-492 (2023).
Effective Resistance for Pandemics: Mobility Network Sparsification for High-Fidelity Epidemic Simulation (with Alexander Mercier (first author) and Samuel V. Scarpino) PLoS Computational Biology 18(11): e1010650 (2022).
The heavy tail of outbreaks (reprinted as Why COVID-19 Flare-Ups Will Keep Happening) Nautilus issue 084, May 13, 2020.
Percolation is Odd (with Stephan Mertens) Physical Review Letters 123 (2019) 230605.
Series Expansion of Critical Densities for Percolation on Z^d (with Stephan Mertens) J. Physics A: Mathematical and Theoretical, 51 (47) 475001 (2018).
Percolation Thresholds and Fisher Exponents in Hypercubic Lattices (with Stephan Mertens) Physical Review E 98 (2018) 022120.
Percolation Thresholds in Hyperbolic Lattices (with Stephan Mertens) Physical Review E 96 (2017) 042116.
Message-passing approach for recurrent-state epidemic models on networks (with Munik Shrestha and Samuel V. Scarpino) Physical Review E 92 022821 (2015).
A message-passing approach for threshold models of behavior in networks (with Munik Shrestha) Physical Review E 89 022805 (2014).
Continuum Percolation Thresholds in Two Dimensions (with Stephan Mertens) Physical Review E 86 (2012) 061109.
Exact Solution of Site and Bond Percolation on Small-World Networks (with Mark Newman) Physical Review E 62 (2000) 7059-7064.
Epidemics and Percolation in Small-World Networks (with Mark Newman) Physical Review E 61 (2000) 5678-5682.

ALGORITHMS AND PHASE TRANSITIONS IN STATISTICAL INFERENCE (other than community detection)

Disordered Systems Insights on Computational Hardness (with David Gamarnik and Lenka Zdeborova). J. Statistical Mechanics: Theory and Experiment, to appear.
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): 2663-2720 (2021).
The Kikuchi Hierarchy and Tensor PCA (with Alex Wein and Ahmed El Alaoui) Proc. FOCS 2019.
Information-theoretic 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, MESSAGE-PASSING ALGORITHMS, COMMUNITY DETECTION, AND THE INTERNET

Improved Reconstruction of Random Geometric Graphs (with Varsha Dani, Josep Diaz, and Thomas P. Hayes) Proc. ICALP 2022 1-17.
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) 1098-1119 (2019). Conference version in Proc. RANDOM '17, 1-28.
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 mixed-membership stochastic block models (with Antonia Godoy-Lorite, Roger Guimera, and Marta Sales-Pardo) Proc. National Academy of Sciences 113 (50) 14207-14212 (2016).
Information-theoretic thresholds for community detection in sparse networks (with Jess Banks, Joe Neeman, and Praneeth Netrapalli) Proc. COLT 2016, 383-416.
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: message-passing for modularity (with Pan Zhang) Proc. National Academy of Sciences 111 (51) 18144-18149 (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 Degree-corrected 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 Degree-generated Block Models: Generating and Inferring Communities with Inhomogeneous Degree Distributions (with Yaojia Zhu and Xiaoran Yan) J. Complex Networks 2(1) 1-18 (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) 20935-20940 (2013).
Scalable Text and Link Analysis with Mixed-Topic 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) 519-524.
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 98-101 (2008).
The Power of Choice in Network Growth (with Raissa D'Souza and Paul Krapivsky) European Journal of Physics B 59 535-543 (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, Power-law Degree Distributions in Regular Graphs (with Dimitris Achlioptas, Aaron Clauset, and David Kempe) Proc. STOC 2005. Journal version in J. ACM 56(4) (2009) 1-28.
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.
Mean-field Solution of the Small-World Network Model (with Mark Newman and Duncan Watts) Physical Review Letters 84 (2000) 3201-3204.

STATISTICAL PHYSICS, MARKOV CHAINS, AND GLASSY SYSTEMS

Lower Bounds on the Critical Density in the Hard Disk Model via Optimized Metrics (with Thomas P. Hayes) Preprint, 2014.
Sampling Grid Colourings with Fewer Colours (with D. Achlioptas, M. Molloy and F. van Bussel) Proc. LATIN 2004, 80-89.
Height Representation, Critical Exponents, and Ergodicity in the Four-state Triangular Potts Antiferromagnet (with Mark Newman) Journal of Statistical Physics 99 (2000) 661-690.
Glassy Dynamics in an Exactly Solvable Spin Model. (with Mark Newman) Physical Review E 60 (1999) 5068-5072.
Vortex Dynamics and Entropic Coulomb Forces in in Antiferromagnets and Antiferromagnetic Potts Models. (with Mats G. Nordahl, Nelson Minar, and Cosma Rohilla Shalizi) Physical Review E 60 (1999) 5344-5351.

QUANTUM COMPUTATION, THE HIDDEN SUBGROUP PROBLEM, REPRESENTATION THEORY, QUANTUM WALKS, QUANTUM CIRCUITS, AND PSEUDORANDOMNESS

Dmitriy Kunisky and Cristopher Moore, The spectrum of the Grigoriev-Laurent pseudomoments. Preprint.
Optimal epsilon-biased sets with just a little randomness (with Alexander Russell) SIAM J. Discrete Math. 29 (3) 1303-1311 (2015).
Group representations that resist random sampling (with Shachar Lovett and Alexander Russell) Random Struct. Algorithms 47(3): 605-614 (2015).
Approximate representations, approximate homomorphisms, and low-dimensional embeddings of groups (with Alexander Russell) SIAM J. Discrete Math. 29 (1) 182-197 (2015).
Limitations of single coset states and quantum algorithms for code equivalence (with Hang Dinh and Alexander Russell) Quantum Information and Computation 15 260-294 (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., 28-1 (2014) 173-176
Small-Bias Sets for Nonabelian Groups: Derandomizing the Alon-Roichman Theorem (with Sixia Chen and Alexander Russell) Proc. RANDOM '13, 436-451
The complexity of the fermionant, and immanants of constant width (with Stephan Mertens) Theory of Computation 9 (6) 273-282 (2013).
Approximating the permanent via nonabelian determinants (with Alex Russell) SIAM J. Computing (2012) 332--355.
A graph integral formulation of the circuit partition polynomial (with Alexander Russell) Combinatorics, Probability, and Computing 20 (2011) 911-920.
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(3-4) (2010) 282-291.
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) 752-765.
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) 1842-1864.
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) 35-65.
Parallel Quantum Computation and Quantum Codes (with Martin Nilsson) SIAM Journal on Computing 31(3) (2002) 799-815.
Quantum Automata and Quantum Grammars (with J.P. Crutchfield) Theoretical Computer Science 237 (2000) 275-306.

PHASE TRANSITIONS IN NP-COMPLETE 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) 742--765 (2016).
The phase transition in random regular exact cover. Annales l'Institut Henri Poincare D, Combinatorics, Physics and their Interactions, 3 (3) 349-362 (2016).
The Power of Choice for Random Satisfiability (with Varsha Dani, Josep Diaz, and Thomas Hayes) Proc. RANDOM '13, 484-496.
Tight bounds on the threshold for permuted k-colorability (with Varsha Dani and Anna Olson) Proc. RANDOM '12, 505-516.
Independent sets in random graphs from the weighted second moment method (with Varsha Dani) Proc. RANDOM '11, 472-482.
The rigidity transition in random graphs (with S. Kasiviswanathan and L. Theran) Proc. 22nd Symp. on Discrete Algorithms (SODA '11) 1237-1252.
A Continuous-Discontinuous Second-Order Transition in the Satisfiability of Random Horn-SAT 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) 623-639. Preliminary version appeared in AAAI 2004.
Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold (with Dimitris Achlioptas) SIAM J. Computing 36 (2006) 740-762.
The Resolution Complexity of Random Graph k-Colorability (with Paul Beame, Joseph Culberson, and David Mitchell) Discrete Applied Mathematics 153 (2005) 25-47.
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 Coja-Oghlan and Vishal Sanwalani) Proc. RANDOM 2004.
MAX k-CUT and Approximating the Chromatic Number of Random Graphs (with Amin Coja-Oghlan and Vishal Sanwalani) Proc. ICALP 2003.
On the 2-Colorability of Random Hypergraphs (with Dimitris Achlioptas) Proc. RANDOM 2002.
The Asymptotic Order of the k-SAT Threshold (with Dimitris Achlioptas) Proc. Foundations of Computer Science (FOCS) 2002.
Almost All Graphs of Degree 4 are 3-Colorable (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) 441-471, special issue for STOC 2002.
The Phase Transition in NAESAT and 1-in-k SAT (with Dimitris Achlioptas, Arthur Chtcherba, and Gabriel Istrate) Proc. Symposium on Discrete Algorithms (SODA) 2001.

BRAIDS IN THE N-BODY PROBLEM

New Periodic Orbits for the n-Body Problem (with Michael Nauenberg) Journal of Computational and Nonlinear Dynamics 1 (2006) 271-367, Special issue for Philip Holmes' 60th birthday.
Braids in Classical Dynamics Physical Review Letters 70 (1993) 3675-3679.

COMPUTATIONAL COMPLEXITY OF PREDICTION AND SIMULATION IN STATISTICAL PHYSICS AND CELLULAR AUTOMATA

Automatic Filters for the Detection of Coherent Structure in Spatiotemporal Systems (with Cosma Rohilla Shalizi, Robert Haslinger, Jean-Baptiste Rouquier, and Kristina Lisa Klinkner) Physical Review E 73 (2006): 036104.
Computational Complexity in Physics NATO Workshop on Complexity and Large Deviations, Geilo, Norway, 2001.
Internal Diffusion-Limited Aggregation: Parallel Algorithms and Complexity (with Jonathan Machta) Journal of Statistical Physics 99 (2000) 629-660.
The Computational Complexity of Sandpiles (with Martin Nilsson) Journal of Statistical Physics 96 (1999) 205-224.
Predicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones (with Timofey Pnin) Physica D 111 (1998) 27-41.
Majority-Vote Cellular Automata, Ising Dynamics, and P-Completeness Journal of Statistical Physics 88 (1997) 795-805.
Predicting Lattice Gases is P-complete (with Mats Nordahl) Santa Fe Institute Working Paper 97-04-034.
Quasi-linear Cellular Automata. Physica D 103 (1997) 100-132, the Proceedings of the International Workshop on Lattice Dynamics.
Commuting Cellular Automata (with Timothy Boykett) Complex Systems 11 (1997) 55-64.
Algebraic Properties of the Block Transformation on Cellular Automata (with Arthur Drisko) Complex Systems 10(3) (1996) 185-194.
Life Without Death is P-complete (with David Griffeath) Complex Systems 10 (1996) 437-447.

PARALLEL COMPLEXITY, ALGEBRAIC CIRCUITS, MONOIDS, QUASIGROUPS, AND LOOPS

Subtree-Counting Loops (with Francois Lemieux and Denis Therien) Quasigroups and Related Systems 8 (2001) 45-65.
Satisfiability of Systems of Equations over Finite Monoids (with Pascal Tesson and Denis Therien) Proc. Mathematical Foundations of Computer Science (2001).
Equation Satisfiability and Program Satisfiability for Finite Monoids (with David Mix Barrington, Pierre McKenzie, Pascal Tesson, and Denis Therien) Proc. Mathematical Foundations of Computer Science (2000).
Circuits and Expressions with Non-Associative Gates (with Francois Lemieux, Denis Therien, Joshua Berman, and Arthur Drisko.) Proceedings of the 12th Annual IEEE Conference on Computational Complexity (1997) 193-203. A longer version appeared as Journal of Computer and System Sciences 60 (2000) 368-394.
Polyabelian loops and Boolean-completeness (with Francois Lemieux and Denis Therien) Commentationes Mathematicae Universitatis Carolinae 41 (2000) 671-686.

TILINGS AND POLYOMINOES

Ribbon Tile Invariants from Signed Area (with Igor Pak) J. Combin. Theory Ser. A. 98 (2002) 1-16.
Tiling groups for Wang tiles (with Ivan Rapaport and Eric Remila) Proc. Symposium on Discrete Algorithms (SODA) 2002.
Hard Tiling Problems with Simple Tiles (with John Michael Robson) Discrete and Computational Geometry 26(4) (2001) 573-590.
An n-Dimensional Generalization of the Rhombus Tiling (with Joakim Linde and Mats Nordahl) Discrete Mathematics and Theoretical Computer Science Proceedings AA (2001) 23-42.
Height representations and long-range order in random trimer tilings of the square lattice (DRAFT!)
Some Polyomino Tilings of the Plane.

COMBINATORIAL GAMES

Who Wins Domineering on Rectangular Boards? (with Michael Lachmann and Ivan Rapaport) MSRI Workshop on Combinatorial Games (2000).
One-Dimensional Peg Solitaire, and Duotaire. (with David Eppstein) MSRI Workshop on Combinatorial Games (2000).

TWO-DIMENSIONAL LANGUAGES, OR "PICTURE LANGUAGES"

Rectangles and squares recognized by two-dimensional automata. (with Jarkko Kari) In Theory Is Forever, Essays Dedicated to Arto Salomaa on the Occasion of His 70th Birthday. J.Karhumaki, H.Maurer, G.Paun, G.Rozenberg (Eds.), LNCS 3113 (2004) 134-144.
New Results on Alternating and Non-deterministic Two-dimensional Finite-state Automata. (with Jarkko Kari) Symposium on Theoretical Aspects of Computer Science (STACS) 2001.
Complexity of Two-Dimensional Patterns. (with Kristian Lindgren and Mats Nordahl) Journal of Statistical Physics 91(5-6) (1998) 909-951.

ANALOG COMPUTATION, RECURRENT NEURAL NETWORKS, AND DYNAMICAL SYSTEMS

An Analog Characterization of the Grzegorczyk Hierarchy (with Manuel Lameiras Campagnolo and Jose Felix Costa) Journal of Complexity 18 (2002) 977-1000.
Iteration, inequalities, and differentiability in analog computers (with Manuel Lameiras Campagnolo and Jose Felix Costa) Journal of Complexity 16 (2000) 642-660.
Upper and lower bounds on continuous-time computation (with Manuel Lameiras Campagnolo) Proc. 2nd International Conference on Unconventional Models of Computation (2000) 135-153.
An Analog Characterization of the Subrecursive Functions (with Manuel Lameiras Campagnolo and Jose Felix Costa) Proc. 4th Conference on Real Numbers and Computers.
Queues, Stacks, and Transcendentality at the Transition to Chaos (with Porus Lakdawala) Physica D 135 (2000) 24-40.
Closed-form Analytic Maps in One and Two Dimensions Can Simulate Universal Turing Machines (with Pascal Koiran) Theoretical Computer Science, 210 (1999) 217-223 (Special Issue on Real Numbers).
Finite-Dimensional Analog Computers: Flows, Maps, and Recurrent Neural Networks Invited talk for the First International Conference on Unconventional Models of Computation in Auckland, New Zealand, 1998.
Dynamical Recognizers: Real-time Language Recognition by Analog Computers. Theoretical Computer Science 201 (1998) 99-136.
Recursion Theory on the Reals and Continuous-time Computation. Theoretical Computer Science 162 (1996) 23-44.
Generalized One-sided Shifts and Maps of the Interval. Nonlinearity 4 (1991) 727-745.
Generalized Shifts: Undecidability and Unpredictability in Dynamical Systems. Nonlinearity 4 (1991) 199-230.
Undecidability and Unpredictability in Dynamical Systems. Physical Review Letters 64 (1990) 2354-2357.

PROOF-OF-STAKE BLOCKCHAINS

The Generals' Scuttlebutt: Byzantine-Resilient Gossip Protocols (with Sandro Coretti, Aggelos Kiayias, and Alexander Russell) Proc. 2022 Conference on Computer and Communications Security (2022) 595-608.
Efficient Random Beacons with Adaptive Security for Ungrindable Blockchains (with Aggelos Kiayias, Saad Quader, and Alexander Russell) Preprint, 2021.
Linear Consistency for Proof-of-Stake Blockchains (with Erica Blum, Aggelos Kiayias, Saad Quader, and Alexander Russell) Proc. SODA 2020, 1135-1154.

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) 1766-1771 (2016).
Stability analysis of financial contagion due to overlapping portfolios. (with Fabio Caccioli, Munik Shrestha, and J. Doyne Famer) J. Banking and Finance 46, 233-245 (2014).
A Complex Legacy. Nature Physics 7, 828-830 (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) 745-754.
The Physical Limits of Communication. (with Michael Lachmann and Mark Newman) American Journal of Physics 72 (2004) 1290-1293.
What Is a Macrostate? Subjective Observations and Objective Dynamics. (with Cosma Shalizi)
Comment on `Space-time as a Causal Set'. Physical Review Letters 60 (1988) 655.