{"id":"arxiv/2604.00966","url":"https://arxiv.org/abs/2604.00966","tags":["math.ST","cs.CC"],"score":0,"title":"From Reverse Detection--Estimation Gaps to Computational Lower Bounds for Norm Approximation","domain":"math.ST","source":"arxiv","authors":["Runshi Tang","Yuefeng Han","Anru R. Zhang"],"reviews":0,"subject":"math.ST","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-01","reactions":{}}