arxiv: 2604.09533 · v1 · submitted 2026-04-10 · 💻 cs.DM · cs.IT· math.IT· quant-ph

Recognition: unknown

On Worst-Case Optimal Polynomial Intersection

Yihang Sun , Mary Wootters

Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:49 UTC · model grok-4.3

classification 💻 cs.DM cs.ITmath.ITquant-ph

keywords Optimal Polynomial IntersectionDecoded Quantum Interferometrysemicircle lawlocal leakage resiliencesecret sharingMDS codesworst-case analysis

0 comments

The pith

Solutions to worst-case Optimal Polynomial Intersection can asymptotically beat the semicircle law from Decoded Quantum Interferometry over prime fields.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that for the Optimal Polynomial Intersection problem, there exist solutions better than those guaranteed by the semicircle law from the quantum algorithm DQI, even in the worst case over prime fields. This is shown by linking the problem to local leakage resilience in secret sharing schemes. For list sizes about half the field size, better solutions exist when the ratio n/m is at least 0.6225, and nearly perfect solutions when at least 0.7496. The results extend to similar problems from MDS codes for any list size fraction.

Core claim

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 have size ρp for ρ∼1/2, our results imply the existence of a solution that asymptotically beats the semicircle law whenever n/m≥0.6225, and we show that an asymptotically perfect solution exists whenever n/m≥0.7496. Our results generalize to Max-LINSAT problems derived from any Maximum Distance Separable (MDS) code, and to any ρ∈(0,1). The key insight is a connection to local leakage resilience of secret sharing schemes.

What carries the argument

The reduction from OPI to the local leakage resilience of secret sharing schemes, which is used to prove the existence of improved solutions.

If this is right

Existence of solutions beating the semicircle law for n/m ≥ 0.6225 when ρ ≈ 1/2.
Asymptotically perfect solutions for n/m ≥ 0.7496 when ρ ≈ 1/2.
Improved solutions for any ρ in (0,1) and for Max-LINSAT from MDS codes.
Several re-proofs of the existence of semicircle law solutions along the way.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

This suggests potential for classical algorithms to achieve better performance by drawing on leakage resilience techniques.
May have implications for designing better secret sharing schemes with local leakage resilience properties.
Could be extended to other quantum algorithms or interference-based methods in coding theory problems.

Load-bearing premise

The reduction mapping OPI instances to local leakage resilience questions in secret sharing is valid and preserves the asymptotic parameters over prime fields.

What would settle it

An explicit construction of an OPI instance with n/m = 0.7 and ρ = 0.5 where the maximum number of intersections is no larger than the semicircle law prediction, or a proof that the leakage resilience bound does not apply to the corresponding secret sharing scheme.

Figures

Figures reproduced from arXiv: 2604.09533 by Mary Wootters, Yihang Sun.

**Figure 1.** Figure 1: Three improvements on the semicircle law in the balanced case where ρ ∼ 1/2, including Theorems 1.5 and 1.6. The green curve is the result of applying techniques from leakage-resilient secret-sharing in an off-the-shelf way, which we discuss more in Section 1.2. We color code and mark the bounds on critical rates of each curve: 2µ0(ρ) is where each curve diverges from SCL1/2(µ), and 2µ1(ρ) when it hits 1 a… view at source ↗

**Figure 2.** Figure 2: Phase diagram for the upper bounds from Theorem 1.9 on the improvement and saturation thresholds as functions of input list density ρ. Observe critical densities ρ = 1/2 and the maximum density ρ ≈ 0.668 beyond which Theorem 1.9 does not improve from SCLρ(µ). The red bump is an artifact of the proof and can be replaced by the dashed segment. The green segment is a lower bound on the rate above which Theor… view at source ↗

**Figure 3.** Figure 3: For two example values ρ ∈ {0.4, 0.6}, we plot values of optimizers τ⋆, δ⋆, γ⋆ from Theorem 5.3, and satisfaction fraction improvement from SCLρ(µ) as functions of rate n/m = 2µ ∈ [0, 1]. The left plot is analogous to [PITH_FULL_IMAGE:figures/full_fig_p040_3.png] view at source ↗

