5 papers
The Collapse of Unentangled Stoquastic Merlin-Arthur Proof Systems
William Gay, Fernando Granha Jeronimo
Entanglement and interference are among the most fundamental properties of quantum mechanics. In this work, we investigate the role and power of interference in the context of dete…
Multipass Linear Sketches for Geometric LP-Type Problems
N. Efe Ãekirge, William Gay, David P. Woodruff
LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinat…
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).…
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…
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…