From Reverse Detection--Estimation Gaps to Computational Lower Bounds for Norm Approximation

Runshi Tang, Yuefeng Han, Anru R. Zhang

arXivarxiv/2604.00966Apr 1, 2026math.STscore 0

We develop a general reduction scheme that converts reverse detection--estimation gaps into computational lower bounds for norm approximation. If an efficiently computable estimator has error well below a conjectured computational detection threshold, then a sufficiently accurate norm approximator applied to this estimator would yield an efficient test, transferring average-case detection hardness to worst-case approximation hardness. The ratio between the detection and estimation scales becomes a lower bound on the achievable approximation factor. We apply the reduction in three settings.…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2604.00966
curl -X POST /api/v1/records/arxiv/2604.00966/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.00966/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'