Tight inapproximability of max-LINSAT and implications for decoded quantum interferometry
We establish tight inapproximability bounds for max-LINSAT, the problem of maximizing the number of satisfied linear constraints over the finite field $\mathbb{F}_q$, where each constraint accepts $r$ values. Specifically, we prove by a direct reduction from Håstad's theorem that no polynomial-time algorithm can exceed the random-assignment ratio $r/q$ by any constant, assuming $\mathsf{P} \neq \mathsf{NP}$. This threshold coincides with the $\ell/m \to 0$ limit of the semicircle law governing decoded quantum interferometry (DQI), where $\ell$ is the decoding radius of the underlying code.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2603.04540
curl -X POST /api/v1/records/arxiv/2603.04540/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2603.04540/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'