Showing cs.DSShow all
3 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.DS2024
Interactive Coding with Unbounded Noise
Eden Fargion, Ran Gelles, Meghal Gupta
Interactive coding allows two parties to conduct a distributed computation despite noise corrupting a certain fraction of their communication. Dani et al.\@ (Inf.\@ and Comp., 2018…
cs.DS2023
Dueling Optimization with a Monotone Adversary
Avrim Blum, Meghal Gupta, Gene Li +3
We introduce and study the problem of dueling optimization with a monotone adversary, which is a generalization of (noiseless) dueling convex optimization. The goal is to design an…