6 papers
Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
Nicholas Kocurek, Shayan Oveis Gharan, Dante Tjowasi
We design an efficient sampling algorithm to generate samples from the hardcore model on random regular bipartite graphs as long as , where is the d…
Spectral Certificates and Non-commutative Sum-of-Squares Lower Bounds for Hamiltonians
Nicholas Kocurek, Chinmay Nirkhe
A central question in quantum many-body physics is estimating the ground energy of a -local Hamiltonian system. In this work, we present a spectral technique for certifying a lo…
Spectral Refutations of Semirandom -LIN over Larger Fields
Nicholas Kocurek, Peter Manohar
We study the problem of strongly refuting semirandom -LIN instances: systems of -sparse inhomogeneous linear equations over a finite field . For the…
Sampling and Identity-Testing Without Approximate Tensorization of Entropy
William Gay, William He, Nicholas Kocurek +1
Certain tasks in high-dimensional statistics become easier when the underlying distribution satisfies a local-to-global property called approximate tensorization of entropy (ATE).…
Pseudorandomness Properties of Random Reversible Circuits
William Gay, William He, Nicholas Kocurek +1
Motivated by practical concerns in cryptography, we study pseudorandomness properties of permutations on computed by random circuits made from reversible -bit gates…
Faster Mixing of Higher-Dimensional Random Reversible Circuits
William Gay, William He, Nicholas Kocurek
We continue the study of the approximate -wise independence of random reversible circuits as permutations of . Our main result is the first construction of a natural…