Publications (151)
Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts
David Kempe, Mahyar Salek, Cristopher Moore
We study truthful mechanisms for hiring a team of agents in three classes of set systems: Vertex Cover auctions, k-flow auctions, and cut auctions. For Vertex Cover auctions, the v…
Lower Bounds on the Critical Density in the Hard Disk Model via Optimized Metrics
Thomas P. Hayes, Cristopher Moore
We prove a new lower bound on the critical density of the hard disk model, i.e., the density below which it is possible to efficiently sample random configurations of no…
Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively
Haixia Jia, Cristopher Moore, Doug Strain
To test incomplete search algorithms for constraint satisfaction problems such as 3-SAT, we need a source of hard, but satisfiable, benchmark instances. A simple way to do this is…
The McEliece Cryptosystem Resists Quantum Fourier Sampling Attacks
Hang Dinh, Cristopher Moore, Alexander Russell
Quantum computers can break the RSA and El Gamal public-key cryptosystems, since they can factor integers and extract discrete logarithms. If we believe that quantum computers will…
Gurau's spectral density is not a probability measure for individual real symmetric tensors
Maximilian Jerdee, Dmitriy Kunisky, Cristopher Moore
Gurau (2020) proposed a generalization of the trace of the matrix resolvent to tensors of higher order, and recent work has explored analogs of the Wigner semicircle and Marchenko-…
Spatial Mixing for Independent Sets in Poisson Random Trees
Varsha Dani, Thomas P. Hayes, Cristopher Moore
We consider correlation decay in the hard-core model with fugacity on a rooted tree in which the arity of each vertex is independently Poisson distributed with mean . S…