Random linear codes over finite fields satisfy near-optimal discrepancy properties, enabling list-decoding and zero-error list-recovery above capacity that match random codes.
A nearly linear-time decoded quantum interferometry algorithm for the optimal polynomial intersection problem
5 Pith papers cite this work. Polarity classification is still indexing.
5
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
years
2026 5verdicts
UNVERDICTED 5roles
background 1polarities
background 1representative citing papers
Multivariate DQI uses N-variable polynomials for weighted Max-LINSAT, derives closed-form asymptotics for expectation and concentration, provides a single-decoder preparation circuit, and shows outperformance over weighted Prange for some OPI cases while extending to Hamiltonian DQI.
Existence of asymptotically better solutions than the semicircle law for worst-case OPI over prime fields when n/m exceeds thresholds like 0.6225 for rho approximately 1/2, via connection to local leakage resilience of secret sharing.
Extends NP-hardness of exceeding r/q + O(1/sqrt(D)) for bounded-degree max-Ek-LINSAT(q,r) over F_q and shows quantum decoding is required for DQI to achieve the hardness-optimal 1/sqrt(D) scaling.
Decoded quantum interferometry is generalized to translation association schemes, reducing analysis to tridiagonal eigenvalue problems, with a finite-field matrix rank-difference protocol that produces constant-probability residual-rank bounds but no additive optimality guarantee.
citing papers explorer
-
Discrepancy for Random Linear Codes
Random linear codes over finite fields satisfy near-optimal discrepancy properties, enabling list-decoding and zero-error list-recovery above capacity that match random codes.
-
Multivariate Decoded Quantum Interferometry for Weighted Optimization
Multivariate DQI uses N-variable polynomials for weighted Max-LINSAT, derives closed-form asymptotics for expectation and concentration, provides a single-decoder preparation circuit, and shows outperformance over weighted Prange for some OPI cases while extending to Hamiltonian DQI.
-
On Worst-Case Optimal Polynomial Intersection
Existence of asymptotically better solutions than the semicircle law for worst-case OPI over prime fields when n/m exceeds thresholds like 0.6225 for rho approximately 1/2, via connection to local leakage resilience of secret sharing.
-
Approximability limits for bounded-degree max-LINSAT and implications for decoded quantum interferometry
Extends NP-hardness of exceeding r/q + O(1/sqrt(D)) for bounded-degree max-Ek-LINSAT(q,r) over F_q and shows quantum decoding is required for DQI to achieve the hardness-optimal 1/sqrt(D) scaling.
-
Decoded Quantum Interferometry Beyond Hamming: Rank-Metric and Translation Association Schemes
Decoded quantum interferometry is generalized to translation association schemes, reducing analysis to tridiagonal eigenvalue problems, with a finite-field matrix rank-difference protocol that produces constant-probability residual-rank bounds but no additive optimality guarantee.