Match!
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...
Source
#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...
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...
2 CitationsSource
#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...
2 Citations
#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...
5 Citations
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...
Source
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...
2 CitationsSource
12345678910