3 papers
cs.DS2025
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…
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.CR2025
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…