2 papers
quant-ph2026
Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
Brandon Augustino, Shouvanik Chakrabarti, Enrico Fontana +4
We establish a linear quantum query lower bound for high-accuracy convex optimization over an explicit family of -dimensional ellipsoids. We focus on linear optimization with an…
cs.CC2023
Approximate degree lower bounds for oracle identification problems
Mark Bun, Nadezhda Voronova
The approximate degree of a Boolean function is the minimum degree of real polynomial that approximates it pointwise. For any Boolean function, its approximate degree serves as a l…