Cris Moore's Homepage

I am an Associate Professor in the Computer Science Department at the University of New Mexico, with a joint appointment in the Department of Physics and Astronomy. I am also an External Professor at the Santa Fe Institute, where I will be spending Fall 2008.

I study interesting things like quantum computation (especially algorithms for the Hidden Subgroup Problem), phase transitions in NP-complete problems (e.g. the colorability of random graphs, or the satisfiability of random formulas) and social networks.

Curriculum Vitae, Publications, Teaching, Students, Gallery, Press

My book with Stephan Mertens: The Nature of Computation, coming out soon from Oxford University Press

Recent talks

Hierarchical Structure and Predicting Missing Links in Networks, joint work with Aaron Clauset and Mark Newman. Given at a DIMACS workshop at Georgia Tech and a Los Alamos workshop on Algorithms, Inference, and Statistical Physics.

The Power of Choice in Social Networks, joint work with Raissa D'Souza and Paul Krapivsky, a talk given at a Santa Fe Institute workshop on Scaling in Biological and Social Networks.

Phase Transitions in Physics and Computer Science: A Tale of Two Cultures, a talk for a general scientific audience given at the European Conference on Complex Systems.

Proving Lower Bounds on Random Satisfiability Using the Second Moment Method at the SIAM Conference on Discrete Mathematics in Victoria, 2006, minisyposium on Random Constraint Satisfaction Problems: from Physics to Algorithms.

The Hunt for a Quantum Algorithm for Graph Isomorphism, at QIP (Quantum Information Processing) 2006.

Fearful Symmetries: Factoring, Graph Isomorphism, and Quantum Computing, a more informal talk focusing on the role symmetry plays in physics, and comments on cultural differences between physics and computer science, given at ESA (European Symposium on Algorithms) 2005.

Books

Computational Complexity and Statistical Physics, A. Percus. G. Istrate and C. Moore, editors: buy it on Amazon

New Constructions in Cellular Automata, D. Griffeath and C. Moore, editors: buy it on Amazon

Teaching Tools

Here are two animated applets by UNM undergraduate Rory McGuire: Union-find (with path compression), and 2-3-4 Trees.

Other Stuff

If you're interested in employment or economic development in this region, I recommend you visit the New Mexico Information Technology and Software Association.

I have a cat named Spootie.

I am a big fan of Vladimir Nabokov. Here are some of his favorite words.

Here are three poems by my grandfather, Louis Untermeyer.

I have been known to cite fictional books.

I and Mats Nordahl are the editors-in-chief of the Journal of Unpublished Results, and I also edit the Journal of Weird-Ass Shit.

Finally, here is a list of restaurant reviews for Santa Fe and Paris. Of course, these are my own personal opinions, which, though correct, may or may not be shared by my employers.