3 papers
cs.CC2025
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,…
cs.DS2025
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…
math.GR2024
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…