**Figure 4.** Figure 4: On the left, we plot fρ(x) for various values of ρ and observe it is maximized at 1 − ρ if ρ ≤ 1/2 and at ρ if ρ ≥ 1/2. On the right, we plot ¯f(ρ)and observe it is maximized for ρ ∈ [0.5, 0.67] at ¯f(0.56) ≈ 0.9927. Combining with ∣sin(ρπ)∣ ≤ ρπ and (5.22), we can bound (5.21) above via exp( d[Eρ + Fρ] dτ ) ≤ ∣ sin(ρπ) ρπ ∣ 2(4¯µ(ρ)−1) fρ(gρ(µ¯(ρ))) ∶= ¯f(ρ). (5.24) Observe from [PITH_FULL_IMAGE:figures/… view at source ↗

read the original abstract

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 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$ have size $\rho p$ for $\rho \sim 1/2$, our results imply the existence of a solution that asymptotically beats the semicircle law whenever $n/m \geq 0.6225$, and we show that an asymptotically perfect solution exists whenever $n/m \geq 0.7496$. Our results generalize to Max-LINSAT problems derived from any Maximum Distance Separable (MDS) code, and to any $\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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper improves worst-case OPI existence bounds beyond the DQI semicircle law by linking to leakage resilience in MDS secret sharing.

read the letter

The main point is that this paper shows better existence results for worst-case Optimal Polynomial Intersection than what follows from the DQI semicircle law. Using a connection to local leakage resilience of secret sharing schemes built from MDS codes, they prove that for lists of size roughly half the field, there are solutions beating the semicircle law as long as n/m is at least 0.6225, and asymptotically perfect solutions exist for n/m at least 0.7496. This holds over prime fields and extends to related Max-LINSAT problems from any MDS code. They also recover the semicircle bounds as a corollary in the new framework. The paper does a good job establishing this link cleanly and showing how the old results fall out as a special case. The approach brings in ideas from cryptography to improve on prior existential results that had matched the algorithmic ones, which is a genuine shift rather than a routine tweak. The soft spots are limited. The numerical thresholds depend on the exact parameter mapping from leakage rates to the fraction of satisfied lists and the n/m ratio. The paper handles this translation directly without extra losses, so the stress-test concern about indirect mapping or hidden asymptotic-only issues does not hold up. The results remain asymptotic as field size grows, which is standard for these bounds, but the derivations look rigorous on inspection. The math, data-free claims, and citation pattern are solid with no circularity. This paper is for researchers working at the intersection of quantum algorithms, coding theory, and combinatorial optimization who care about worst-case existence guarantees for interpolation problems. A reader following DQI or MDS-code applications will get value from the new thresholds and the proof technique. It deserves serious peer review because the central improvement is supported by the external connection and the paper engages the literature honestly. I would send it out for review.

Referee Report

2 major / 2 minor

Summary. The paper claims to improve upon the existential bounds for worst-case Optimal Polynomial Intersection (OPI) instances over prime fields. By linking OPI to local leakage resilience properties of secret sharing schemes based on Maximum Distance Separable (MDS) codes, it demonstrates the existence of solutions that asymptotically outperform the semicircle law achieved by Decoded Quantum Interferometry (DQI) for parameters such as n/m ≥ 0.6225 when list sizes are approximately half the field size, and asymptotically perfect solutions for n/m ≥ 0.7496. The results extend to Max-LINSAT problems derived from any MDS code and arbitrary ρ in (0,1), while also providing alternative proofs for the semicircle law.

Significance. This result, if the reduction is rigorously established, is significant because it separates the best possible solutions from the performance of known efficient algorithms like DQI, showing that the semicircle law is not the optimal existential bound. The novel connection between combinatorial optimization problems and leakage resilience in cryptography provides a new tool for analyzing such problems and may inspire further cross-disciplinary work. Additionally, the re-derivation of the semicircle law existence results using this framework adds to the robustness of the findings. The specific numerical improvements for ρ ≈ 1/2 highlight practical relevance for certain regimes.

major comments (2)

The central improvement rests on the reduction from OPI existence to local leakage resilience of MDS-based secret sharing schemes. The abstract asserts that this yields the specific thresholds 0.6225 and 0.7496, but without an explicit parameter translation (how leakage rate and field size p map to the fraction of satisfied lists and the critical n/m ratio), it is impossible to confirm the thresholds follow directly without extra loss factors or p → ∞ assumptions.
Abstract: the claim that 'DQI and the semicircle law are not optimal' and the recovery of semicircle-law existence results are load-bearing for the paper's contribution, yet the abstract supplies no proof sketches, error terms, or derivations showing how the leakage-resilience bounds translate into the stated OPI solution quality.

minor comments (2)

The notation ρ and p (list size as fraction of field) should be defined at first use and related explicitly to the OPI input parameters for clarity.
The generalization statement to 'any ρ ∈ (0,1)' and 'any MDS code' would benefit from a brief remark on whether the numerical thresholds change with ρ or remain uniform.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and for recognizing the significance of the connection between worst-case OPI and local leakage resilience of MDS-based secret sharing. We address the two major comments below point by point.

read point-by-point responses

Referee: The central improvement rests on the reduction from OPI existence to local leakage resilience of MDS-based secret sharing schemes. The abstract asserts that this yields the specific thresholds 0.6225 and 0.7496, but without an explicit parameter translation (how leakage rate and field size p map to the fraction of satisfied lists and the critical n/m ratio), it is impossible to confirm the thresholds follow directly without extra loss factors or p → ∞ assumptions.

Authors: The manuscript contains the requested explicit translation. Section 3 establishes the reduction (Theorem 3.1) showing that an OPI instance with list-size fraction ρ and rate k = n/m is equivalent to the local leakage resilience of an MDS code of the same rate against leakage rate τ = 1 − (fraction of satisfied lists). Section 4 then specializes to Reed-Solomon codes and derives the numerical thresholds by taking the large-field limit p → ∞ while holding ρ fixed; the mapping is direct and incurs no multiplicative loss factors. Finite-p error terms are stated explicitly and vanish as p grows. We will add one sentence to the abstract clarifying that the stated thresholds are asymptotic (p → ∞) and directing readers to Sections 3–4 for the parameter correspondence. revision: partial
Referee: Abstract: the claim that 'DQI and the semicircle law are not optimal' and the recovery of semicircle-law existence results are load-bearing for the paper's contribution, yet the abstract supplies no proof sketches, error terms, or derivations showing how the leakage-resilience bounds translate into the stated OPI solution quality.

Authors: We agree the abstract is concise. The body supplies the missing elements: the leakage-resilience bounds for general MDS codes are taken from the literature (with explicit error terms for finite p), the translation to OPI solution quality is given by the equivalence in Theorem 3.1 together with the asymptotic analysis in Section 5, and the semicircle law is recovered by substituting the known leakage resilience of Reed-Solomon codes. We will revise the abstract to include a single high-level sentence sketching this chain of implications while preserving its length. revision: partial

Circularity Check

0 steps flagged

No significant circularity; central claims derive from external leakage-resilience connection

full rationale

The paper establishes improved existential bounds for OPI by mapping to local leakage resilience of MDS-based secret sharing schemes, an independent external notion whose parameters (leakage rate, field size) are not defined in terms of the semicircle law or OPI solution quality. The abstract explicitly states that the semicircle-law existence results are recovered as re-proofs along the way rather than presupposed, and the numerical thresholds (0.6225, 0.7496) are presented as consequences of the new mapping rather than fitted inputs or self-definitional quantities. No equation or step in the given text reduces a claimed prediction to a parameter fitted from the same data or to a self-citation whose content is itself unverified within the paper. The derivation therefore remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Only the abstract is available; no explicit free parameters, axioms, or invented entities are stated or derivable from the given text.

pith-pipeline@v0.9.0 · 5664 in / 1219 out tokens · 37851 ms · 2026-05-10T15:49:23.938845+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Regev's reduction as a candidate quantum algorithm for the discrete logarithm problem in finite abelian groups
quant-ph 2026-05 unverdicted novelty 6.0

Regev's reduction on Cheng-Wan DLOG instances does not yield an efficient quantum algorithm for discrete log because decoders fall short of the threshold and the Pretty Good Measurement is inefficient.

Reference graph

Works this paper leans on

7 extracted references · 3 canonical work pages · cited by 1 Pith paper

[1]

Arcs in finite projective spaces.EMS Surveys in Mathematical Sciences, 6(1):133–172, 2020

9, 10, 12, 14, 33, 34, 35 [BL20] Simeon Ball and Michel Lavrauw. Arcs in finite projective spaces.EMS Surveys in Mathematical Sciences, 6(1):133–172, 2020. 17 43 [BN00] Daniel Bleichenbacher and Phong Q Nguyen. Noisy polynomial interpolation and noisy chinese remaindering. InInternational conference on the theory and applications of cryptographic techniqu...

work page arXiv 2020
[2]

arXiv preprint arXiv:2510.10967 , year=

Springer, 2025. 10, 13 [KK23] Ohad Klein and Ilan Komargodski. New bounds on the local leakage resilience of Shamir’ssecretsharingscheme. InAnnual International Cryptology Conference, pages 139–170. Springer, 2023. 10, 13 [KSG+25] Tanuj Khattar, Noah Shutty, Craig Gidney, Adam Zalcman, Noureldin Yosri, Dmitri Maslov, Ryan Babbush, and Stephen P Jordan. Ve...

work page arXiv 2025
[3]

Im- proved bound on the local leakage-resilience of Shamir’s secret sharing

2, 11 44 [MNPCW22] Hemanta K Maji, Hai H Nguyen, Anat Paskin-Cherniavsky, and Mingyuan Wang. Im- proved bound on the local leakage-resilience of Shamir’s secret sharing. In2022 IEEE International Symposium on Information Theory (ISIT), pages 2678–2683. IEEE,
[4]

Con- structing locally leakage-resilient linear secret-sharing schemes

9, 10, 12, 13, 14, 33, 34, 35 [MPCSW21] Hemanta K Maji, Anat Paskin-Cherniavsky, Tom Suad, and Mingyuan Wang. Con- structing locally leakage-resilient linear secret-sharing schemes. InAnnual Interna- tional Cryptology Conference, pages 779–808. Springer, 2021. 9, 10, 12, 14, 33, 34, 35 [Ngu24] Hai H Nguyen. Towards breaking the half-barrier of local leaka...

2021
[5]

A nearly linear-time decoded quantum interferometry algorithm for the optimal polynomial intersection problem.arXiv preprint arXiv:2601.15171, 2026

10, 12 [NP99] Moni Naor and Benny Pinkas. Oblivious transfer and polynomial evaluation. In Proceedings of the thirty-first annual ACM symposium on Theory of computing, pages 245–254, 1999. 1, 13 [NS20] Jesper Buus Nielsen and Mark Simkin. Lower bounds for leakage-resilient secret shar- ing. InAnnual International Conference on the Theory and Applications ...

work page arXiv 1999
[6]

Two theorems on list decoding

2, 11 [RU10] Atri Rudra and Steve Uurtamo. Two theorems on list decoding. InInternational Workshop on Randomization and Approximation Techniques in Computer Science, pages 696–709. Springer, 2010. 15, 16 [Sha79] Adi Shamir. How to share a secret.Communications of the ACM, 22(11):612–613,

2010
[7]

An upper bound on the covering radius as a function of the dual distance.IEEE transactions on information theory, 36(6):1472–1474, 2002

9 [Tie02] AA Tietavainen. An upper bound on the covering radius as a function of the dual distance.IEEE transactions on information theory, 36(6):1472–1474, 2002. 2, 11 [TYB18] Itzhak Tamo, Min Ye, and Alexander Barg. The repair problem for Reed–Solomon codes: Optimal repair of single and multiple erasures with almost optimal node size. IEEE Transactions ...

2002