On Worst-Case Optimal Polynomial Intersection

1. Problem Definition: Optimal Polynomial Intersection (OPI)

The paper addresses the Optimal Polynomial Intersection (OPI) problem, which asks for a low-degree polynomial that satisfies a large number of constraints on its evaluations.

• Formal Setup: Given a finite field $\mathbb{F}_q$, distinct evaluation points $a_1, \dots, a_m \in \mathbb{F}_q$, and subsets $S_1, \dots, S_m \subseteq \mathbb{F}_q$ (where $|S_i| = \rho q$), the goal is to find a polynomial $Q \in \mathbb{F}_q[x]$ with $\deg(Q) < n$ that maximizes the satisfaction ratio:
  $$s(Q) = \frac{1}{m} |\{i \in \{1, \dots, m\} : Q(a_i) \in S_i\}|$$
• Context: This problem is central to list-recovery of Reed-Solomon codes and noisy polynomial reconstruction in cryptography.
• The Quantum Benchmark: The Decoded Quantum Interferometry (DQI) algorithm [JSW+25] provides an efficient quantum solution for OPI. In the worst case, DQI achieves a satisfaction ratio approaching the Semicircle Law (SCL):
  $$SCL_\rho(\mu) = \begin{cases} (\sqrt{\mu(1-\rho)} + \sqrt{\rho(1-\mu)})^2 & \text{if } \mu + \rho \le 1 \\ 1 & \text{if } \mu + \rho \ge 1 \end{cases}$$
  where $\mu = n/2m$ is the code rate.
• The Open Question: Does DQI find the optimal solution in the worst case? Prior to this work, it was unknown if better solutions existed for worst-case instances, as existential bounds matched algorithmic ones.

2. Methodology and Technical Framework

The authors develop a framework to prove the existence of solutions that asymptotically beat the Semicircle Law. Their approach combines tools from coding theory, discrepancy theory, and local leakage resilience in secret sharing.

A. Re-proving the Semicircle Law Barrier

The authors first provide two new, simplified classical proofs for the existence of solutions achieving the Semicircle Law, moving away from the "proof-by-quantum-algorithm" approach:

1. Moments Problem Proof: They show that for a uniform random solution $x$, the number of satisfied constraints has the same first $n$ moments as a Binomial distribution $Bin(m, 1/2)$. Using the theory of orthogonal polynomials (specifically Kravchuk polynomials), they show the maximum possible value is bounded by the largest root of these polynomials, which converges to the Semicircle Law.
2. Discrepancy Proof: They define a $k$-wise discrepancy function $q_k(x)$ and analyze the expected satisfaction ratio under a specific probability distribution $P_u(x) \propto (\sum u_k q_k(x))^2$. They demonstrate that if the cutoff $\ell$ (related to the degree of the polynomial) is restricted to $\ell < d^\perp/2$ (where $d^\perp$ is the dual distance), the analysis is stuck at the Semicircle Law.

B. Breaking the Barrier: Extending Beyond $d^\perp$

To improve upon the Semicircle Law, the authors propose increasing the cutoff parameter $\ell$ to $\ell = (\mu + \delta)m$ where $\delta > 0$. This allows the algorithm to "see" beyond the minimum distance of the code.

• The Challenge: Increasing $\ell$ introduces "correction terms" in the expected satisfaction expansion involving $t \ge d^\perp$. These terms correspond to the expectation of discrepancies $E[q_t(x)]$ for high weights $t$.
• The Solution: The authors must prove that these correction terms are exponentially small. They achieve this by establishing a connection to Local Leakage Resilience in secret sharing schemes.

C. Connection to Leakage Resilience

The term $E[q_t(x)]$ is shown to be equivalent to a Fourier sum over the dual code $C^\perp$, which appears in the analysis of Massey secret sharing schemes (a generalization of Shamir's scheme).

• Key Insight: The quantity to be bounded is the "per-transcript leakage" of the secret sharing scheme.
• Improvement over Prior Work: Existing bounds on leakage resilience (e.g., [MNPCW22]) used a "union bound" approach over coordinate sets. The authors improve this by:
  1. Splitting the coordinates into many overlapping sets (buckets) $B_j$.
  2. Using a probabilistic argument to show that for any high-weight vector $y$, there exists a bucket $B_j$ where the intersection $|supp(y) \cap B_j|$ is large.
  3. Applying Cauchy-Schwarz and Fourier analysis to bound the sum, achieving a tighter exponential decay rate than previous leakage-resilience results.

3. Key Contributions and Results

A. Existential Improvements over the Semicircle Law

The main contribution is proving that for prime fields $\mathbb{F}_p$, there exist solutions strictly better than the Semicircle Law for a wide range of parameters $(\rho, \mu)$.

• Balanced Case ($\rho \approx 1/2$):

  • Improvement Threshold: The authors prove that for rates $2\mu \ge 0.6225$, there exist solutions with satisfaction ratio $SCL_{1/2}(\mu + \delta) > SCL_{1/2}(\mu)$.
  • Saturation Threshold: They show that an asymptotically perfect solution ($s(x) \to 1$) exists whenever $2\mu \ge 0.7496$.
  • Comparison: This improves upon the previous best known threshold for perfect solutions ($0.78$) derived from leakage resilience literature and the $3/4$ threshold for average-case hybrid models.

• General Biased Case ($\rho \in (0,1)$):

  • They generalize the result to arbitrary list sizes $\rho p$.
  • They derive a phase diagram (Figure 2) showing the improvement and saturation thresholds as functions of $\rho$.
  • They identify a critical density $\rho \approx 0.668$ beyond which their current technique cannot improve upon the Semicircle Law (due to a barrier in the Fourier proxy analysis).

B. New Proofs and Techniques

• Simplified Proofs: Provided two classical, combinatorial re-proofs of the Semicircle Law existence, clarifying the barrier at $d^\perp/2$.
• Leakage Resilience Bounds: Improved the bounds on the Fourier proxy for local leakage resilience in Massey secret sharing, lowering the rate threshold for one-bit leakage resilience from $0.78$ to $0.7496$ (though noting that newer non-Fourier methods have surpassed this).

4. Significance and Implications

1. Quantum Advantage Limits: The results demonstrate that the Semicircle Law achieved by DQI is not optimal in the worst case. This suggests that while DQI is efficient, there is a "gap" between what quantum algorithms currently achieve and the theoretical maximum for worst-case OPI.
2. Algorithmic Potential: While the current results are existential (proving such solutions exist without providing an efficient algorithm to find them), the framework suggests a path toward improved quantum algorithms. The authors discuss the difficulty of implementing this via DQI (specifically the "syndrome decoding" bottleneck for $\ell > d^\perp/2$) but hope future work can bridge this gap.
3. Cross-Disciplinary Impact: The paper successfully bridges Quantum Computing, Coding Theory, and Cryptography (Secret Sharing). It shows that techniques developed for analyzing leakage in secret sharing can be repurposed to solve hard combinatorial optimization problems like OPI.
4. Open Problems: The authors highlight the challenge of converting these existential results into efficient algorithms (Question 1.17) and determining the true optimal saturation threshold $\mu_1(\rho)$ (Question 1.14).

Summary of Thresholds (Balanced Case $\rho \sim 1/2$)

In conclusion, this work fundamentally shifts the understanding of the OPI problem by proving that the Semicircle Law is a suboptimal barrier for worst-case instances over prime fields, leveraging deep connections to secret sharing leakage resilience to establish the existence of superior solutions.