Cristopher Moore

Santa Fe Institute

CombinatoricsDiscrete mathematicsQuantum algorithmMathematicsRandom graph

225Publications

45H-index

12.7kCitations

What is this?

Publications 231

Newest

#1Antoine AllardH-Index: 13

#2Cristopher MooreH-Index: 45

Last. Laurent Hébert-DufresneH-Index: 13

view all 5 authors...

Most models of epidemic spread, including many designed specifically for COVID-19, implicitly assume that social networks are undirected, i.e., that the infection is equally likely to spread in either direction whenever a contact occurs. In particular, this assumption implies that the individuals most likely to spread the disease are also the most likely to receive it from others. Here, we review results from the theory of random directed graphs which show that many important quantities, includi...

Jan 5, 2020 in SODA (Symposium on Discrete Algorithms)

#1Erica Blum (UMD: University of Maryland, College Park)H-Index: 1

#1Erica BlumH-Index: 1

Last. Alexander RussellH-Index: 26

view all 5 authors...

#1Mehrdad Moharrami (UM: University of Michigan)H-Index: 2

#2Cristopher Moore (SFI: Santa Fe Institute)H-Index: 45

Last. Jiaming Xu (Duke University)H-Index: 19

view all 3 authors...

We study the problem of recovering a planted matching in randomly weighted complete bipartite graphs K_{n,n} For some unknown perfect matching M^* the weight of an edge is drawn from one distribution Pif e \in M^*and another distribution Qif e \in M^* Our goal is to infer M^* exactly or approximately, from the edge weights. In this paper we take P=\exp(\lambda)and Q=\exp(1/n) in which case the maximum-likelihood estimator of M^*is the minimum-weight matching $M_{\mi...

#1Stephan MertensH-Index: 16

#2Cristopher MooreH-Index: 45

We prove a remarkable combinatorial symmetry in the number of spanning configurations in site percolation: for a large class of lattices, the number of spanning configurations with an odd or even number of occupied sites differs by +/-1. In particular, this symmetry implies that the total number of spanning configurations is always odd, independent of the size or shape of the lattice. The class of lattices that share this symmetry includes the square lattice and the hypercubic lattice in any dim...

#1Erica BlumH-Index: 1

#2Aggelos KiayiasH-Index: 34

Last. Alexander RussellH-Index: 26

view all 5 authors...

The blockchain data structure maintained via the longest-chain rule---popularized by Bitcoin---is a powerful algorithmic tool for consensus algorithms. Such algorithms achieve consistency for blocks in the chain as a function of their depth from the end of the chain. While the analysis of Bitcoin guarantees consistency with error 2^{-k}for blocks of depth O(k) the state-of-the-art of proof-of-stake (PoS) blockchains suffers from a quadratic dependence on k these protocols, exemplified b...

#1Stephan Mertens (Otto-von-Guericke University Magdeburg)H-Index: 16

#2Cristopher Moore (SFI: Santa Fe Institute)H-Index: 45

We discuss the number of spanning configurations in site percolation. We show that for a large class of lattices, the number of spanning configrations is odd for all lattice sizes. This class includes site percolation on the square lattice and on the hypercubic lattice in any dimension.

These lecture notes are intended as a supplement to Moore and Mertens' The Nature of Computation or as a standalone resource, and are available to anyone who wants to use them. Comments are welcome, and please let me know if you use these notes in a course. There are 61 exercises. I emphasize that automata are elementary playgrounds where we can explore the issues of deterministic and nondeterministic computation. Unlike P vs. NP, we can prove that nondeterminism is equivalent to determinism, or...

#1Alexander S. Wein (NYU: New York University)H-Index: 8

#2Ahmed El Alaoui (Stanford University)H-Index: 6

Last. Cristopher Moore (SFI: Santa Fe Institute)H-Index: 45

view all 3 authors...

For the tensor PCA (principal component analysis) problem, we propose a new hierarchy of algorithms that are increasingly powerful yet require increasing runtime. Our hierarchy is analogous to the sum-of-squares (SOS) hierarchy but is instead inspired by statistical physics and related algorithms such as belief propagation and AMP (approximate message passing). Our level-\ellalgorithm can be thought of as a (linearized) message-passing algorithm that keeps track of \ellwise dependencies am...

Special Section on the Fifty-Sixth Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015)

#1Cristopher MooreH-Index: 45

#2Santosh VempalaH-Index: 48

This special section of 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS) contains 10 papers on a wide range of topics in theoretical computer science. Extended abstracts of these papers were presented at the conference, which took place October 18--20, 2015, in Berkeley, California. The regular conference program consisted of 86 papers chosen from among 314 submissions. These were selected by a program committee consisting of Arkadev Chattopadhyay, Irit Dinur, Uriel Feige, Yu...

#1Stephan MertensH-Index: 16

#2Cristopher MooreH-Index: 45

We study proper lattice animals for bond- and site-percolation on the hypercubic lattice \mathbb{Z}^dto derive asymptotic series of the percolation threshold p_cin 1/d The first few terms of these series were computed in the 1970s, but the series have not been extended since then. We add two more terms to the series for \pcsiteand one more term to the series for \pcbond using a combination of brute-force enumeration, combinatorial identities and an approach based on Pad\'e approxi...

12345678910