4 papers
Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
Ryan O'Donnell, Noah G. Singer
We study the Kaufman--Oppenheim coset complexes (STOC 2018, Eur. J. Comb. 2023), which have an elementary and strongly explicit description. Answering an open question of Kaufman,…
A Classical Quadratic Speedup for Planted XOR
Meghal Gupta, William He, Ryan O'Donnell +1
A recent work of Schmidhuber et al (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted XOR problem running quartically faster than all known cla…
Latency Guarantees for Caching with Delayed Hits
Keerthana Gurushankar, Noah G. Singer, Bernardo Subercaseaux
In the classical caching problem, when a requested page is not present in the cache (i.e., a "miss"), it is assumed to travel from the backing store into the cache "before" the nex…
Coboundary expansion inside Chevalley coset complex HDXs
Ryan O'Donnell, Noah G. Singer
Recent major results in property testing~\cite{BLM24,DDL24} and PCPs~\cite{BMV24} were unlocked by moving to high-dimensional expanders (HDXs) constructed from -ty…