Showing cs.DSShow all
2 papers · 1 filter
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…
cs.DS2025
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…