AI Settles a 25 Year-old Problem We Left Behind | XCancel

AI Settles a 25 Year-old Problem We Left Behind

Dimitris Papailiopoulos

@DimitrisPapail<br>22h

50

146

884

319,793

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 😊<br>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.<br>Full paper<br>Let me tell you a little more about it.<br>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.<br>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.<br>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.<br>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:<br>When recovering the transmitted bits is statistically possible, can we do it in poly-time?<br>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.<br>Until last week. And the final answer comes out to<br>YES! Whenever perfect detection is statistically possible, you can do it in polynomial time.<br>MIMO solved; Done.<br>But who cares? We’ll come back to this in a second.<br>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.<br>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.<br>The problem setting<br>So you transmit a binary vector x in {±1}^N, and receive<br>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.<br>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.<br>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.<br>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:<br>Can a poly-time algorithm recover the transmitted x when ML succeeds?

A brief history with a tiny bit of drama<br>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.<br>Hassibi and Vikalo in 2001 were the first—as far as I know—to argue that there is hope for an average...