{"id":"arxiv/2604.09533","url":"https://arxiv.org/abs/2604.09533","tags":["cs.DM","cs.IT","quant-ph"],"score":0,"title":"On Worst-Case Optimal Polynomial Intersection","domain":"cs.DM","source":"arxiv","authors":["Yihang Sun","Mary Wootters"],"reviews":0,"subject":"cs.DM","summary":"The Optimal Polynomial Intersection (OPI) problem is the following: Given sets $S_1, \\ldots, S_m \\subseteq \\mathbb{F}$ and evaluation points $a_1, \\ldots, a_m \\in \\mathbb{F}$, find a polynomial $Q \\in \\mathbb{F}[x]$ of degree less than $n$ so that $Q(a_i) \\in S_i$ for as many $i \\in \\{1, 2, \\ldots, m\\}$ as possible. Decoded Quantum Interferometry (DQI) is a quantum algorithm that efficiently returns good solutions to the problem, even on worst-case instances (Jordan et. al., 2025). The quality of the solutions returned follows a semicircle law, which outperforms known efficient classical…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-04-10","reactions":{}}