Publications

SOCIAL NETWORKS, COMMUNITY STRUCTURE, AND THE INTERNET

• Hierarchical structure and the prediction of missing links in networks (with Aaron Clauset and Mark Newman) Nature 453 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.

• 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 to appear in J. ACM.

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

• Finding Community Structure in Very Large Networks Physical Review E 70 (2004) 066111.

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

• Exact Solution of Site and Bond Percolation on Small-World Networks (with M.E.J. Newman) Physical Review E 62 (2000) 7059-7064.

• Epidemics and Percolation in Small-World Networks (with M.E.J. Newman) Physical Review E 61 (2000) 5678-5682.

• Mean-field Solution of the Small-World Network Model (with M.E.J. Newman and D. Watts) Physical Review Letters 84 (2000) 3201-3204.

QUANTUM COMPUTATION, THE HIDDEN SUBGROUP PROBLEM, QUANTUM WALKS, AND QUANTUM CIRCUITS

• 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, to appear.

• 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, to appear in SIAM J. Computing.

• 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

• 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, to appear. Preliminary version appeared in AAAI 2004.

• Random k-SAT: Two Moments Suffice to Cross a Sharp Threshold (with Dimitris Achlioptas) SIAM J. Computing, to appear.

• The Resolution Complexity of Random Graph k-Colorability (with Paul Beame, Joseph Culberson, and David Mitchell) Discrete Applied Mathematics, to appear.

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

• 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.

• 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 M.E.J. Newman) Journal of Statistical Physics 99 (2000) 661-690.

• Glassy Dynamics in an Exactly Solvable Spin Model. (with M.E.J. 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.

PARALLEL COMPUTATION AND CIRCUIT COMPLEXITY IN STATISTICAL PHYSICS

• 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.

• 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.

CELLULAR AUTOMATA: PREDICTION, COMPLEXITY, AND ALGEBRAIC PROPERTIES

• Predicting Non-linear Cellular Automata Quickly by Decomposing Them into Linear Ones. (with Timofey Pnin) Physica D 111 (1998) 27-41.

• 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

• Upper and lower bounds on continuous-time computation. (with Manuel Lameiras Campagnolo) Proc. 2nd International Conference on Unconventional Models of Computation (2000) 135-153.

• Iteration, Inequalities, and Differentiability in Analog Computers. (with Manuel Lameiras Campagnolo and Jose Felix Costa) Journal of Complexity 16 (2000) 642-660.

• 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.

MISCELLANEOUS

• The Physical Limits of Communication. (with Michael Lachmann and M.E.J. Newman) American Journal of Physics 72 (2004) 1290-1293.

• Braids in Classical Dynamics. Physical Review Letters 70 (1993) 3675-3679.

• Comment on `Space-time as a Causal Set'. Physical Review Letters 60 (1988) 655.