On Worst-Case Optimal Polynomial Intersection

Yihang Sun, Mary Wootters · 2026

Read On Worst-Case Optimal Polynomial Intersection by Yihang Sun, Mary Wootters (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-09533.txt.

Introduction

Sun and Wootters show Decoded Quantum Interferometry is not optimal for worst-case Optimal Polynomial Intersection. The task: a low-degree polynomial hitting as many sets as possible at given points. DQI solutions follow a semicircle law beating classical methods, but better solutions exist over prime fields. When each list holds about half the field, a beating solution appears once the degree-to-points ratio reaches about five eighths. A near-perfect solution appears once it reaches about three quarters. The argument links to local leakage resilience in secret sharing.

Catalog record

CREATORYihang Sun, Mary Wootters
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE142740
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.09533

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Worst-Case Optimal Polynomial Intersection Yihang Sun, Mary Wootters Abstract The Optimal Polynomial Intersection (OPI) problem is the following: Given sets S 1 , … , S m ⊆ 𝔽 S_{1},\ldots,S_{m}\subseteq\mathbb{F} and evaluation points a 1 , … , a m ∈ 𝔽 a_{1},\ldots,a_{m}\in\mathbb{F} , find a polynomial Q ∈ 𝔽 ⁡ [ x ] Q\in\mathbb{F}[x] of degree less than n n so that Q ⁡ ( a i ) ∈ S i Q(a_{i})\in S_{i} for as many i ∈ { 1 , 2 , … , m } 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 [ 13 ] . The quality of the solutions returned follows a semicircle law , which outperforms known efficient classical algorithms. But does DQI obtain the best possible solutions? That is, are there solutions better than the semicircle law for worst-case OPI instances? Surprisingly, before this work, the best existential results coincide with (and follow from) the best algorithmic results. In this work, we show that there are better solutions for worst-case OPI instances over prime fields. In particular, DQI and the semicircle law are not optimal. For example, when the lists S i S_{i} have size ρ ​ p \rho p for ρ ∼ 1 / 2 \rho\sim 1/2 , our results imply the existence of a solution that asymptotically beats the semicircle law whenever n / m ≥ 0.6225 n/m\geq 0.6225 , and we show that an asymptotically perfect solution exists whenever n / m ≥ 0.7496 n/m\geq 0.7496 . Our results generalize to Max-LINSAT problems derived from any Maximum Distance Separable (MDS) code, and to any ρ ∈ ( 0 , 1 ) \rho\in(0,1) . The key insight to our improvement is a connection to local leakage resilience of secret sharing schemes. Along the way, we recover several re-proofs of the existence of solutions achieving the semicircle law. 1 Introduction The Optimal Polynomial Intersection (OPI) problem is to find a low-degree polynomial that satisfies a large number of constraints on its evaluations. Formally, we have the following definition. Problem 1.1 (Optimal Polynomial Intersection) . Fix prime power q and integers 0\leq n\leq m\leq q , and fix distinct evaluation points a_{1},\ldots,a_{m}\in\mathbb{F}_{q} . The Optimal Polynomial Intersection (OPI) problem (with respect to a_{1},\ldots,a_{m} ) is the following: Given input subsets S_{1},\ldots,S_{m} with S_{i}\subseteq\mathbb{F}_{q} , find a polynomial Q\in\mathbb{F}_{q}[x] with \deg Q<n that maximizes the satisfaction ratio s(Q)\coloneqq\frac{1}{m}|\{i\in\{1,2,\ldots,m\}\,:\,Q(a_{i})\in S_{i}\}|. OPI arises as a natural problem in many different areas. In coding theory, it is related to list-recovery of Reed-Solomon codes: There, the goal is to show that there are not too many polynomials Q of degree less than n so that s(Q)\geq\alpha (for some parameter \alpha ), and to return them all. In cryptography, OPI has been studied under the name noisy polynomial reconstruction/interpolation (e.g., [ 22 , 5 ] ), and has been considered as a hardness assumption in certain parameter regimes. More recently, OPI has arisen as a potential demonstration of quantum advantage: The Decoded Quantum Interferometry (DQI) algorithm [ 13 ] and related algorithms [ 7 , 8 , 27 , 15 ] give quantum algorithms to solve OPI that out-perform known efficient classical heuristics. The guarantees of DQI for OPI hold in the worst case: For any input sets S_{1},\ldots,S_{m} , DQI finds a polynomial Q of degree less than n so that the fraction of satisfied constraints approaches a semicircle law . More precisely, for \mu\in[0,1/2] and \rho\in(0,1) , let \operatorname{SCL}_{\rho}(\mu)\coloneqq\begin{cases}\mathopen{}\mathclose{{\left(\sqrt{\mu(1-\rho)}+\sqrt{\rho(1-\mu)}}}\right)^{2}&\text{if }\mu+\rho\leq 1\\ 1&\text{if }\mu+\rho\geq 1\end{cases}. (1.1) Then, as n,m\to\infty with fixed ratio \mu=n/2m , for any S_{1},\ldots,S_{m}\subseteq\mathbb{F}_{q} of size \rho q , [ 13 ] shows that DQI efficiently finds a polynomial Q of degree less than n so that \mathbb{E}[s(Q)]\geq\operatorname{SCL}_{\rho}(\mu)-o(1). Above, the expectation is over the randomness of the algorithm. When \rho\sim 1/2 , we have \operatorname{SCL}_{1/2}(\mu)=\frac{1}{2}+\sqrt{\mu(1-\mu)}, the equation of a semicircle. In contrast, the best known classical heuristic (Prange’s algorithm) is only able to obtain a satisfaction ratio of 1/2+\mu+o(1) , even on average-case instances. A natural question is how the semicircle law compares to the best possible solution to OPI. Does DQI find optimal solutions in the worst case? Before this work, it was not known if there were any better solutions in the worst case. Question 1.2 . Fix a_{1},\ldots,a_{m}\subseteq\mathbb{F}_{q} . Given \rho\in(0,1) and n,m\to\infty so that n/2m\to\mu , what is the optimal worst-case satisfaction ratio for OPI? That is, what is \min_{\begin{subarray}{c}S_{1},\ldots,S_{m}\\ |S_{i}|=\rho q\end{subarray}}\max_{\begin{subarray}{c}Q\in\mathbb{F}_{q}^{[}x]\\ \deg Q<n\end{subarray}}s(Q)\text{?} In particular, is it strictly larger than the semicircle law \operatorname{SCL}_{\rho}(\mu) ? Or does DQI find asymptotically optimal worst-case solutions? We note that prior work [ 7 , 8 ] obtained (algorithmic) improvements on the semicircle law for OPI; however those works consider the average case over an ensemble of OPI instances, not worst-case OPI instances as we do here. We discuss the relationship to these works in Section 1.3.1 . Our contributions. Our contributions are twofold. • Our main results, discussed quantitatively below in Section 1.1 , make progress on 1.2 . We show that, over prime fields, indeed there are solutions to worst-case OPI instances that are asymptotically better than the semicircle law \operatorname{SCL}_{\rho}(\mu) , for a wide range of parameters (\rho,\mu) . While our results are existential, we hope that our framework may lead to improved quantum algorithms. We discuss this possibility more in Section 1.4 . • Along the way, we develop new and simplified proofs of the existence of solutions on the semicircle law. The fact that these solutions exist follows from the analysis of DQI [ 13 ] , but “proof-by-quantum-algorithm” does not seem like the “correct” way to prove this classical combinatorial statement. We give two simpler re-proofs of this result. These simpler proofs form the basis of our (more complicated) improvements. We note that some of the ideas in our re-proofs are present in [ 31 , 20 ] ; by making them explicit, we are able to identify avenues for improvement. More generally, our results apply to any Max-LINSAT problem that arises from a Maximum Distance Separable (MDS) code. A linear code C\subseteq\mathbb{F}_{q}^{m} of dimension n is just an n -dimensional subspace of \mathbb{F}_{q}^{m} . A matrix B\in\mathbb{F}_{q}^{m\times n} is a generator matrix of C if C is the column span of B . We say that C is Maximum Distance Separable (MDS) if any n rows of B are linearly independent; equivalently, if any n symbols of a codeword c\in C determine the entire codeword. Problem 1.3 ((MDS) Max-LINSAT) . Fix a prime power q and a matrix B\in\mathbb{F}_{q}^{m\times n} . The Max-LINSAT problem (with respect to B ) is the following: Given input lists S_{1},\ldots,S_{m} with S_{i}\subseteq\mathbb{F}_{q} , find x\in\mathbb{F}_{q}^{n} that maximizes the satisfaction ratio s(x)\coloneqq\frac{1}{m}\mathopen{}\mathclose{{\left|\mathopen{}\mathclose{{\left\{i\in\{1,2,\ldots,m\}:(Bx)_{i}\in S_{i}}}\right\}}}\right|. (1.2) When the matrix B is the generator matrix of an MDS code, we call the problem MDS Max-LINSAT (with respect to B ). As observed in [ 13 , Section 5] , OPI is a special case of MDS Max-LINSAT when the matrix B is the Vandermonde matrix with B_{i,j}=a_{i}^{j-1} . It corresponds to the case when the MDS code C is a Reed-Solomon code. 1 1 1 A Reed-Solomon code

Read the complete text