4 papers · 1 filter
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…