待翻譯：AI Settles a 25 Year-Old Problem We Left Behind

AI 服務暫時不可用，以下為來源正文，待恢復後補全翻譯。

Last week, GPT-5.6 and Claude Fable appear to have settled an open theoretical question in wireless communications that was intensely studied between 2000 till the 2010s and that I briefly worked on as an anxious first-year PhD student. The answer finally arrived, perhaps because I was one of the last few to ask the question and the first to prompt the machines to solve it 😊 The result: you send N bits through an N×N Gaussian wireless channel, and the receiver must recover all of them exactly. It has been known since the 2000s that it is information theoretically possible to do so when the signal-to-noise ratio is at least 2 log N. But the only method known to reach that was an exponential search algorithm. There is now proof that a simple, polynomial-time algorithm succeeds at the exact same threshold. Full paper Let me tell you a little more about it. In 2009, I worked on my first paper with Alex Dimakis (@AlexGDimakis), who soon after became my PhD advisor (not because of that paper): The paper was among many attempts to offer a polynomial time solution to MIMO detection. What is MIMO detection you ask? A transmitter sends a vector of N bits through a wireless channel of N transmit and N receive antennas. The channel mixes the bits all together and adds noise. The receiver, who knows the channel matrix, has to figure out which bits were sent. The block-error optimal receiver, aka the maximum likelihood (ML) detector, solves exactly this problem by finding the most likely vector that could have been sent, given the received signal. In this case, ML detection boils down to solving this fundamental discrete least squares problem: Unfortunately, as with all good problems in life… ML detection is NP-hard. Yet we are not TCS pessimists, and wireless channels are not worst-case, they are random, and the community had been working on the following question since the early 2000s: When recovering the transmitted bits is statistically possible, can we do it in poly-time? We didn’t make much progress on that question in that 2010 paper above, and despite plenty of work in the area, the problem has, as far as I understand, remained open since 2001… aka a QUARTER OF A CENTURY to make it sound more dramatic. Until last week. And the final answer comes out to YES! Whenever perfect detection is statistically possible, you can do it in polynomial time. MIMO solved; Done. But who cares? We’ll come back to this in a second. I am attaching the paper and I have spent 5+ days going back and forth with the models to simplify the proofs and the exposition (which was originally an absolute disaster), a process that took much much longer than the initial proof that GPT produced (which took around 30 minutes or so). The proof is long, but relatively elementary. I have verified everything and to the best of my ability to proof check, it is correct. Now let me talk a bit more about the problem and its history, and why I think it’s worth writing about even though the field has moved on from this specific corner of MIMO detection theory. The problem setting So you transmit a binary vector x in {±1}^N, and receive {\bf y} = \sqrt{\frac{SNR}{N}}{\bf H}{\bf x}+{\bf w} where H is N×N and both H and w have iid N(0,1) entries, all independent. The receiver knows H and the noise statistics, but not w, and wants x back from y. The block error optimal solution to the recovery problem is equal to BTW this optimization comes under different guises too: MIMO detection, CDMA multi-user detection, integer least squares, closest vector in a lattice, etc etc. And when SNR = ∞ (i.e., effective noise 0) the problem becomes trivial: the channel matrix H is invertible with probability 1, so you invert it, and recover the exact x with inv(H)*y. At the other extreme, when SNR = 0, there’s nothing you can detect from noise, and ML detection fails. But somewhere in between 0 and infinity, ML detection succeeds, and does so precisely at SNR = 2 log N. This means that solving the optimization problem above allows you to perfectly recover all the bits of the transmitted N-bit sequence with probability tending to 1, and below (up to additive loglogN terms) the probability of block recovery tends to 0. So above 2logN, the transmitted signal is an optimum of the ML optimization problem, but solving it seems to require an exhaustive search over all possible N-bit sequences. So the question we now care about is: Can a poly-time algorithm recover the transmitted x when ML succeeds? A brief history with a tiny bit of drama The question of solvability of the integer least squares problem is at least as old as 1989, when Verdú proved that it is NP-hard in the general case. But NP-hardness is a worst-case statement, and our instances are not. Hassibi and Vikalo in 2001 were the first—as far as I know—to argue that there is hope for an average case, poly-time solution. The algorithm they analyzed was a popular method at the time, the Sphere Decoder (SD), dating back to Fincke and Pohst in 1985. The Sphere Decoder was of particular interest because 1) it’s an exact ML algorithm, i.e., always outputs the minimizer and 2) it seemed to be way faster than exponential time in practice. So the hope was that one could actually prove that SD runs in poly-time. This is what H&V articulated in their paper: they derived a formula for the expected complexity of the Sphere Decoder, averaged over the channel and the noise, and showed that it looks polynomial. If that was true, the question was settled. That seemed like an incredible result. Then Jaldén and Ottersten in 2005 showed that the asymptotic interpretation was not quite correct: at any fixed SNR, no matter how large, the expected complexity of sphere decoding is in fact exponential in the problem dimension. So since exact and fast was not working, the field spent considerable effort working on approximations to the ML optimization problem. Semidefinite relaxations with approximation guarantees and tightness conditions at high SNR, but no sharp threshold. Bit-flipping local search seemed to match ML in simulations but no full proofs of matching the ML recovery threshold. The AMP literature rigorously characterized the per-bit error, at fixed SNR, where block recovery isn’t possible. Statistical physics produced poly-time methods that were predicted to track exact ML using replica-level arguments, but as far as I understand, no proof. And the paper with Babak and Alex from 2010 above analyzed an MCMC method proving that after mixing, the stationary distribution puts non-vanishing mass on the correct solution but did not prove anything about the mixing time, which is the difficult part. In all those years, it seems to me, exactly one polynomial-time method came with rigorous block-recovery guarantees at any SNR scale: the box relaxation, in 2020, shown to recover the block when the SNR scales like 4 log N and, provably, not below. As an aside, it’s kind of interesting that the probabilistic tools needed to analyze such a technique matured in the late 2010s, which for the most part was after the community moved on and had already dispersed. And since then… not a lot of activity. So long story short, the gap between what ML achieves and what any polynomial-time method could provably achieve never closed. What did GPT & Claude do and how we got a proof that I, Dimitris, can verify? Motivated by the recent unreasonable successes of frontier models on hard math tasks, I decided to go back to problems that haunted me as a graduate student (I used to work on information and coding theory) and start pointing the death star at them. This is precisely how it feels to ask hard math questions and have GPT zero shot them: But I knew there was a bit of a problem. Even if I got back a full answer to any question that I’d ask, I’d be bottlenecked by having to verify it if I wanted to share it more broadly. One, because I don’t want to embarrass myself if it turns out to be wrong, and two, because sharing is the main reason we ask questions and do science anyways. So, I decided to pick what felt like one of the most ambitious questions that bothered me early in my PhD, and one that was clean to state, and still open. So, I asked GPT-5.6 and Claude Fable 5 when ML MIMO detection can be solved in poly-time. Both produced proofs for different algorithms confidently stating that that there is no gap! There is a polynomial-time algorithm that succeeds at SNR above 2 log N, matching exactly (up to additive loglog terms, but who cares) the ML recovery threshold. But there was a small problem 😊 GPT's algorithm was an AMP variant. And I hate AMP, with a passion, because I do not, for the life of me, understand any of its analyses. And so I told it to try and reprove the same result, if possible, for a simpler algorithm. Indeed, GPT produced another algorithm that I also found counter-intuitive, and one that I have never seen used before! Fable, on the other hand, came up with something I really liked: signed LMMSE, then greedy bit flips. An algorithm that was introduced in the past and actually used in practice. But there was another problem! According to GPT, Fable’s proof was mostly wrong.. but salvageable. So I decided to stick with the algorithm that Fable suggested, and asked GPT to take Fable’s proof and fix it. And it did! But there was yet another problem, this new proof was UNREADABLE: a wall of notation, variables pointing to variables pointing to ratios of variables defining other variables, exotic matrix-analysis and probability machinery, Marchenko–Pastur adjacent stuff that gives me the hives, and other beautiful things. So for around 4-5 days I kept going back and forth between the two models and asking them to give me the dumbest possible set of steps, for each of the big components needed for the proof to work out. I explicitly told them that it was OK for the bounds and constants to get worse, AS LONG AS the 2 log N threshold remains, all for the purpose of simplicity. All I wanted was a proof that an old dinosaur with a short attention span can digest without crying. I actually asked GPT and Claude to share back the messages where I was whining the most, lol My favorite: Why did I insist on super simple steps? Because I wanted to verify this myself, end to end. And no, I don’t want to use Lean it DOES NOT solve my problem. Formal verification just moves the abstraction level somewhere else!! You still have to verify that the English of a lemma faithfully translates to Lean, which is a language I don't understand. Yeah, forget about it. I don’t like Lean, sorry. But I do understand basic linear algebra and probability, and I trust myself verifying such steps. So that’s the level the proof I demand. It then took multiple days of prompting and prompting and prompting, with the models simplifying each other’s arguments, while I kept complaining and rejecting anything I could not follow. And in the end it worked! We ended up with a proof that I fully understand, and that I have now checked line by line. Proving the thing took 30 minutes and making it verifiable by me took 5ish days. That’s a bit of an insane ratio, but it is what it is. And the result: a simple algorithm works whenever maximum likelihood works, in polynomial time. There is no computational-statistical gap in this problem. BOOM! What is the high level of the proof? The algorithm is almost embarrassingly simple. But why does this work? LMMSE followed by rounding gets you, in terms of Hamming distance, within a vanishing fraction of the transmitted signal, i.e., o(N) away from the truth. Then, greedy bit-flipping can’t get stuck because the per-step descent gains (i.e., how much the cost improves) are governed by Gaussian quantities, and their uniform concentration establishes that every non-ground-truth vector within a certain ball offers a strictl [truncated for AI cost control]