Polynomial-Time MIMO Detection at the ML Threshold
In the square Gaussian binary MIMO model , exhaustive maximum-likelihood detection recovers once , while sphere decoding at that threshold scale costs . 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 with failure probability tending to zero, uniformly over every transmitted word, in operations.
- Result
- Proved(see note)
- Status
- Candidate (review pending)
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Information theory; average-case complexity
- Posed by
- —
- Year posed
- —
- Years open
- —
- Solved
- 2026-08-08
- Model
- GPT-5.6, Claude Fable 5
- Vendor
- OpenAI, Anthropic
- Collaborators
- Dimitris Papailiopoulos
- Verification
- Unreviewed
- Publication
- Announced
- Significance
- 18 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
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.
What the AI did
The manuscript's footnote in full: "The results in this paper were proved by GPT-5.6 and Claude Fable 5, which also drafted the initial manuscript. The author posed the problem, directed several rounds of proof simplification, verified all mathematical arguments, edited the manuscript, and takes full responsibility for its content." By the author's public account, Claude proposed the algorithm (signed LMMSE plus greedy bit flips) and GPT repaired and simplified the proof over several days of directed iteration.
Verification
A 46-page manuscript posted to the author's own site and announced on X, days old, with no independent review and no formalization. The author states he checked every argument line by line over about five days, and he has published previously on polynomial-complexity ML detection, so the domain expertise is real; neither fact is independent scrutiny, which is why this is a candidate.
Sources
Submitted by VibeGene on