I am a Professor at the Santa Fe Institute. Until recently, I was a Professor in the Computer Science Department at the University of New Mexico, with a joint appointment in the Department of Physics and Astronomy. I study interesting things like quantum computation (especially post-quantum cryptography and the possibility of algorithms for Graph Isomorphism), phase transitions in NP-complete problems (e.g. the colorability of random graphs, or the satisfiability of random formulas) and social, biological, and technological networks (in particular, automated techniques for identifying important structural features of large networks).
P vs. NP, Phase Transitions, and Incomputability in the Wild, given at the Turing Centenary Workshop on the Incomputable at the Kavli Royal Society International Center at Chicheley Hall.
Message-Passing Algorithms for Network Analysis, given at an IPAM workshop on Mathematical Challenges in Graphical Models and Message-Passing Algorithms. Joint work with Lenka Zdeborova, Florent Krzakala, Xiaoran Yan, Yaojia Zhu, Aurelien Decelle, and Mark Newman.
Let the Physics Do the Work: Scattering Algorithms for High-Dimensional Geometry, given at the NASA Quantum Future Technologies conference. Joint work with Aaron Denney.
The video and slides of Sending Secrets: Cryptography in a Quantum World, a Santa Fe Institute community lecture. The next link is to the technical version of this talk.
The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks, given at the IQC Seminar at Waterloo and a Dagstuhl Seminar on Quantum Cryptanalysis. Joint work with Hang Dinh and Alex Russell.
Approximate Representations and Approximate Homomorphisms, given as a UCLA Combinatorics Colloquium and a Tutte Combinatorics Colloquium at Waterloo. Joint work with Alex Russell.
Phase Transitions in NP-Complete Problems: A Challenge for Probability, Combinatorics, and Computer Science, an invited address given at the 2010 Western AMS meeting at UCLA.
Hierarchical Structure and Predicting Missing Links in Networks, joint work with Aaron Clauset and Mark Newman, and with new material on active learning, joint with Xiaoran Yan, Yaojia Zhu, and Jean-Baptiste Rouquier. Given at a CMU Statistics seminar and the Cornell Applied Math Colloquium.
Random Vectors, Random Matrices, and Diagrammatic Fun, invited talk at the SIAM meeting, Special Session on Probabilistic Combinatorics and Algorithms, and another version at the Computer Science/Discrete Math Seminar at the Institute for Advanced Study. Joint work with Alex Russell.
Continuous Methods in Computer Science, invited talk at LATIN 2010. I discuss two areas where continuous techniques arise in computer science: in the analysis of algorithms on random graphs, and in interior-point methods for convex optimization problems.
Bounds on the Quantum Satisfiability Threshold, joint work with Sergey Bravyi and Alex Russell. Proceedings of Innovations in Computer Science (ICS) 2010, and given at a Los Alamos workshop on Physics of Algorithms.
Approximating the Permanent with Nonabelian Determinants, joint work with Alex Russell. Given at a UC Berkeley Theory Seminar.
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, minisymposium 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.
New Constructions in Cellular Automata, D. Griffeath and C. Moore, editors: buy it on Amazon
One of the highest professional honors I have received.
For many years, I was blessed with a cat named Spootie.
I am a big fan of Vladimir Nabokov. Here are some of his favorite words.
Here are a few 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.