theoretical-computer-science / Information theory; average-case complexity
In the square Gaussian binary MIMO model $y = \sqrt{\rho/N}\,Hx^\star + w$, exhaustive maximum-likelihood detection recovers $x^\star$ once $\rho > 2\log N$, while sphere decoding at that threshold scale costs $\exp\{\Theta(N/\log N)\}$. Whether any polynomial-time detector reaches the same first-order threshold, or whether a computational-statistical gap separates them, was open. The claim: rounded linear MMSE followed by steepest single-bit descent recovers $x^\star$ with failure probability tending to zero, uniformly over every transmitted word, in $O(N^3)$ operations.
Temporal state
No reconciled state yet.
Append-only history
An average-case claim about the Gaussian model, not a contradiction of the worst-case NP-hardness of integer least squares. If it holds, no computational-statistical gap separates polynomial-time detection from exhaustive maximum likelihood at first order in this model.
Research memory
In the square Gaussian binary MIMO model $y = \sqrt{\rho/N}\,Hx^\star + w$, exhaustive maximum-likelihood detection recovers $x^\star$ once $\rho > 2\log N$, while sphere decoding at that threshold scale costs $\exp\{\Theta(N/\log N)\}$. Whether any polynomial-time detector reaches the same first-order threshold, or whether a computational-statistical gap separates them, was open. The claim: rounded linear MMSE followed by steepest single-bit descent recovers $x^\star$ with failure probability tending to zero, uniformly over every transmitted word, in $O(N^3)$ operations.
An average-case claim about the Gaussian model, not a contradiction of the worst-case NP-hardness of integer least squares. If it holds, no computational-statistical gap separates polynomial-time detection from exhaustive maximum likelihood at first order in this model.
Evidence graph
No public relationships recorded yet.