Nicholas Kocurek

collaborators

6 papers

cs.DS2026

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 $I^» ≲ \frac{1}{I ^ }$ , where $I^$ is th…

cs.CC2026

Spectral Certificates and Sum-of-Squares Lower Bounds for Semirandom Hamiltonians

Nicholas Kocurek

The $k$ - $XOR$ problem is one of the most well-studied problems in classical complexity. We study a natural quantum analogue of $k$ - $XOR$ , the problem of computing…

cs.DS2025

Spectral Refutations of Semirandom $k$ -LIN over Larger Fields

Nicholas Kocurek, Peter Manohar

We study the problem of strongly refuting semirandom $k$ -LIN $(F)$ instances: systems of $k$ -sparse inhomogeneous linear equations over a finite field $F$ . For the…

math.ST2025

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).…

cs.CC2025

Faster Mixing of Higher-Dimensional Random Reversible Circuits

William Gay, William He, Nicholas Kocurek

We continue the study of the approximate $k$ -wise independence of random reversible circuits as permutations of ${\pm 1}^{n}$ . Our main result is the first construction of a natural…

cs.CR2025

Pseudorandomness Properties of Random Reversible Circuits