6 papers
QEDBENCH: Quantifying the Alignment Gap in Automated Evaluation of University-Level Mathematical Proofs
Santiago Gonzalez, Alireza Amiri Bavandpour, Peter Ye +48
As Large Language Models (LLMs) saturate elementary benchmarks, the research frontier has shifted from generation to the reliability of automated evaluation. We demonstrate that st…
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…
Few Single-Qubit Measurements Suffice to Certify Any Quantum State
Meghal Gupta, William He, Ryan O'Donnell
A fundamental task in quantum information science is state certification: testing whether a lab-prepared -qubit state is close to a given hypothesis state. In this work, we show…
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…
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…
Constant Query Local Decoding Against Deletions Is Impossible
Meghal Gupta
Locally decodable codes (LDC's) are error-correcting codes that allow recovery of individual message indices by accessing only a constant number of codeword indices. For substituti…